Lucas-Lehmer Primality Test

A Mersenne number, M_n is a number of the form 2ⁿ - 1. If the exponent n is prime, there is a chance that M_n is prime.

Let L_n be defined recursively by L₀ = 4 and L_n+1 = L_n² - 2.

[Lucas-Lehmer, 1930] The following two statements are equivalent for Mersenne numbers:

1. M_p = 2^p - 1 is prime
2. M_p divides L_p-1.

Many steps in the proof rely on facts about congruence, finite fields and finite groups. Standard facts of number theory will be assumed in this page. I hope to add additional pages to show proofs or development of these "standard facts" because they are standard only to folks who have had a fair amount of abstract algebra or number theory. Also, this proof is simply "my" proof written for my personal satisfaction. There may well be one or more better proofs in the literature. If you know of one, please feel free to inform me of it (as well as of any errors you may find in this proof!) and if you have a URL, I hope you can share that as well.

Standard Facts. (This collection of definitions and theorems may be expanded depending on feedback.)

Part 1. [(1) implies (2)] If M_p divides L_p-1, then M_p is prime.

Let v = 2 + 3^1/2 and u = 2 -  3^1/2. Then u+v = 4 = L₀ and uv = 1.

An inductive argument shows: L_n = u ^t(n-1) + v ^t(n-1) with t(s) = 2^s. t(s) has the obvious properties t(0) = 1 and t(s+1) = 2 t(s).

(Note: this exponential function is introduced only because HTML does not seem to like superscripts on superscripts.  Also, 3^1/2 is used for the square root of 3 because there does not appear to be a square root symbol which displays properly. ) 

Since T(0) = 1, and L₀ = u ^t(0) + v ^t(0), we have the start of the argument. Assume the formula works for L_n.

Then L_n² - 2 = [u ^t(n-1) + v ^t(n-1) ]² - 2 = u ^{2 t(n-1)} + v ^{2 t(n-1)} + 2 u ^t(n-1) v ^t(n-1) - 2 = u ^t(n) + v ^t(n) = L_n+1 as required.

Now suppose that L_p-1 is divisible by Q = M_p = 2^p - 1 but Q is not prime.

We will show a contradiction which shows that "Q not prime" is false so Q is prime.

Let r be prime dividing Q with r < Q^1/2. Then L_p-1 is divisible by r.

We now pass to working modulo r and view all of the work in the field of (Z/rZ)(3^1/2) or F_r(3^1/2) which contains F_r.

This last inclusion is an equality if 3 is a square mod r. The size of this field is either r or r² and non-zero elements have an size one less. That is, if x is non-zero in the field then there is a smallest positive number d with x^d = 1. The number d is called the order of x and must divide r-1 or r² -1 (since r-1 divides r² -1 we can ignore r-1 and not worry about whether 3 is a square or not).

L_p-1 is divisible by r, so mod r, L_p-1 = 0. That is, L_p-1 = u ^t(p-2) + v ^t(p-2) = u ^t(p-2) ( 1 + v ^{2 t(p-2)} ) = 0.

Now, u is not 0. (Otherwise, we would have 3 = 4 mod r which is impossible unless r = 1.)

Thus 0 = 1 + v ^{2 t(p-2)} = 1 + v^t(p-1) and v^t(p-1) = -1. Squaring, v^t(p) = 1 and the order of v must divide t(p). Now, t(p) is a power of two so any number less than t(p) that divides t(p) will also divide t(p-1). If the order of v is less than t(p), then we would have v^t(p-1) = 1 and not -1. Thus, the order of v is t(p).

Now, t(p) = 2^p = Q + 1 and t(p) divides r² -1. We now have the inequalities:

Q+1 = t(p) = 2^p < r² -1 < Q - 1 since r < Q^1/2 from the start. This gives us the needed contradiction.

Part 2. [(2) implies (1)] If M_p is prime, then M_p divides L_p-1.

Again using Q = M_p = 2^p - 1 and other notation from Part 1, we must show v^t(p-1) = -1 mod Q.

This will establish that L_p-1 = u ^t(p-2) + v ^t(p-2) = u ^t(p-2) ( 1 + v ^{2 t(p-2)} ) = 0 mod Q.

There are several components to this part of the proof. In F_Q. or the usual integers mod Q:

1. -1 is not a square mod Q.
2. 2 is a square and a fourth power mod Q.
3. 3 is not a square mod Q

This last means that F_Q (3^1/2) has Q² elements of the form a + b 3^1/2 with a and b in F_Q.

In this characterization, 3^1/2 is taken as either one of the roots of the equation x² = 3 over F_Q.

We could use some other symbol, of course, but there seem to be enough symbols already.

The real numbers v and u have images in F_Q (3^1/2) given by 2+ 3^1/2 and 2- 3^1/2. These images also satisfy u+v=4 and uv=1.

We then have v^Q = 2^Q +(3^1/2)^Q = 2 + 3^(Q-1)/2 3^1/2.

Now 3 is not a square mod Q and (3^(Q-1)/2)² = 3^(Q-1) = 1, so we must have 3^(Q-1)/2 = -1.

Thus, v^Q = 2 + 3^(Q-1)/2 3^1/2 = 2 - 3^1/2 = u. Also, v^Q+1 = uv = 1.

Examining the orders of elements in F_Q (3^1/2), we see that the order divides Q² - 1 = (Q-1)(Q+1) = [(Q-1)/2] 2^p+1.

Note that (Q-1)/2 is odd and the order of v is a power of 2 dividing Q+1.

We can exhibit an element of F_Q (3^1/2) which is a square root of v but has no square root itself.

This will give us an element of the field with order 2(Q+1) and show that v has order Q+1.

This in turn means that v^(Q+1)/2 = v^t(p-1) = -1 which will complete this part of the proof.  The details supporting this outline follow.

The non-zero elements of F_Q form a cyclic group of order Q-1. (This is one of those standard facts from number theory.)

That is, there are numbers g such that powers of g from 0 to Q-2 cover all of the non-zero elements of F_Q.

For example, mod 31 there are 8 choices for a generator: 3, 11, 12, 13, 17, 21, 22, 24.

We need some information about squares and non-squares mod Q (or really mod any prime). We will use some properties related to the "Law of Quadratic Reciprocity," but we do not need the full theorem and we can develop what we need.

A non-zero element, a, of F_Q is a square if there is an element x in F_Q with x² = a.

Since 2 divides Q-1, we can simply look at a^(Q-1)/2 which is +1 if a is a square or -1 if a is not a square.

Also, given a and b non-zero in F_Q, we see that (ab)^(Q-1)/2 = a^(Q-1)/2 b^(Q-1)/2 so we have several useful properties of squares immediately to hand: the product of any two non-squares is a square and the product of any square and a non-square is a non-square.

Notice that Q-1 is divisible by 2 but not 4. This means that (Q-1)/2 is odd and (-1)^(Q-1)/2 = -1 or -1 is not a square.

From the "Little Fermat" Theorem, 2^Q = 2, so 2^Q+1 = 4 and Q+1 is a power of 2 (in fact, at least 8 = 7 + 1).

Then, 2^1/2 = 2^(Q+1)/4 and 2^1/4 = 2^(Q+1)/8.

Note that one of the three integers Q-1, Q and Q+1 must be divisible by 3. Q is prime and Q+1 is a power of 2, so 3 must divide Q-1. Let g be a generator of the group of non-zero elements of F_Q under multiplication. This group is cyclic and has Q-1 elements. Let g be a generator, then w = g^(Q-1)/3 is a non-trivial cube root of 1. That is, there is an integer w which satisfies (mod Q, of course) w³ - 1 = 0 or w² + w + 1 = 0.

For example, mod 31, the non-trivial cube roots of 1 are 5 and 25 (or -6).

Consider z = w - w². This z (an integer mod Q) has a remarkable square:

z² = ( w - w² )² = w² - 2w³ + w⁴ = w² - 2 + w = -3 because w² + w = -1. This calculation is the simplest case of one approach to proving the general law of Quadratic Reciprocity.

Thus -3 is a square and -1 is not a square, so 3 is not a square because 3 = (-1)(-1) 3 = (-1)(-3).

Work in F_Q(3^1/2) or numbers of the form a+b 3^1/2, viewed mod Q

In any field of prime characteristic Q, we have (x+y) ^Q = x ^Q + y ^Q. This follows from the Binomial theorem and the fact that the binomial coefficients (other than 0 and Q terms) are all divisible by Q.

v = 2 + 3^1/2 has a square root but no 4^th root:

Now that we have 3 is not a square mod Q, we know that 3^(Q-1)/2 = -1. This gives us v^Q = 2 + 3^(Q-1)/2 3^1/2 = 2 - 3^1/2 = u.

Also, v has a fairly simple square root. The process of determining that v has no 4^th root is quite similar to finding the square root, so we will just observe that (1+ 3^1/2 )/ 2^1/2 is a square root of v. By 1/ 2^1/2 we mean any square root of 1/2. One such is 1/2^(Q+1)/4 = 2 ^{Q-1 - (Q+1)/4}. Since 2 also has a 4^th root, so does 1/2 and v has a 4^th root if (1+ 3^1/2 ) is a square.

If (1+ 3^1/2) is a square, there must be integers a and b with (a+b 3^1/2) ² = 1+ 3^1/2.

Expanding, (a+b 3^1/2) ² = a ² + 3b² + 2`ab 3^1/2 = 1 + 3^1/2. From this, a ² + 3b² = 1 and 2ab = 1.

It is enough now to notice that 2ab = a ² + 3b². Rearranging, we have 0 = a ² - 2ab + 3b² = (a-b) ² + 2b².

Solving for -2, we have -2 = (a-b)² /b² = [(a -b)/b]². In order to find a and b, -2 must be a square. However, 2 is a square and -1 is not a square so -2 is not a square and there are no such a and b. Thus we have no 4^th root for v.