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

Re: [PrimeNumbers] GCD result

Expand Messages
  • 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 1 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 2 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.