Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] GCD result

Expand Messages
  • Joshua Zucker
    ... Hard to prove, because it s false. For example: GCD(254, 2^(2*254^2)-2) = 254. GCD(423, 2^(2*423^2)-2) = 47. similarly 635 - a GCD of 127 658 - 94 1143
    Message 1 of 6 , Jan 27, 2007
    • 0 Attachment
      On 1/27/07, Sebastian Martin <sebi_sebi@...> wrote:
      > Prove that:
      >
      > GCD(n,2^(2n^2) - 2)= 1 if n is odd
      > 2 if n is even
      > for all integer n.

      Hard to prove, because it's false.

      For example:
      GCD(254, 2^(2*254^2)-2) = 254.
      GCD(423, 2^(2*423^2)-2) = 47.
      similarly 635 -> a GCD of 127
      658 -> 94
      1143 -> 127
      1504 -> 94
      1524 -> 254
      1739 -> 47
      2032 -> 254
      2413 -> 127
      2585 -> 47

      Now, explaining why 47 and 127 appear as the common factors (other
      than the obvious 1s and 2s), that sounds like it might be interesting.

      Are there other (larger) numbers that will appear later?

      --Joshua Zucker
    • Phil Carmody
      Removing individuals from the To: list. I know I certainly don t need to receive things both by direct mail and the list, and am projecting that onto others.
      Message 2 of 6 , Jan 28, 2007
      • 0 Attachment
        Removing individuals from the To: list. I know I certainly don't need to
        receive things both by direct mail and the list, and am projecting that onto
        others.

        --- Joshua Zucker <joshua.zucker@...> wrote:
        > On 1/27/07, Sebastian Martin <sebi_sebi@...> wrote:
        > > Prove that:
        > >
        > > GCD(n,2^(2n^2) - 2)= 1 if n is odd
        > > 2 if n is even
        > > for all integer n.
        >
        > Hard to prove, because it's false.

        And not just false, but ...

        > For example:
        > GCD(254, 2^(2*254^2)-2) = 254.
        > GCD(423, 2^(2*423^2)-2) = 47.

        ... you guessed it - falsifiable with very small examples that can be found in

        ? for(n=1,500,g=gcd(n,lift(Mod(2,n)^(2*n^2))-2);if(g>2-n%2,print(n" "g)))
        254 254
        423 47
        time = 0 ms.

        no time at all!

        > similarly 635 -> a GCD of 127
        > 658 -> 94
        > 1143 -> 127
        > 1504 -> 94
        > 1524 -> 254
        > 1739 -> 47
        > 2032 -> 254
        > 2413 -> 127
        > 2585 -> 47
        >
        > Now, explaining why 47 and 127 appear as the common factors (other
        > than the obvious 1s and 2s), that sounds like it might be interesting.
        >
        > Are there other (larger) numbers that will appear later?

        Pruning:

        ?
        for(n=1,10000,p=eulerphi(n);g=gcd(n,lift(Mod(2,n)^(2*n^2%p))-2)/(2-n%2);if(g>1&&g!=47&&g!=127,print(n"
        "factor(g))))
        7024 Mat([439, 1])
        8843 Mat([239, 1])
        time = 84 ms.

        Pruning further:

        ?
        for(n=10000,100000,p=eulerphi(n);g=gcd(n,lift(Mod(2,n)^(2*n^2%p))-2)/(2-n%2);if(g>1&&g!=47&&g!=127&&g!=239&&g!=439,print(n"
        "factor(g))))
        11601 Mat([1289, 1])
        25661 Mat([383, 1])
        33530 Mat([479, 1])
        47020 Mat([2351, 1])
        47492 Mat([383, 1])
        47693 Mat([1289, 1])
        58871 Mat([3463, 1])
        63477 Mat([2351, 1])
        75837 Mat([1487, 1])
        80129 Mat([11447, 1])
        80951 Mat([479, 1])
        81122 Mat([863, 1])
        90260 Mat([4513, 1])
        94045 Mat([2687, 1])
        98814 Mat([383, 1])

        Pruning even further:
        ?
        for(n=100000,1000000,p=eulerphi(n);g=gcd(n,lift(Mod(2,n)^(2*n^2%p))-2)/(2-n%2);if(g>1&&g!=47&&g!=127&&g!=239&&g!=439&&g!=383&&g!=479&&g!=863&&g!=1289&&g!=1487&&g!=2351&&g!=2687&&g!=3463&&g!=4513&&g!=11447,print(n"
        "factor(g))))
        103526 Mat([1399, 1])
        105121 Mat([3391, 1])
        122230 Mat([719, 1])
        129806 Mat([1583, 1])
        133910 Mat([1913, 1])
        135891 Mat([719, 1])
        160404 Mat([13367, 1])
        160424 Mat([1823, 1])
        222441 Mat([1399, 1])
        233118 Mat([1439, 1])
        236587 Mat([18199, 1])
        244729 [47, 1; 127, 1]
        247126 [47, 1; 239, 1]
        278062 Mat([3391, 1])
        302122 Mat([5209, 1])
        314739 Mat([11657, 1])
        323297 Mat([1913, 1])
        324206 Mat([3449, 1])
        355327 Mat([2207, 1])
        367372 Mat([3167, 1])
        380351 Mat([719, 1])
        382016 [47, 1; 127, 1]
        387643 Mat([13367, 1])
        393213 Mat([131071, 1])
        394012 Mat([719, 1])
        400377 Mat([3607, 1])
        401590 Mat([5737, 1])
        406831 Mat([1583, 1])
        416783 Mat([18121, 1])
        429493 Mat([1399, 1])
        431079 Mat([13063, 1])
        452335 Mat([6959, 1])
        459699 Mat([4943, 1])
        463601 Mat([5209, 1])
        488304 Mat([3391, 1])
        510598 Mat([23209, 1])
        525518 Mat([37537, 1])
        532048 Mat([3023, 1])
        539036 Mat([7927, 1])
        548408 Mat([1399, 1])
        550773 Mat([20399, 1])
        555051 Mat([26431, 1])
        575577 Mat([2063, 1])
        578993 [47, 1; 127, 1]
        591117 Mat([1913, 1])
        638472 Mat([719, 1])
        652133 Mat([719, 1])
        661245 Mat([3391, 1])
        666752 Mat([5209, 1])
        698119 [127, 1; 239, 1]
        699325 Mat([2543, 1])
        708451 Mat([13367, 1])
        716280 [47, 1; 127, 1]
        721649 Mat([23279, 1])
        748547 Mat([20231, 1])
        755460 Mat([1399, 1])
        780504 Mat([1913, 1])
        801523 Mat([1439, 1])
        818515 [127, 1; 1289, 1]
        828231 Mat([5209, 1])
        845322 Mat([1583, 1])
        871487 Mat([3391, 1])
        874375 Mat([1399, 1])
        896593 Mat([719, 1])
        910254 Mat([719, 1])
        915291 Mat([7823, 1])
        935690 Mat([13367, 1])
        948831 Mat([24329, 1])
        964458 Mat([4871, 1])
        969553 Mat([5737, 1])
        time = 10,649 ms.


        What do we conclude from this:

        1) Post not requests for proofs of simply-falsifiable things to multiple
        mailing lists, lest thee bring upon thyself a gargantuan public shaming in
        so-doing.

        2) Use Pari/GP to avoid (1)

        3) Other stuff, dunno what. Joshua - do you want to take over from here?

        Phil


        () ASCII ribbon campaign () Hopeless ribbon campaign
        /\ against HTML mail /\ against gratuitous bloodshed

        [stolen with permission from Daniel B. Cristofani]



        ____________________________________________________________________________________
        Need a quick answer? Get one in minutes from people who know.
        Ask your question on www.Answers.yahoo.com
      • Phil Carmody
        ... The first appearance of all primes that appear before n=30000000 can be found in the file gcd(n,2^(2n^2)-2) in the Prime Tables folder of the
        Message 3 of 6 , Jan 28, 2007
        • 0 Attachment
          --- Phil Carmody <thefatphil@...> wrote:
          > 3) Other stuff, dunno what. Joshua - do you want to take over from here?

          The first appearance of all primes that appear before n=30000000 can be found
          in the file "gcd(n,2^(2n^2)-2)" in the Prime Tables folder of the primenumbers
          yahoogroup.

          Some primes appear quite late. p=11423 only appears at n=29596993.

          Phil

          () ASCII ribbon campaign () Hopeless ribbon campaign
          /\ against HTML mail /\ against gratuitous bloodshed

          [stolen with permission from Daniel B. Cristofani]



          ____________________________________________________________________________________
          Want to start your own business?
          Learn how on Yahoo! Small Business.
          http://smallbusiness.yahoo.com/r-index
        • Sebastian Martin
          I am sorry to have committed this mistake. I promise to check better the results. But I verified it for several chains of 200 numbers and only 1 and 2 were
          Message 4 of 6 , Jan 28, 2007
          • 0 Attachment
            I am sorry to have committed this mistake.
            I promise to check better the results.
            But I verified it for several chains of 200 numbers and only 1 and 2 were going out.
            Nevertheless I believe that this has interest.

            Sincerely

            Serbastian Martin Ruiz

            Phil Carmody <thefatphil@...> escribió:
            Removing individuals from the To: list. I know I certainly don't need to
            receive things both by direct mail and the list, and am projecting that onto
            others.

            --- Joshua Zucker <joshua.zucker@...> wrote:
            > On 1/27/07, Sebastian Martin <sebi_sebi@...> wrote:
            > > Prove that:
            > >
            > > GCD(n,2^(2n^2) - 2)= 1 if n is odd
            > > 2 if n is even
            > > for all integer n.
            >
            > Hard to prove, because it's false.

            And not just false, but ...

            > For example:
            > GCD(254, 2^(2*254^2)-2) = 254.
            > GCD(423, 2^(2*423^2)-2) = 47.

            ... you guessed it - falsifiable with very small examples that can be found in

            ? for(n=1,500,g=gcd(n,lift(Mod(2,n)^(2*n^2))-2);if(g>2-n%2,print(n" "g)))
            254 254
            423 47
            time = 0 ms.

            no time at all!

            > similarly 635 -> a GCD of 127
            > 658 -> 94
            > 1143 -> 127
            > 1504 -> 94
            > 1524 -> 254
            > 1739 -> 47
            > 2032 -> 254
            > 2413 -> 127
            > 2585 -> 47
            >
            > Now, explaining why 47 and 127 appear as the common factors (other
            > than the obvious 1s and 2s), that sounds like it might be interesting.
            >
            > Are there other (larger) numbers that will appear later?

            Pruning:

            ?
            for(n=1,10000,p=eulerphi(n);g=gcd(n,lift(Mod(2,n)^(2*n^2%p))-2)/(2-n%2);if(g>1&&g!=47&&g!=127,print(n"
            "factor(g))))
            7024 Mat([439, 1])
            8843 Mat([239, 1])
            time = 84 ms.

            Pruning further:

            ?
            for(n=10000,100000,p=eulerphi(n);g=gcd(n,lift(Mod(2,n)^(2*n^2%p))-2)/(2-n%2);if(g>1&&g!=47&&g!=127&&g!=239&&g!=439,print(n"
            "factor(g))))
            11601 Mat([1289, 1])
            25661 Mat([383, 1])
            33530 Mat([479, 1])
            47020 Mat([2351, 1])
            47492 Mat([383, 1])
            47693 Mat([1289, 1])
            58871 Mat([3463, 1])
            63477 Mat([2351, 1])
            75837 Mat([1487, 1])
            80129 Mat([11447, 1])
            80951 Mat([479, 1])
            81122 Mat([863, 1])
            90260 Mat([4513, 1])
            94045 Mat([2687, 1])
            98814 Mat([383, 1])

            Pruning even further:
            ?
            for(n=100000,1000000,p=eulerphi(n);g=gcd(n,lift(Mod(2,n)^(2*n^2%p))-2)/(2-n%2);if(g>1&&g!=47&&g!=127&&g!=239&&g!=439&&g!=383&&g!=479&&g!=863&&g!=1289&&g!=1487&&g!=2351&&g!=2687&&g!=3463&&g!=4513&&g!=11447,print(n"
            "factor(g))))
            103526 Mat([1399, 1])
            105121 Mat([3391, 1])
            122230 Mat([719, 1])
            129806 Mat([1583, 1])
            133910 Mat([1913, 1])
            135891 Mat([719, 1])
            160404 Mat([13367, 1])
            160424 Mat([1823, 1])
            222441 Mat([1399, 1])
            233118 Mat([1439, 1])
            236587 Mat([18199, 1])
            244729 [47, 1; 127, 1]
            247126 [47, 1; 239, 1]
            278062 Mat([3391, 1])
            302122 Mat([5209, 1])
            314739 Mat([11657, 1])
            323297 Mat([1913, 1])
            324206 Mat([3449, 1])
            355327 Mat([2207, 1])
            367372 Mat([3167, 1])
            380351 Mat([719, 1])
            382016 [47, 1; 127, 1]
            387643 Mat([13367, 1])
            393213 Mat([131071, 1])
            394012 Mat([719, 1])
            400377 Mat([3607, 1])
            401590 Mat([5737, 1])
            406831 Mat([1583, 1])
            416783 Mat([18121, 1])
            429493 Mat([1399, 1])
            431079 Mat([13063, 1])
            452335 Mat([6959, 1])
            459699 Mat([4943, 1])
            463601 Mat([5209, 1])
            488304 Mat([3391, 1])
            510598 Mat([23209, 1])
            525518 Mat([37537, 1])
            532048 Mat([3023, 1])
            539036 Mat([7927, 1])
            548408 Mat([1399, 1])
            550773 Mat([20399, 1])
            555051 Mat([26431, 1])
            575577 Mat([2063, 1])
            578993 [47, 1; 127, 1]
            591117 Mat([1913, 1])
            638472 Mat([719, 1])
            652133 Mat([719, 1])
            661245 Mat([3391, 1])
            666752 Mat([5209, 1])
            698119 [127, 1; 239, 1]
            699325 Mat([2543, 1])
            708451 Mat([13367, 1])
            716280 [47, 1; 127, 1]
            721649 Mat([23279, 1])
            748547 Mat([20231, 1])
            755460 Mat([1399, 1])
            780504 Mat([1913, 1])
            801523 Mat([1439, 1])
            818515 [127, 1; 1289, 1]
            828231 Mat([5209, 1])
            845322 Mat([1583, 1])
            871487 Mat([3391, 1])
            874375 Mat([1399, 1])
            896593 Mat([719, 1])
            910254 Mat([719, 1])
            915291 Mat([7823, 1])
            935690 Mat([13367, 1])
            948831 Mat([24329, 1])
            964458 Mat([4871, 1])
            969553 Mat([5737, 1])
            time = 10,649 ms.

            What do we conclude from this:

            1) Post not requests for proofs of simply-falsifiable things to multiple
            mailing lists, lest thee bring upon thyself a gargantuan public shaming in
            so-doing.

            2) Use Pari/GP to avoid (1)

            3) Other stuff, dunno what. Joshua - do you want to take over from here?

            Phil

            () ASCII ribbon campaign () Hopeless ribbon campaign
            /\ against HTML mail /\ against gratuitous bloodshed

            [stolen with permission from Daniel B. Cristofani]

            __________________________________________________________
            Need a quick answer? Get one in minutes from people who know.
            Ask your question on www.Answers.yahoo.com





            ---------------------------------

            LLama Gratis a cualquier PC del Mundo.
            Llamadas a fijos y móviles desde 1 céntimo por minuto.
            http://es.voice.yahoo.com

            [Non-text portions of this message have been removed]
          • Joshua Zucker
            ... What is the interest? That is, why all the 2s in 2^(2n^2)-2? Why not -1? Or just n as the exponent? Or just n^2? Or something else? Did this
            Message 5 of 6 , Jan 28, 2007
            • 0 Attachment
              On 1/28/07, Sebastian Martin <sebi_sebi@...> wrote:
              > I am sorry to have committed this mistake.
              > I promise to check better the results.
              > But I verified it for several chains of 200 numbers and only 1 and 2 were going out.
              > Nevertheless I believe that this has interest.

              What is the interest? That is, why all the 2s in 2^(2n^2)-2? Why not
              -1? Or just n as the exponent? Or just n^2? Or something else? Did
              this relationship come up in investigating some other idea, or was it
              just an arbitrary pick?

              Also, to fill in more of what I think is the most interesting part of
              the investigation, namely which primes p appear in the gcd here, we
              have Max (Thanks Max!)

              --Joshua Zucker

              from: Max Alekseyev
              Odd prime p can divide gcd(n, 2^(2n^2)-2) if and only if the
              multiplicative order of 2 modulo p is odd and 2 is a square modulo
              this order.
              The following simple PARI script gives a list of all such primes below 10^4:

              forprime(p=3,10^4, q=znorder(Mod(2,p)); if( (q%2) &&
              issquare(Mod(2,q)), print1(p,", ")) )

              47, 127, 239, 383, 439, 479, 719, 863, 1289, 1399, 1439, 1487, 1583,
              1823, 1913, 2063, 2207, 2351, 2447, 2543, 2687, 2879, 3023, 3119,
              3167, 3359, 3391, 3449, 3463, 3607, 4079, 4127, 4463, 4513, 4567,
              4703, 4799, 4871, 4943, 5087, 5209, 5519, 5737, 5807, 6047, 6089,
              6287, 6719, 6791, 6857, 6863, 6959, 7247, 7583, 7727, 7823, 7927,
              8167, 8447, 8543, 8783, 9431, 9743, 9839, 9887

              I will give an example of n such that 719 divides gcd(n, 2^(2n^2)-2).

              The multiplicative order of 2 modulo 719 is 359. Therefore, 719
              divides gcd(n, 2^(2n^2)-2) if and only if
              n = 0 (mod 719)
              2n^2 - 1 = 0 (mod 359) ==> n = +- 170 (mod 359)
              This system of congruences have a solution
              n = 122230 or 135891 (mod 258121)

              In particular, for n=122230 we have gcd(n, 2^(2n^2)-2)=1438 which is a
              multiple of 719 (as expected).

              Max
            Your message has been successfully submitted and would be delivered to recipients shortly.