Brian J. Beesley wrote:> [...]
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):
If p>3 and odd, 2^((p+1)/2) + 2 (mod 2^p-1) is always a QR.
That is rubbish. I was misusing the Kroecker symbol and the conclusion is wrong. (The fact that your list contained several counterexamples should have been a strong hint!)
What my argument shows is that the number of prime factors of Mp for which [+-]2^((p+1)/2) + 2 are QNR is always even. But that doesn't tell us whether they are QR (mod Mp) or not, i.e. whether they are QR modulo *every* prime factor, unless of course Mp is prime and both must be QR modulo the only prime "factor" there is.
Since (2^((p+1)/2) + 2) * (-2^((p+1)/2) + 2) == -2^(p+1) + 4 == -2 + 4 == 2 (mod f) for any f|Mp, and 2 is a QR (mod f), [+-]2^((p+1)/2) + 2 must be either both be QR or QNR. So it suffices to check only one.
To determine whether or not they are QR (mod Mp) via quadratic reciprocity would require knowing the prime factorization of Mp - and knowing even one nontrivial factor would of course settle the question of primality as well.
One could use Euler's criterion as a check: if q is prime and gcd(r,q)==1, r^((q-1)/2) == 1 (mod q) if r is a QR, and == -1 otherwise. If q is not prime, the result will usually be neither 1 or -1. We already know that 2^((p+1)/2) + 2 is a QR if Mp is prime, so this check will really just be a Fermat-style probable prime test which takes just as long as a LL test, but doesn't prove primality.
I've made a list of Mp, p<200, that are not Mersenne primes, and the Kronecker symbol (or Legendre, actually) of 2^((p+1)/2) + 2 (mod f) for each prime factor f of Mp. It shows that knowing whether [+-]2^((p+1)/2) + 2 is a QR would really eliminate a lot of candidates - M_23, M_37, M_47, M_59, M_101, M_137, M_139, M_149, M_167, M_181, M_193, M_197, M199 would survive the test, while M_11, M_29, M_41, M_43, M_53, M_67, M_71, M_73, M_79, M_83, M_97, M_103, M_109, M_113, M_131, M_151, M_157, M_163, M_173, M_179, M_191 could be indentifed as composite.
Your question (2) remains open - is there a faster way to determine whether 2^((p+1)/2) + 2 is a QR (mod Mp) than running a LL test?
When a composite Mp is completely factored, it is very easy to determine whether 2^((p+1)/2) + 2 is a QR. With enough composite Mp completely factored, maybe some kind of pattern can be discovered in the exponents p for which it is or isn't a QR?
Alex
M_11: ( 2^6+2 | 23 ) = -1 M_11: ( 2^6+2 | 89 ) = -1
M_23: ( 2^12+2 | 47 ) = 1 M_23: ( 2^12+2 | 178481 ) = 1
M_29: ( 2^15+2 | 233 ) = -1 M_29: ( 2^15+2 | 1103 ) = 1 M_29: ( 2^15+2 | 2089 ) = -1
M_37: ( 2^19+2 | 223 ) = 1 M_37: ( 2^19+2 | 616318177 ) = 1
M_41: ( 2^21+2 | 13367 ) = -1 M_41: ( 2^21+2 | 164511353 ) = -1
M_43: ( 2^22+2 | 431 ) = 1 M_43: ( 2^22+2 | 9719 ) = -1 M_43: ( 2^22+2 | 2099863 ) = -1
M_47: ( 2^24+2 | 2351 ) = 1 M_47: ( 2^24+2 | 4513 ) = 1 M_47: ( 2^24+2 | 13264529 ) = 1
M_53: ( 2^27+2 | 6361 ) = -1 M_53: ( 2^27+2 | 69431 ) = -1 M_53: ( 2^27+2 | 20394401 ) = 1
M_59: ( 2^30+2 | 179951 ) = 1 M_59: ( 2^30+2 | 3203431780337 ) = 1
M_67: ( 2^34+2 | 193707721 ) = -1 M_67: ( 2^34+2 | 761838257287 ) = -1
M_71: ( 2^36+2 | 228479 ) = 1 M_71: ( 2^36+2 | 48544121 ) = -1 M_71: ( 2^36+2 | 212885833 ) = -1
M_73: ( 2^37+2 | 439 ) = -1 M_73: ( 2^37+2 | 2298041 ) = -1 M_73: ( 2^37+2 | 9361973132609 ) = 1
M_79: ( 2^40+2 | 2687 ) = 1 M_79: ( 2^40+2 | 202029703 ) = -1 M_79: ( 2^40+2 | 1113491139767 ) = -1
M_83: ( 2^42+2 | 167 ) = -1 M_83: ( 2^42+2 | 57912614113275649087721 ) = -1
M_97: ( 2^49+2 | 11447 ) = -1 M_97: ( 2^49+2 | 13842607235828485645766393 ) = -1
M_101: ( 2^51+2 | 7432339208719 ) = 1 M_101: ( 2^51+2 | 341117531003194129 ) = 1
M_103: ( 2^52+2 | 2550183799 ) = -1 M_103: ( 2^52+2 | 3976656429941438590393 ) = -1
M_109: ( 2^55+2 | 745988807 ) = -1 M_109: ( 2^55+2 | 870035986098720987332873 ) = -1
M_113: ( 2^57+2 | 3391 ) = 1 M_113: ( 2^57+2 | 23279 ) = 1 M_113: ( 2^57+2 | 65993 ) = -1 M_113: ( 2^57+2 | 1868569 ) = -1 M_113: ( 2^57+2 | 1066818132868207 ) = 1
M_131: ( 2^66+2 | 263 ) = -1 M_131: ( 2^66+2 | 10350794431055162386718619237468234569 ) = -1
M_137: ( 2^69+2 | 32032215596496435569 ) = 1 M_137: ( 2^69+2 | 5439042183600204290159 ) = 1
M_139: ( 2^70+2 | 5625767248687 ) = 1 M_139: ( 2^70+2 | 123876132205208335762278423601 ) = 1
M_149: ( 2^75+2 | 86656268566282183151 ) = 1 M_149: ( 2^75+2 | 8235109336690846723986161 ) = 1
M_151: ( 2^76+2 | 18121 ) = -1 M_151: ( 2^76+2 | 55871 ) = 1 M_151: ( 2^76+2 | 165799 ) = -1 M_151: ( 2^76+2 | 2332951 ) = -1 M_151: ( 2^76+2 | 7289088383388253664437433 ) = -1
M_157: ( 2^79+2 | 852133201 ) = 1 M_157: ( 2^79+2 | 60726444167 ) = -1 M_157: ( 2^79+2 | 1654058017289 ) = -1 M_157: ( 2^79+2 | 2134387368610417 ) = 1
M_163: ( 2^82+2 | 150287 ) = 1 M_163: ( 2^82+2 | 704161 ) = 1 M_163: ( 2^82+2 | 110211473 ) = 1 M_163: ( 2^82+2 | 27669118297 ) = -1 M_163: ( 2^82+2 | 36230454570129675721 ) = -1
M_167: ( 2^84+2 | 2349023 ) = 1 M_167: ( 2^84+2 | 79638304766856507377778616296087448490695649 ) = 1
M_173: ( 2^87+2 | 730753 ) = 1 M_173: ( 2^87+2 | 1505447 ) = -1 M_173: ( 2^87+2 | 70084436712553223 ) = -1 M_173: ( 2^87+2 | 155285743288572277679887 ) = 1
M_179: ( 2^90+2 | 359 ) = -1 M_179: ( 2^90+2 | 1433 ) = -1 M_179: ( 2^90+2 | 1489459109360039866456940197095433721664951999121 ) = 1
M_181: ( 2^91+2 | 43441 ) = 1 M_181: ( 2^91+2 | 1164193 ) = 1 M_181: ( 2^91+2 | 7648337 ) = 1 M_181: ( 2^91+2 | 7923871097285295625344647665764672671 ) = 1
M_191: ( 2^96+2 | 383 ) = 1 M_191: ( 2^96+2 | 7068569257 ) = -1 M_191: ( 2^96+2 | 39940132241 ) = 1 M_191: ( 2^96+2 | 332584516519201 ) = 1 M_191: ( 2^96+2 | 87274497124602996457 ) = -1
M_193: ( 2^97+2 | 13821503 ) = 1 M_193: ( 2^97+2 | 61654440233248340616559 ) = 1 M_193: ( 2^97+2 | 14732265321145317331353282383 ) = 1
M_197: ( 2^99+2 | 7487 ) = 1 M_197: ( 2^99+2 | 26828803997912886929710867041891989490486893845712448833 ) = 1
M_199: ( 2^100+2 | 164504919713 ) = 1 M_199: ( 2^100+2 | 4884164093883941177660049098586324302977543600799 ) = 1
_________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
