Hi,
(1) Could someone with the required background please tidy up my logic and prove that the assertion above is true i.e. there is no prime 2^p-1 with p > 3 such that there are solutions to x^2 mod 2^p-1 = 2^((p+1)/2) + 2
I believe the idea is correct, but it doesn't remove candidates.
Lets try (going out on a limb here, fingers crossed):
Is 2^((p+1)/2) + 2 (mod 2^p-1) a QR?
We can rewrite as 2*(2^((p-1)/2) + 1) (mod 2^p-1) and that is a QR iff 2^((p-1)/2) + 1 (mod 2^p-1) is, as 2 is a QR and quadratic character is multiplicative.
( 2^((p-1)/2) + 1 ) (-----------------) (Kronecker symbol) ( 2^p-1 )
( (2^p-1) % 2^((p-1)/2) + 1 ) = (---------------------------) ( 2^((p-1)/2) + 1 )
because 2^((p-1)/2) + 1 == 1 (mod 4) if p>3 and odd, and
(2^p-1)-1 = 2*(2^(p-1)-1) = 2*(2^((p-1)/2)-1)(2^((p-1)/2)+1), therefore 2^((p-1)/2) + 1 | (2^p-1)-1, (2^p-1)-1 == 0 (mod 2^((p-1)/2) + 1) and thus 2^p-1 == 1 (mod 2^((p-1)/2) + 1).
It follows
( 1 ) = (-----------------) = 1 ( 2^((p-1)/2) + 1 )
If p>3 and odd, 2^((p+1)/2) + 2 (mod 2^p-1) is always a QR.
For the other sqrt(2), -2^((p+1)/2), the question is:
Is -2^((p+1)/2) + 2 a QR?
We can reqrite as (-1)*(2)*(2^((p-1)/2) - 1), since 2^p-1 == 3 (mod 4), -1 is a QNR and so
( -2^((p+1)/2) + 2 ) ( 2^((p-1)/2) - 1 ) (------------------) = - (-----------------) ( 2^p-1 ) ( 2^p-1 )
Since both 2^((p-1)/2) - 1 and 2^p-1 are == 3 (mod 4) for odd p>3, quadratic reciprocity introduces another sign change, thus
( (2^p-1) % 2^((p-1)/2) - 1 ) = (---------------------------) ( 2^((p-1)/2) - 1 )
2^((p-1)/2) - 1 | (2^p-1)-1 as seen before, so
( 1 ) = (-----------------) = 1 ( 2^((p-1)/2) - 1 )
If p>3 and odd, -2^((p+1)/2) + 2 (mod 2^p-1) is always a QR.
Is there a better (or if applicable, correct) proof? Can, for example, sqrt([+/-]2^((p+1)/2) + 2) in Z/Z(2^p-1) be given explicitly, like sqrt(2) can?
Alex
_________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
