# Re: Mersenne: Possible refinement of screening for Mersenne primes

Alexander Kruppa wrote:
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
```