Proof for the Lucas-Lehmer Primality Test

The Lucas-Lehmer primality test states that for the recursive sequence s₀ = 4 and s_n = s_n-1² – 2, and for all p > 2, s_p-2 is divisible by 2^p – 1 if and only if 2^p – 1 is a prime number.  (The following is loosely based on the proof found here with some improvements.)

Definitions

s₀ = 4

Let a = ½s₀ = ½(4) = 2

Let b = a² – 1 = 2² – 1 = 3

Let u = a + √b

Let ū = a – √b

Then uū = (a + √b)(a – √b) = a² – b = a² – (a² – 1) = a² – a² + 1 = 1

Then s_n = u^{2^n} + ū^{2^n} by induction:

s₀ = u^{2^0} + ū^{2^0} = u¹ + ū¹ = u + ū = a + √b + a – √b = 2a = 2(½s₀) = s₀

Assuming s_n = u^{2^n} + ū^{2^n}:

s_n+1 = s_n² – 2

s_n+1 = (u^{2^n} + ū^{2^n})² – 2

s_n+1 = u^{2(2^n)} + 2u^{2^n}ū^{2^n} + ū^{2(2^n)} – 2

s_n+1 = u^{2^(n+1)} + 2(uū)^{2^n} + ū^{2^(n+1)} – 2

s_n+1 = u^{2^(n+1)} + 2(1)^{2^n} + ū^{2^(n+1)} – 2

s_n+1 = u^{2^(n+1)} + 2 + ū^{2^(n+1)} – 2

s_n+1 = u^{2^(n+1)} + ū^{2^(n+1)}

Proof of Sufficiency

Prove: If s_p-2 is divisible by 2^p – 1, then 2^p – 1 is a prime number.

Assume s_p-2 is divisible by 2^p – 1:

Let M = 2^p – 1

s_p–2 = kM

u^{2^(p-2)} + ū^{2^(p-2)} = kM

u^{2^(p-2)} = kM – ū^{2^(p-2)}

u^{2^(p-2)}u^{2^(p-2)} = kMu^{2^(p-2)} – ū^{2^(p-2)}u^{2^(p-2)}

(u^{2^(p-2)})² = kMu^{2^(p-2)} – (uū)^{2^(p-2)}

u^{2^(p-1)} = kMu^{2^(p-2)} – 1

Assume that 2^p – 1 is not a prime number:

Let q be the smallest factor of M = 2^p – 1

M ≡ 0 (mod q)

u^{2^(p-1)} ≡ k(0)u^{2^(p-2)} – 1 (mod q)

u^{2^(p-1)} ≡ -1 (mod q)

(u^{2^(p-1)})² ≡ (-1)² (mod q)

u^{2^p} ≡ 1 (mod q)

Since u^{2^(p-1)} ≠ 1, the order does not divide 2p – 1, so the order is 2^p

Let X = {n + m√b | n, m ε Z_q} and X* = {all elements of X except 0}

|X| = q² and |X*| = q² – 1 (as long as b = a² – 1 is not a perfect square)

u is in X*, and since the order of an element is at most the order of its size,

so 2^p ≤ q² – 1 < q²

Since q is the smallest factor of M, q² < M = 2^p – 1

But then 2^p < 2^p – 1 which is a contradiction

So 2^{p – 1} must be a prime number.

Proof of Necessity

Prove: If 2^p – 1 is a prime number, then s_p-2 is divisible by 2^p – 1.

Let M = 2^p – 1

Assume p is not a prime number

Then p has two factors m ≥ 2 and n ≥ 2 such that p = mn

But then 2^p – 1 = 2^mn – 1 which is divisible by 2^m – 1 and 2ⁿ – 1

This contradicts the assumption that 2^p – 1 is a prime number

So p must be a prime number

(-1)^(M-1)/2 ≡ -1 (mod M)

the exponent (M – 1)/2 = ½(2^p – 1 – 1) = ½(2^p – 2) = 2^p-1 – 1 must be odd

-1 to an odd exponent is -1

so (-1)^(M-1)/2 ≡ -1 (mod M)

2^(M-1)/2 ≡ 1 (mod M)

by Fermat’s Little Theorem, 2^p ≡ 2 (mod p), so 2^p – 2 = np

2^p – 2 must be even, and p (as a prime larger than 2) must be odd, so n = 2k and 2^p – 2 = 2kp

so the exponent (M – 1)/2 = ½(2^p – 1 – 1) = ½(2^p – 2) = kp

now 2^p ≡ 1 (mod 2^p – 1) or 2^p ≡ 1 (mod M)

so 2^(M-1)/2 = 2^kp = (2^p)^k ≡ 1^k (mod M) = 1 (mod M)

so 2^(M-1)/2 ≡ 1 (mod M)

3^(M-1)/2 ≡ -1 (mod M)

2²ⁿ⁺¹ – 1 ≡ 7 (mod 12) for all positive integers of n by induction:

2²⁽¹⁾⁺¹ – 1 = 2³ – 1 = 7 ≡ 7 (mod 12)

Assuming 2²ⁿ⁺¹ – 1 ≡ 7 (mod 12):

then 2²ⁿ⁺¹ ≡ 8 (mod 12)

2^{2(n + 1) +1} – 1 = 2^{2n + 3} – 1 = 2^{2n + 1 + 2} – 1 = 2^{2n + 1}2² – 1 ≡ 8(4) – 1 (mod 12) ≡ 7 (mod 12)

Since p is a prime larger than 2, p = 2n + 1 for all positive integers,

so M = 2^p – 1 = 2²ⁿ⁺¹ – 1 ≡ 7 (mod 12)

Since M ≡ 7 (mod 12), M = 12n + 7 for some integer n

By the law of quadratic reciprocity, (3 | 12n + 7)(12n + 7 | 3)

= (-1)^{½(3 – 1)½(12n + 7 – 1)} = (-1)^{6n + 3} = -1

Now, (12n + 7 | 3) = (3·4n + 3·2 + 1 | 3) ≡ (1 | 3) = 1

So (3 | 12n + 7) = -1

Or (3 | M) = -1, which means 3 is a quadratic nonresidue of M

So by Euler’s criterion, 3^(M-1)/2 ≡ -1 (mod M)

u^(M+1)/2 ≡ -1 (mod M)

u = a + √b = ^{(a + √b)2(a + 1)}/_{2(a + 1)} = ^{(a + 1 + √b)^2}/_{2(a + 1)}

because the numerator (a + √b)2(a + 1) = 2(a + 1)a + 2(a + 1)√b

= 2a² + 2a + 2(a + 1)√b = a² + a² + 2a + 1 – 1 + 2(a + 1)√b

= a² + 2a + 1 + 2(a + 1)√b + a² – 1 = (a + 1)² + 2(a + 1)√b + b = (a + 1 + √b)²

(recall that b = a² – 1)

so u^(M+1)/2 = [^{(a + 1 + √b)^2}/_{2(a + 1)}]^(M+1)/2 ≡ ^{2(a + 1)}/_{-2(a + 1)} (mod M) = -1 (mod M)

the numerator (a + 1 + √b)^2(M+1)/2 = (a + 1 + √b)^(M+1)

= (a + 1 + √b)(a + 1 + √b)^M ≡ -2(a + 1) (mod M)

using the binomial theorem in a finite field and prime exponent M,

(a + 1 + √b)^M ≡ (a + 1)^M + √b^M (mod M)

and using Fermat’s Little Theorem, (a + 1)^M ≡ a + 1 (mod M)

and √b^M = b^M/2 = b^{M/2 – ½ + ½} = b^{(M – 1)/2 + ½} = b^{(M – 1)/2}b^½ = (a² – 1)^{(M – 1)/2}b^½

= ((a – 1)(a + 1))^{(M – 1)/2}b^½ = (a – 1)^{(M – 1)/2}(a + 1)^{(M – 1)/2}b^½

since a = 2, (a – 1)^{(M – 1)/2} = (2 – 1)^{(M – 1)/2} = 1^{(M – 1)/2} ≡ 1 (mod M), and (a + 1)^{(M – 1)/2} = (2 + 1)^{(M – 1)/2} = 3^{(M – 1)/2} ≡ -1 (mod M)

so √b^M = (a – 1)^{(M – 1)/2}(a + 1)^{(M – 1)/2}b^½ ≡ (1)(-1)b½ (mod M) = -√b (mod M)

therefore, (a + 1 + √b)^M ≡ (a + 1 – √b) (mod M)

so (a + 1 + √b)^2(M+1)/2 = (a + 1 + √b)(a + 1 + √b)^M ≡ (a + 1 + √b)(a + 1 – √b) (mod M)

= (a + 1)² – b (mod M) = (a + 1)² – (a² – 1) (mod M) = a² + 2a + 1 – a² + 1 (mod M)

= 2a + 2 (mod M) = 2(a + 1) (mod M)

the denominator (2(a + 1))^(M+1)/2 = (2(a + 1))^{(M–1)/2 + 1} = (2(a + 1))^(M–1)/2(2(a + 1))

= 2^(M–1)/2(a + 1)^(M–1)/2(2(a + 1)) ≡ (1)(-1)(2(a + 1)) (mod M) = -2(a + 1) (mod M)

so u^(M+1)/2 ≡ -1 (mod M)

Therefore,

u^(M+1)/2 ≡ -1 (mod M)

u^{(M+1)/4+(M+1)/4} ≡ -1 (mod M)

u^(M+1)/4u^(M+1)/4 ≡ -1 (mod M)

u^(M+1)/4u^(M+1)/4ū^(M+1)/4 ≡ -ū^(M+1)/4 (mod M)

u^(M+1)/4(uū)^(M+1)/4 ≡ -ū^(M+1)/4 (mod M)

u^(M+1)/4(1)^(M+1)/4 ≡ -ū^(M+1)/4 (mod M)

u^(M+1)/4 ≡ -ū^(M+1)/4 (mod M)

u^(M+1)/4 + ū^(M+1)/4 ≡ 0 (mod M)

u^{(2^p–1+1)/4} + ū^{(2^p–1+1)/4} ≡ 0 (mod M)

u^{(2^p)/4} + ū^{(2^p)/4} ≡ 0 (mod M)

u^{2^(p–2)} + ū^{2^(p–2)} ≡ 0 (mod M)

s_p-2 ≡ 0 (mod M)

which means s_p-2 is divisible by 2^p – 1

Conclusion

We have proved the conditional (if s_p-2 is divisible by 2^p – 1, then 2^p – 1 is a prime number) and its converse (if 2^p – 1 is a prime number, then s_p-2 is divisible by 2^p – 1), which means the biconditional (s_p-2 is divisible by 2^p – 1 if and only if 2^p – 1 is a prime number) is also true.

Interesting Notes

Other s₀ values can be chosen, as long as the following criteria are met:

● b = a² – 1 is not a perfect square

● (a – 1)^{(M – 1)/2} ≡ 1 (mod M)

● (a + 1)^{(M – 1)/2} ≡ -1 (mod M)

The traditional value for s₀ is s₀ = 4 (a = 2, a – 1 = 1, a + 1 = 3, and b = 3), but other values that fit the above criteria are s₀ = 10 (a = 5, a – 1 = 4, a + 1 = 6, and b = 24) and s₀ = ²/₃ (a = ¹/₃, a – 1 = -²/₃, a + 1 = ⁴/₃, and b = -⁸/₉).