Proof of the Lucas–Lehmer test

Proof

Let $p$ be an odd prime and $M = M_p = 2^p - 1$, the Mersenne number. Then $p \ge 3$, so $M \ge 7$ and $M$ is odd.

Setup.

1. Let $A = \set{a + b\sqrt{3} : a, b \in \Z}$. It contains $1$ and is closed under differences and under products, since $(a + b\sqrt3)(c + d\sqrt3) = (ac + 3bd) + (ad + bc)\sqrt3$.
2. So $A$ is a subring of $\R$, and it is a commutative ring.
3. If $a + b\sqrt3 = c + d\sqrt3$ with integers $a, b, c, d$ and $b \ne d$, then $\sqrt3 = (a - c)/(d - b)$ is rational. This contradicts the irrationality of square roots of non-squares. So $a = c$ and $b = d$.
4. For an integer $N \ge 2$, the set $NA = \set{N\alpha : \alpha \in A}$ is a two-sided ideal of $A$. Let $X_N = A/NA$ be the quotient ring. We write $\bar\alpha$ for the coset of $\alpha$.
5. Let $s$ be an integer. If $s \in NA$, then $s = Nc + Nd\sqrt3$ for integers $c, d$. By step 3, $Nd = 0$ and $s = Nc$. So $\bar s = 0$ in $X_N$ exactly when $N \mid s$.
6. Put $\omega = 2 + \sqrt3$ and $\tau = 2 - \sqrt3$ in $A$. Then $\omega\tau = 4 - 3 = 1$.
7. We show $s_i = \omega^{2^i} + \tau^{2^i}$ by induction on $i$. For $i = 0$, $\omega + \tau = 4 = s_0$.
8. If $s_{i-1} = \omega^{2^{i-1}} + \tau^{2^{i-1}}$, then $s_{i-1}^2 - 2 = \omega^{2^i} + 2(\omega\tau)^{2^{i-1}} + \tau^{2^i} - 2 = \omega^{2^i} + \tau^{2^i}$, by step 6.
9. Put $t = 2^{p-2}$. So $s_{p-2} = \omega^t + \tau^t$, and $2t = 2^{p-1} = (M + 1)/2$.

If $s_{p-2} \equiv 0 \pmod M$, then $M$ is prime.

10. Assume $M \mid s_{p-2}$ and, for a contradiction, that $M$ is composite. By the square root bound, $M$ has a prime factor $q$ with $q^2 \le M$. Since $M$ is odd, $q$ is odd.
11. Work in $X = X_q$. Since $q \mid s_{p-2}$, step 5 gives $\bar\omega^t + \bar\tau^t = 0$.
12. Multiply by $\bar\omega^t$ and use $\omega\tau = 1$. This gives $\bar\omega^{2t} + 1 = 0$, so $\bar\omega^{2^{p-1}} = -1$ and $\bar\omega^{2^p} = 1$.
13. In $X$ we have $-1 \ne 1$: otherwise $\bar 2 = 0$, so $q \mid 2$ by step 5, but $q$ is odd.
14. By step 6, $\bar\omega$ is a unit of $X$, so it lies in the group of units $X^\times$. Let $r$ be its order.
15. By step 12 and the order criterion, $r$ divides $2^p$, so $r = 2^j$ with $j \le p$. If $j \le p - 1$, then $\bar\omega^{2^{p-1}} = 1$, against steps 12 and 13. So $r = 2^p$.
16. Each element of $A$ is congruent modulo $qA$ to some $a + b\sqrt3$ with $0 \le a, b < q$. So $X$ has at most $q^2$ elements.
17. The element $0$ of $X$ is not a unit, since $0 \cdot \beta = 0 \ne 1$ by step 13. So $X^\times$ has at most $q^2 - 1$ elements.
18. Since the order of an element divides the order of the group, $2^p \le q^2 - 1 < q^2 \le M = 2^p - 1$. This is false. So $M$ is prime.

If $M$ is prime, then $s_{p-2} \equiv 0 \pmod M$.

19. Assume $M$ is prime. Congruences below are modulo $M$. Since $2^p \equiv 1$ and $p$ is odd, $2 \equiv 2^{p+1} = (2^{(p+1)/2})^2$.
20. So $2$ is a quadratic residue modulo $M$, and $M \nmid 2$. By Euler's criterion, $2^{(M-1)/2} \equiv 1$.
21. Since $p$ is odd, $2^p = 2 \cdot 4^{(p-1)/2} \equiv 2 \pmod 3$. So $M \equiv 1 \pmod 3$, and $M \ne 3$.
22. The number $1 = 1^2$ is a quadratic residue modulo $3$, so the Legendre symbol $\left(\frac{M}{3}\right)$ equals $1$.
23. Also $(M - 1)/2 = 2^{p-1} - 1$ is odd. By quadratic reciprocity, $\left(\frac{3}{M}\right)\left(\frac{M}{3}\right) = (-1)^{(M-1)/2} = -1$. So $\left(\frac{3}{M}\right) = -1$.
24. By Euler's criterion, $3^{(M-1)/2} \equiv -1$.
25. For $0 < k < M$, the factorial formula gives $k!\,(M - k)! \binom{M}{k} = M!$. The prime $M$ divides $M!$ but no factor of $k!\,(M-k)!$. By Euclid's lemma, $M \mid \binom{M}{k}$.
26. Work in $X = X_M$. For integers $a, b$, the binomial theorem and step 25 give $\overline{(a + b\sqrt3)^M} = \overline{a^M + b^M (\sqrt3)^M}$. Here $(\sqrt3)^M = 3^{(M-1)/2}\sqrt3$, since $M$ is odd.
27. By Fermat's little theorem and step 24, $a^M \equiv a$ and $b^M 3^{(M-1)/2} \equiv -b$. So $\overline{(a + b\sqrt3)^M} = \overline{a - b\sqrt3}$.
28. Note $(1 + \sqrt3)^2 = 4 + 2\sqrt3 = 2\omega$. With step 27 for $a = b = 1$, $$\overline{(2\omega)^{(M+1)/2}} = \overline{(1 + \sqrt3)^{M+1}} = \overline{(1 + \sqrt3)(1 - \sqrt3)} = \overline{-2}.$$
29. By step 20, $\overline{2^{(M+1)/2}} = \overline{2 \cdot 2^{(M-1)/2}} = \bar 2$. So $\bar 2 \, \bar\omega^{(M+1)/2} = -\bar 2$.
30. The element $\bar 2$ is a unit of $X$, with inverse $\overline{(M+1)/2}$. Hence $\bar\omega^{(M+1)/2} = -1$, that is, $\bar\omega^{2t} = -1$ by step 9.
31. Multiply by $\bar\tau^t$ and use $\omega\tau = 1$. This gives $\bar\omega^t = -\bar\tau^t$, so $\overline{s_{p-2}} = \bar\omega^t + \bar\tau^t = 0$.
32. By step 5, $M$ divides $s_{p-2}$. So $s_{p-2} \equiv 0 \pmod{M_p}$.