# Mersenne: Penultimate Lucas-Lehmer step

```     Let p > 2 be prime and  Mp = 2^p - 1.
The familiar Lucas-Lehmer test sets a = 4
and a[j+1] = a[j]^2 - 2 for j >= 0.
Mp is prime if and only if a[p-1] == 0 mod Mp.```
```
When Mp is prime, then

a[p-2]^2 == 2 == 2*Mp + 2 = 2^(p+1)  (mod Mp).

Taking square roots, either

a[p-2] ==  2^((p+1)/2) mod Mp
or
a[p-2] == -2^((p+1)/2) mod Mp.

Around 20 years ago I heard that nobody could predict
which of these would occur.  For example,

p = 3    a = 4 == 2^2 (mod 7)
p = 5    a = 194 == 2^3 (mod 31)
p = 7    a = 1416317954 == -2^4 (mod 127).

Now that 40 Mersenne primes are known, can anyone
extend this table further?  That will let us test
heuristics, such as whether both  +- 2^((p+1)/2)
seem to occur 50% of the time, and
provide data to support or disprove conjectures.

Peter Montgomery

_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ      -- http://www.tasam.com/~lrwiman/FAQ-mers
```