# proof of Lucas-Lehmer primality test

Let $p>2$ be a prime, and let $M_{p}=2^{p}-1$ be the corresponding Mersenne number. Then $M_{p}$ is prime if and only if $M_{p}$ divides $s_{p-1}$ (equivalently, if and only if $s_{p-1}\equiv 0\pod{M_{p}}$) where the numbers $(s_{n})_{n\geq 1}$ are given by the following recurrence relation:

 $\displaystyle s_{1}$ $\displaystyle=4$ $\displaystyle s_{n+1}$ $\displaystyle={s_{n}}^{2}-2,\quad n\geq 1$

We show that the validity of the primality test is equivalent to the following theorem, which is then proved directly:

###### Theorem 1.

(Lucas) $M_{p}$ is prime if and only if $\alpha^{(M_{p}+1)/2}\equiv-1\pod{M_{p}}$, where $\alpha=2+\sqrt{3}$.

To see that the two are in fact equivalent, let $\beta=2-\sqrt{3}$. Then $\alpha+\beta=4,\ \alpha\beta=1$. Thus

 $\displaystyle s_{1}$ $\displaystyle=\alpha+\beta$ $\displaystyle s_{2}$ $\displaystyle=(\alpha+\beta)^{2}-2=\alpha^{2}+\beta^{2}+2\alpha\beta-2=\alpha^% {2}+\beta^{2}$ $\displaystyle s_{3}$ $\displaystyle=\alpha^{4}+\beta^{4}$ $\displaystyle\cdots$ $\displaystyle s_{p-1}$ $\displaystyle=\alpha^{2^{p-2}}+\beta^{2^{p-2}}$

Note that $2^{p-2}=\frac{M_{p}+1}{4}$. Then

 $\displaystyle s_{p-1}\equiv 0\pod{M_{p}}$ $\displaystyle\iff\alpha^{(M_{p}+1)/4}+\beta^{(M_{p}+1)/4}\equiv 0\pod{M_{p}}$ $\displaystyle\iff\alpha^{(M_{p}+1)/2}+(\alpha\beta)^{(M_{p}+1)/4}\equiv 0\pod{% M_{p}}$ $\displaystyle\iff\alpha^{(M_{p}+1)/2}\equiv-1\pod{M_{p}}$

It thus remains to prove Theorem 1. We start with two simple lemmas:

###### Lemma 2.

If $p>3$ is prime, then $\alpha^{p-1}\equiv 1\pod{p}$ or $\alpha^{p+1}\equiv 1\pod{p}$.

###### Proof.
 $\alpha^{p}\equiv 2^{p}+3^{(p-1)/2}\sqrt{3}\equiv\begin{cases}\alpha\pod{p}&% \text{if }\left(\frac{3}{p}\right)=1\\ \beta\pod{p}&\text{if }\left(\frac{3}{p}\right)=-1\end{cases}$

where $\left(\frac{\cdot}{\cdot}\right)$ is the Legendre symbol. Thus

 $\displaystyle\left(\frac{3}{p}\right)=1\ \Rightarrow\ \alpha^{p-1}=\alpha^{p}% \alpha^{-1}=\alpha^{p}\beta\equiv\alpha\beta=1\pod{p}$ $\displaystyle\left(\frac{3}{p}\right)=-1\ \Rightarrow\ \alpha^{p+1}=\alpha^{p}% \alpha\equiv\beta\alpha=1\pod{p}$

###### Lemma 3.

Let $p$ be a prime with $p\equiv 7\pod{8}$ and $p\equiv 7\pod{12}$. Then $\alpha^{(p+1)/2}\equiv-1\pod{p}$.

###### Proof.

$(1+\sqrt{3})^{2}=4+2\sqrt{3}=2\alpha$, so that

 $(1+\sqrt{3})^{p+1}=2^{(p+1)/2}\alpha^{(p+1)/2}$

But $p\equiv 7\pod{8}$, so that $\left(\frac{2}{p}\right)=1$. Thus $2^{(p+1)/2}\equiv 2\cdot 2^{(p-1)/2}\equiv 2\pod{p}$ and therefore

 $(1+\sqrt{3})^{p+1}\equiv 2\alpha^{(p+1)/2}\pod{p}$

Also,

 $(1+\sqrt{3})^{p+1}=(1+\sqrt{3})(1+\sqrt{3})^{p}\equiv(1+\sqrt{3})(1+3^{(p-1)/2% }\sqrt{3})\pod{p}$

But $p\equiv 7\pod{12}$, so $3^{(p-1)/2}\equiv-1\pod{p}$ and thus

 $(1+\sqrt{3})^{p+1}\equiv(1+\sqrt{3})(1-\sqrt{3})=-2\pod{p}$

Putting together the two expressions for $(1+\sqrt{3})^{p+1}$, we get $\alpha^{(p+1)/2}\equiv-1\pod{p}$. ∎

We are now in a position to prove Theorem 1:

###### Proof.

$(\Rightarrow):$ If $M_{p}$ is prime where $p>3$ is prime, then note that $M_{p}\equiv 7\pod{8},7\pod{1}2$ so that $M_{p}$ satisfies the conditions of Lemma 3. The result follows.

$(\Leftarrow):$ If $\alpha^{(M_{p}+1)/2}\equiv-1\pod{M_{p}}$, choose $q\mid M_{p}$ for $q$ a prime. Since $M_{p}\equiv 7\pod{1}2$, we have $q>3$. Since $\alpha^{(M_{p}+1)/2}\equiv-1\pod{M_{p}}$ also $\alpha^{(M_{p}+1)/2}\equiv-1\pod{q}$ and thus $\alpha^{M_{p}+1}\equiv 1\pod{q}$. But $M_{p}+1=2^{p}$, so

 $\alpha^{2^{p}}\equiv 1\pod{q}$

Thus the order of $\alpha\pod{q}$ divides $2^{n}$. It can’t divide $2^{n-1}$ since $\alpha^{(M_{p}+1)/2}\equiv-1\pod{q}$, so its order is precisely $2^{n}=M_{p}+1$. However, $\alpha^{q+1}\equiv 1\pod{q}$ or $\alpha^{q-1}\equiv 1\pod{q}$ by Lemma 2 and thus $q\geq M_{p}$. But $q\mid M_{p}$, so $q=M_{p}$ and $M_{p}$ is in fact prime. ∎

Title proof of Lucas-Lehmer primality test ProofOfLucasLehmerPrimalityTest 2013-03-22 18:42:16 2013-03-22 18:42:16 rm50 (10146) rm50 (10146) 5 rm50 (10146) Proof msc 11A51