Editing Lucas–Lehmer primality test (section)

=== Necessity ===

In the other direction, the goal is to show that the primality of <math>M_p</math> implies <math>s_{p-2} \equiv 0 \pmod{M_p}</math>. The following simplified proof is by Öystein J. Rödseth.<ref name="Rodseth">{{cite journal|last=Rödseth|first=Öystein J.|title=A note on primality tests for N=h·2^n−1|journal=BIT Numerical Mathematics|volume=34|number=3|date=1994|pages=451–454|doi=10.1007/BF01935653|s2cid=120438959 |url=http://folk.uib.no/nmaoy/papers/luc.pdf|archive-url=https://web.archive.org/web/20160306082833/http://folk.uib.no/nmaoy/papers/luc.pdf|archive-date=March 6, 2016}}</ref>

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

:<math>3^{\frac{M_p-1}{2}} \equiv -1 \pmod{M_p}.</math>

In contrast, 2 is a [[quadratic residue]] modulo <math>M_p</math> since <math>2^p \equiv 1 \pmod{M_p}</math> and so <math>2 \equiv 2^{p+1} = \left(2^{\frac{p+1}{2}}\right)^2 \pmod{M_p}.</math> This time, Euler's criterion gives

:<math>2^{\frac{M_p-1}{2}} \equiv 1 \pmod{M_p}.</math>

Combining these two equivalence relations yields

:<math>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}.</math>

Let <math>\sigma = 2\sqrt{3}</math>, and define ''X'' as before as the ring <math>X = \{a + b\sqrt{3} \mid a, b \in \mathbb{Z}_{M_p}\}.</math> Then in the ring ''X'', it follows that

:<math>
\begin{align}
 (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{align}
</math>

where the first equality uses the [[Proofs of Fermat's little theorem#Proofs using the binomial theorem|Binomial Theorem in a finite field]], which is

: <math>(x+y)^{M_p} \equiv x^{M_p} + y^{M_p} \pmod{M_p}</math>,

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

: <math>a^{M_p} \equiv a \pmod{M_p}</math>

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

:<math>
\begin{align}
 \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{align}
</math>

All that remains is to multiply both sides of this equation by <math>\bar{\omega}^{\frac{M_p+1}{4}}</math> and use <math>\omega \bar{\omega} = 1</math>, which gives

:<math>
\begin{align}
 \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{align}
</math>

Since <math>s_{p - 2}</math> is 0 in ''X'', it is also 0 modulo <math>M_p.</math>