Mersenne prime

A Mersenne number, commonly denoted M_p, is 2^p-1 (in Common LISP notation: (1- (expt 2 p))). Not all Mersenne numbers are prime, for example M₁₁ = 2047 = 23 * 89, and M₈ = 255 = 3 * 5 * 17. It's easy to show that M_n cannot be prime for nonprime n; let k|n, then M_k|M_n... which actually means that M₁ divides all M_n. But that's okay since M₁ = 1.

The largest-known primes have been Mersenne primes in recent years simply because the tests for them involve the least amount of calculations when compared with other forms of primes (e.g., Fermat numbers, generalized Fermat numbers, random primes). In fact, the upper bound on the number of atomic calculations required to prove that a given Mersenne number is prime is equivalent to p-2 (for Mersenne number M_p). This is true due to the Lucas-Lehmer test:

Theorem

Given: S(1)=4 and S(n+1) = S(n)²-2 and a prime p, M_p divides S(p-1) iff M_p is prime. (See http://www.utm.edu/research/primes/notes/proofs/LucasLehmer.html for part of the proof and more info.)

So calculating S(p-1) involves p-2 "atomic" calculations: "square and subtract 2". Unfortunately, when p = 30402457 or so, M_p has upwards of nine million decimal digits. Calculating whether M_p divides S(p-1) requires weeks to months of computer time for the average computer. Calculating whether M_p divides S(p-1) for each of the primes in this range is then quite a daunting task. But there is a slight simplification that can be made for finding "probable" Mersenne primes:

-3 = ₃2^p-1 (mod M_p).

My 'simplification' proof

Following the proof laid out on the prime pages site, let w = 2+sqrt(3) and v = 2-sqrt(3). Note that w+v = 4 and w*v = 1. Now S(1) = w+v,
S(2) = w²+2wv+v²-2 = w²+v²,
S(3) = w⁴+2(wv)²+v⁴-2 = w⁴+v⁴,
and so on, until we get
S(n) = _w2^n-1 + _v2^n-1.
(Use induction to show this property.) For sanity's sake, let y = 2^p-2 for a given prime p. Then S(p-1) = w^y+v^y. Now, M_p divides S(p-1) iff there exists an x in the positive integers such that x*M_p = S(p-1). Suppose such an x exists. Then
(1) x*M_p = w^y+v^y.
Further,
(x*M_p)² = w^2*y+2(wv)^y+v^2*y,
or
(x*M_p)²-2 = w^2*y+v^2*y.
Squaring again, we get
(2) ((x*M_p)²-2)² = w^4*y+2+v^4*y.

Now it is worth noting that 4*y = 2^p = 2 (mod p) (by Fermat's little theorem). Let h be a positive integer such that h*p+2 = 2^p.

Modding both sides of (2) by M_p yields
(3) 4 = w^4*y+2+v^4*y (mod M_p)
(note that this works because S(n) is always an integer, even though w and v are not integers).

Now we have to expand w^4*y+v^4*y. Fortunately, every other term of v is negative while all the terms of w are positive. Also fortunately, all the odd powers of sqrt(3) have this sign disparity, so each of the terms with an odd power of sqrt(3) is cancelled out. Further, all but two of the remaining terms are divisible by M_p (using the binomial expansion of (a+b)ⁿ where n = 2^p), so (3) can be further pared down to
2 = 2^4*y+1+2*3^2*y (mod M_p)
or
1 = 2^h*p+2+3^2*y (mod M_p).
(Caution: the first of those last two steps only works when M_p is prime.)

Use the fact that x+1 = 1 (mod x), for instance x = M_p, to get
1 = 4+3^2*y (mod M_p).
At last, we have the 'simplification':
(4) -3 = 3^2*y = ₃2^p-1 (mod M_p).

I realize that several steps have been glossed over. This is mostly due to difficulties with representing the numbers and powers in a sensible way in HTML. So you'll either have to believe me or go through the steps yourself to verify this property of Mersenne primes. Notice that the condition given in (4) is merely necessary for a given Mersenne number to be prime. It is not yet known whether it is sufficient.

In tandem with this, there are other ways to show that the above holds. There is Legendre symbols and Gauss' quadratic reciprocity law, which, when combined with (4), shows that 3 is a quadratic non-residue mod M_p. Conversely, M_p prime implies that 3 is a quadratic non-residue which can in turn be used to imply (4). Also, there is an 'Euler pseudoprime test' which can be used to determine whether a given number is probably prime; again, the use of quadratic (non-)residues is required, but the end result is another form of (4).

I suppose it would help to have a current listing of the known Mersenne primes... the page at http://primes.utm.edu/mersenne/ is pretty up-to-date, but it is (sometimes) missing the most-recently-discovered Mersenne prime as found on the page at http://www.mersenne.org/prime.htm.