Mathwords logoMathwords

Lucas-Lehmer Test — Definition, Formula & Examples

The Lucas-Lehmer test is a primality test that determines whether a Mersenne number Mp=2p−1M_p = 2^p - 1 is prime. It works by computing a specific recursive sequence modulo MpM_p and checking whether the final term is zero.

For an odd prime pp, define the sequence s0=4s_0 = 4 and sk+1=sk2−2s_{k+1} = s_k^2 - 2 for k≥0k \geq 0. The Mersenne number Mp=2p−1M_p = 2^p - 1 is prime if and only if sp−2≡0(modMp)s_{p-2} \equiv 0 \pmod{M_p}.

Key Formula

s0=4,sk+1=sk2−2(modMp)s_0 = 4, \quad s_{k+1} = s_k^2 - 2 \pmod{M_p}
Where:
  • sks_k = The k-th term of the Lucas-Lehmer sequence
  • MpM_p = The Mersenne number $2^p - 1$
  • pp = An odd prime exponent

How It Works

Start by setting s0=4s_0 = 4. At each step, square the current value, subtract 2, and reduce the result modulo MpM_p. Repeat this p−2p - 2 times total, producing s1,s2,…,sp−2s_1, s_2, \ldots, s_{p-2}. If the final value sp−2s_{p-2} is exactly 0 modulo MpM_p, then MpM_p is prime. Otherwise, MpM_p is composite. The test only applies when pp itself is an odd prime, since MpM_p is always composite when pp is composite.

Worked Example

Problem: Use the Lucas-Lehmer test to determine whether M7=27−1=127M_7 = 2^7 - 1 = 127 is prime.
Setup: Since p=7p = 7, we need to compute p−2=5p - 2 = 5 iterations of the sequence, checking whether s5≡0(mod127)s_5 \equiv 0 \pmod{127}.
Step 1: Start with s0=4s_0 = 4. Compute s1s_1:
s1=42−2=14s_1 = 4^2 - 2 = 14
Step 2: Compute s2s_2:
s2=142−2=194≡194−127=67(mod127)s_2 = 14^2 - 2 = 194 \equiv 194 - 127 = 67 \pmod{127}
Step 3: Compute s3s_3:
s3=672−2=4487≡4487mod  127=42(mod127)s_3 = 67^2 - 2 = 4487 \equiv 4487 \mod 127 = 42 \pmod{127}
Step 4: Compute s4s_4:
s4=422−2=1762≡1762mod  127=111(mod127)s_4 = 42^2 - 2 = 1762 \equiv 1762 \mod 127 = 111 \pmod{127}
Step 5: Compute s5s_5:
s5=1112−2=12319≡12319mod  127=0(mod127)s_5 = 111^2 - 2 = 12319 \equiv 12319 \mod 127 = 0 \pmod{127}
Answer: Since s5≡0(mod127)s_5 \equiv 0 \pmod{127}, the Mersenne number M7=127M_7 = 127 is prime.

Why It Matters

The Lucas-Lehmer test is the method behind every record-breaking prime discovery by the Great Internet Mersenne Prime Search (GIMPS). Its efficiency — requiring only p−2p - 2 modular squarings — makes it feasible to test numbers with millions of digits, far beyond the reach of general-purpose primality tests.

Common Mistakes

Mistake: Applying the test to arbitrary integers, not just Mersenne numbers of the form 2p−12^p - 1 with pp an odd prime.
Correction: The Lucas-Lehmer test is specifically designed for Mersenne numbers. For general integers, use other primality tests such as Miller-Rabin or AKS.