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_{11} = 2047 = 23 * 89, and M_{8} = 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_{1} divides all M_{n}. But that's okay since M_{1} = 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:

Given: S(1)=4 and S(n+1) = S(n)^{2}-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 = `_{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^{2}+2wv+v^{2}-2 = w^{2}+v^{2},

S(3) = w^{4}+2(wv)^{2}+v^{4}-2 = w^{4}+v^{4},

and so on, until we get

S(n) = _{w}2^{n-1} + _{v}2^{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})^{2} = w^{2*y}+2(wv)^{y}+v^{2*y},

or

(x*M_{p})^{2}-2 = w^{2*y}+v^{2*y}.

Squaring again, we get

(2) ((x*M_{p})^{2}-2)^{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)^{n} 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} = _{3}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__.