Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] GCD result

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