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

Re: [PrimeNumbers] GCD result

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