gcd(n,2^(2n^2)-2) is usually 1 or 2

[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

First six of them (and some others) you have already met. 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

On 1/27/07, Joshua Zucker <joshua.zucker at gmail.com> wrote:
> Hi folks,
> Someone on another mailing list (I don't know why) asked about a proof
> that gcd(n, 2^(2n^2)-2) = 1 for n odd, 2 for n even.
>
> But of course it's not true, though the exceptions are pretty rare,
> and at least the small exceptions all involve a factor of either 47 or
> 127, which seems interesting.
>
> But I don't know enough number theory to say whether this sequence (of
> exceptions to the 1 or 2 pattern) is interesting or not.
>
> Can someone help me decide whether this is worth submitting or not?
>
> n such that gcd(n, 2^(2n^2 - 2)) is greater than 2:
> 254 423 635 658 1143 1504 1524 1739 2032 2413 2585 2820 2921 3302 3666
> 3810 3901 4191 4699 4747 4982 5080 5588 5828 5969 6063 6477 6858 6909
> 7024 7144 7366 7747 7990 8225 8255 8636 8843 9071 9144 9306 9525
>
> and the corresponding gcds:
> 254 47 127 94 127 94 254 47 254 127 47 94 127 254 94 254 47 127 127 47
> 94 254 254 94 127 47 127 254 47 878 94 254 127 94 47 127 254 239 47
> 254 94 127
>
> Hm, that 878 and 239 seem to be interlopers in a crowd full of 47s and 127s.
>
> What's special about the primes that appear in these GCDs?  Up to n =
> 100000, all we get are the obvious 2, and then a lot of  47 and 127
> (about 410 of them), and also a few others (about 35) built from these
> primes:
> 439 239 1289 383 479 2351 3463 1487 11447 863 4513 2687
>
> and most of those small ones occur several times -- it sure doesn't
> look "random".
>
> Maybe there is something interesting here after all?
>
> --Joshua Zucker
>