A Mersenne number, commonly denoted Mp, is 2p-1 (in Common LISP notation: (1- (expt 2 p))). Not all Mersenne numbers are prime, for example M11 = 2047 = 23 * 89, and M8 = 255 = 3 * 5 * 17. It's easy to show that Mn cannot be prime for nonprime n; let k|n, then Mk|Mn... which actually means that M1 divides all Mn. But that's okay since M1 = 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 Mp). This is true due to the Lucas-Lehmer test:


Given: S(1)=4 and S(n+1) = S(n)2-2 and a prime p, Mp divides S(p-1) iff Mp 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, Mp has upwards of nine million decimal digits. Calculating whether Mp divides S(p-1) requires weeks to months of computer time for the average computer. Calculating whether Mp 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 = 32p-1 (mod Mp).

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) = w2+2wv+v2-2 = w2+v2,
S(3) = w4+2(wv)2+v4-2 = w4+v4,
and so on, until we get
S(n) = w2n-1 + v2n-1.
(Use induction to show this property.) For sanity's sake, let y = 2p-2 for a given prime p. Then S(p-1) = wy+vy. Now, Mp divides S(p-1) iff there exists an x in the positive integers such that x*Mp = S(p-1). Suppose such an x exists. Then
(1) x*Mp = wy+vy.
(x*Mp)2 = w2*y+2(wv)y+v2*y,
(x*Mp)2-2 = w2*y+v2*y.
Squaring again, we get
(2) ((x*Mp)2-2)2 = w4*y+2+v4*y.

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

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

Now we have to expand w4*y+v4*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 Mp (using the binomial expansion of (a+b)n where n = 2p), so (3) can be further pared down to
2 = 24*y+1+2*32*y (mod Mp)
1 = 2h*p+2+32*y (mod Mp).
(Caution: the first of those last two steps only works when Mp is prime.)

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

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 Mp. Conversely, Mp 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.

Log in or register to write something here or to contact authors.