Lucas–Lehmer primality test

Starting values s₀ other than 4 are possible, for instance 10, 52, and others (sequence A018844 in the OEIS).[2] The Lucas-Lehmer residue calculated with these alternative starting values will still be zero if M_p is a Mersenne prime. However, the terms of the sequence will be different and a non-zero Lucas-Lehmer residue for non-prime M_p will have a different numerical value from the non-zero value calculated when s₀ = 4.

It is also possible to use the starting value (2 mod M_p)(3 mod M_p)⁻¹, usually denoted by 2/3 for short.[2] This starting value equals (2^p + 1) /3, the Wagstaff number with exponent p.

Starting values like 4, 10, and 2/3 are universal, that is, they are valid for all (or nearly all) p. There are infinitely many additional universal starting values.[2] However, some other starting values are only valid for a subset of all possible p, for example s₀ = 3 can be used if p = 3 (mod 4).[3] This starting value was often used where suitable in the era of hand computation, including by Lucas in proving M₁₂₇ prime.[4] The first few terms of the sequence are 3, 7, 47, ... (sequence A001566 in the OEIS).

If s_p−2 = 0 mod M_p then the penultimate term is s_p−3 = ± 2^(p+1)/2 mod M_p. The sign of this penultimate term is called the Lehmer symbol ϵ(s₀, p).

In 2000 S.Y. Gebre-Egziabher proved that for the starting value 2/3 and for p ≠ 5 the sign is:

${\displaystyle \epsilon ({2 \over 3},\ p)=(-1)^{p-1 \over 2}}$

That is, ϵ(2/3, p) = +1 iff p = 1 (mod 4) and p ≠ 5.[2]

The same author also proved that the Lehmer symbols for starting values 4 and 10 when p is not 2 or 5 are related by:

${\displaystyle \epsilon (10,\ p)=\epsilon (4,\ p)\ \times \ (-1)^{{(p+1)(p+3)} \over 8}}$

That is, ϵ(4, p) × ϵ(10, p) = 1 iff p = 5 or 7 (mod 8) and p ≠ 2, 5.[2]

OEIS sequence A123271 shows ϵ(4, p) for each Mersenne prime M_p.

The goal is to show that ${\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}}$ implies that ${\displaystyle M_{p}}$ is prime. What follows is a straightforward proof exploiting elementary group theory given by J. W. Bruce[6] as related by Jason Wojciechowski.[7]

Suppose ${\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}.}$ Then

${\displaystyle \omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}=kM_{p}}$

for some integer k, so

${\displaystyle \omega ^{2^{p-2}}=kM_{p}-{\bar {\omega }}^{2^{p-2}}.}$

Multiplying by ${\displaystyle \omega ^{2^{p-2}}}$ gives

${\displaystyle \left(\omega ^{2^{p-2}}\right)^{2}=kM_{p}\omega ^{2^{p-2}}-(\omega {\bar {\omega }})^{2^{p-2}}.}$

Thus,

${\displaystyle \omega ^{2^{p-1}}=kM_{p}\omega ^{2^{p-2}}-1.\qquad \qquad (1)}$

For a contradiction, suppose M_p is composite, and let q be the smallest prime factor of M_p. Mersenne numbers are odd, so q > 2. Informally,[note 1] let ${\displaystyle \mathbb {Z} _{q}}$ be the integers modulo q, and let ${\displaystyle X=\left\{a+b{\sqrt {3}}\mid a,b\in \mathbb {Z} _{q}\right\}.}$ Multiplication in ${\displaystyle X}$ is defined as

${\displaystyle \left(a+{\sqrt {3}}b\right)\left(c+{\sqrt {3}}d\right)=[(ac+3bd)\,{\bmod {\,}}q]+{\sqrt {3}}[(ad+bc)\,{\bmod {\,}}q].}$

Clearly, this multiplication is closed, i.e. the product of numbers from X is itself in X. The size of X is denoted by ${\displaystyle |X|.}$

Since q > 2, it follows that ${\displaystyle \omega }$ and ${\displaystyle {\bar {\omega }}}$ are in X.[note 2] The subset of elements in X with inverses forms a group, which is denoted by X* and has size ${\displaystyle |X^{*}|.}$ One element in X that does not have an inverse is 0, so ${\displaystyle |X^{*}|\leq |X|-1=q^{2}-1.}$

Now ${\displaystyle M_{p}\equiv 0{\pmod {q}}}$ and ${\displaystyle \omega \in X}$, so

${\displaystyle kM_{p}\omega ^{2^{p-2}}=0}$

in X. Then by equation (1),

${\displaystyle \omega ^{2^{p-1}}=-1}$

in X, and squaring both sides gives

${\displaystyle \omega ^{2^{p}}=1.}$

Thus ${\displaystyle \omega }$ lies in X* and has inverse ${\displaystyle \omega ^{2^{p}-1}.}$ Furthermore, the order of ${\displaystyle \omega }$ divides ${\displaystyle 2^{p}.}$ However ${\displaystyle \omega ^{2^{p-1}}\neq 1}$, so the order does not divide ${\displaystyle 2^{p-1}.}$ Thus, the order is exactly ${\displaystyle 2^{p}.}$

The order of an element is at most the order (size) of the group, so

${\displaystyle 2^{p}\leq |X^{*}|\leq q^{2}-1<q^{2}.}$

But q is the smallest prime factor of the composite ${\displaystyle M_{p}}$, so

${\displaystyle q^{2}\leq M_{p}=2^{p}-1.}$

This yields the contradiction ${\displaystyle 2^{p}<2^{p}-1}$. Therefore, ${\displaystyle M_{p}}$ is prime.

In the other direction, the goal is to show that the primality of ${\displaystyle M_{p}}$ implies ${\displaystyle s_{p-2}\equiv 0{\pmod {M_{p}}}}$. The following simplified proof is by Öystein J. Rödseth.[8]

Since ${\displaystyle 2^{p}-1\equiv 7{\pmod {12}}}$ for odd ${\displaystyle p>1}$, it follows from properties of the Legendre symbol that ${\displaystyle (3|M_{p})=-1.}$ This means that 3 is a quadratic nonresidue modulo ${\displaystyle M_{p}.}$ By Euler's criterion, this is equivalent to

${\displaystyle 3^{\frac {M_{p}-1}{2}}\equiv -1{\pmod {M_{p}}}.}$

In contrast, 2 is a quadratic residue modulo ${\displaystyle M_{p}}$ since ${\displaystyle 2^{p}\equiv 1{\pmod {M_{p}}}}$ and so ${\displaystyle 2\equiv 2^{p+1}=\left(2^{\frac {p+1}{2}}\right)^{2}{\pmod {M_{p}}}.}$ This time, Euler's criterion gives

${\displaystyle 2^{\frac {M_{p}-1}{2}}\equiv 1{\pmod {M_{p}}}.}$

Combining these two equivalence relations yields

${\displaystyle 24^{\frac {M_{p}-1}{2}}\equiv \left(2^{\frac {M_{p}-1}{2}}\right)^{3}\left(3^{\frac {M_{p}-1}{2}}\right)\equiv (1)^{3}(-1)\equiv -1{\pmod {M_{p}}}.}$

Let ${\displaystyle \sigma =2{\sqrt {3}}}$, and define X as before as the ring ${\displaystyle X=\{a+b{\sqrt {3}}\mid a,b\in \mathbb {Z} _{M_{p}}\}.}$ Then in the ring X, it follows that

${\displaystyle {\begin{aligned}(6+\sigma )^{M_{p}}&=6^{M_{p}}+\left(2^{M_{p}}\right)\left({\sqrt {3}}^{M_{p}}\right)\\&=6+2\left(3^{\frac {M_{p}-1}{2}}\right){\sqrt {3}}\\&=6+2(-1){\sqrt {3}}\\&=6-\sigma ,\end{aligned}}}$

where the first equality uses the Binomial Theorem in a finite field, which is

${\displaystyle (x+y)^{M_{p}}\equiv x^{M_{p}}+y^{M_{p}}{\pmod {M_{p}}}}$,

and the second equality uses Fermat's little theorem, which is

${\displaystyle a^{M_{p}}\equiv a{\pmod {M_{p}}}}$

for any integer a. The value of ${\displaystyle \sigma }$ was chosen so that ${\displaystyle \omega ={\frac {(6+\sigma )^{2}}{24}}.}$ Consequently, this can be used to compute ${\displaystyle \omega ^{\frac {M_{p}+1}{2}}}$ in the ring X as

${\displaystyle {\begin{aligned}\omega ^{\frac {M_{p}+1}{2}}&={\frac {(6+\sigma )^{M_{p}+1}}{24^{\frac {M_{p}+1}{2}}}}\\&={\frac {(6+\sigma )(6+\sigma )^{M_{p}}}{24\cdot 24^{\frac {M_{p}-1}{2}}}}\\&={\frac {(6+\sigma )(6-\sigma )}{-24}}\\&=-1.\end{aligned}}}$

All that remains is to multiply both sides of this equation by ${\displaystyle {\bar {\omega }}^{\frac {M_{p}+1}{4}}}$ and use ${\displaystyle \omega {\bar {\omega }}=1}$, which gives

${\displaystyle {\begin{aligned}\omega ^{\frac {M_{p}+1}{2}}{\bar {\omega }}^{\frac {M_{p}+1}{4}}&=-{\bar {\omega }}^{\frac {M_{p}+1}{4}}\\\omega ^{\frac {M_{p}+1}{4}}+{\bar {\omega }}^{\frac {M_{p}+1}{4}}&=0\\\omega ^{\frac {2^{p}-1+1}{4}}+{\bar {\omega }}^{\frac {2^{p}-1+1}{4}}&=0\\\omega ^{2^{p-2}}+{\bar {\omega }}^{2^{p-2}}&=0\\s_{p-2}&=0.\end{aligned}}}$

Since ${\displaystyle s_{p-2}}$ is 0 in X, it is also 0 modulo ${\displaystyle M_{p}.}$