Editing Lucas–Lehmer primality test (section)

=== Sufficiency ===

The goal is to show that <math>s_{p-2} \equiv 0 \pmod{M_p}</math> implies that <math>M_p</math> is prime. What follows is a straightforward proof exploiting elementary [[group theory]] given by J. W. Bruce<ref>{{cite journal |first=J. W. |last=Bruce |title=A Really Trivial Proof of the Lucas–Lehmer Test |journal=The American Mathematical Monthly |volume=100 |issue=4 |pages=370–371 |year=1993 |doi=10.2307/2324959|jstor=2324959 }}</ref> as related by Jason Wojciechowski.<ref>Jason Wojciechowski. [https://web.archive.org/web/20110722232101/http://wonka.hampshire.edu/~jason/math/smithnum/project.ps Mersenne Primes, An Introduction and Overview]. 2003.</ref>

Suppose <math>s_{p-2} \equiv 0 \pmod{M_p}.</math> Then 
:<math>\omega^{2^{p-2}} + \bar{\omega}^{2^{p-2}} = k M_p</math> 
for some integer ''k'', so
:<math>\omega^{2^{p-2}} = k M_p - \bar{\omega}^{2^{p-2}}.</math>
Multiplying by <math>\omega^{2^{p - 2}}</math> gives
:<math>\left(\omega^{2^{p-2}}\right)^2 = k M_p\omega^{2^{p-2}} - (\omega \bar{\omega})^{2^{p-2}}.</math>
Thus,
:<math>\omega^{2^{p-1}} = k M_p\omega^{2^{p-2}} - 1.\qquad\qquad(1)</math>

For a contradiction, suppose ''M''<sub>''p''</sub> is composite, and let ''q'' be the smallest prime factor of ''M''<sub>''p''</sub>. Mersenne numbers are odd, so ''q''&nbsp;>&nbsp;2.  Let <math>\mathbb{Z}_q</math> be the integers modulo ''q'', and let <math>X = \left\{a + b \sqrt{3} \mid a, b \in \mathbb{Z}_q\right\}.</math> Multiplication in <math>X</math> is defined as

:<math>\left(a + \sqrt{3} b\right) \left(c + \sqrt{3} d\right) = [(a c + 3 b d) \,\bmod\,q] + \sqrt{3} [(a d + b c) \,\bmod\,q].</math><ref group="note">Formally, let <math>\mathbb{Z}_q = \mathbb{Z} / q \mathbb{Z}</math> and <math>X = \mathbb{Z}_q[T] / \langle T^2 - 3 \rangle</math>.</ref>

Clearly, this multiplication is closed, i.e. the product of numbers from ''X'' is itself in ''X''.  The size of ''X'' is denoted by <math>|X|.</math>

Since ''q''&nbsp;>&nbsp;2, it follows that <math>\omega</math> and <math>\bar{\omega}</math> are in ''X''.<ref group="note">Formally, <math>\omega + \langle T^2 - 3 \rangle</math> and <math>\bar{\omega} + \langle T^2 - 3 \rangle</math> are in ''X''.  By abuse of language <math>\omega</math> and <math>\bar{\omega}</math> are identified with their images in ''X'' under the natural ring homomorphism from <math>\mathbb{Z}[\sqrt{3}] </math> to ''X'' which sends <math>\sqrt{3}</math> to ''T''.</ref> The subset of elements in ''X'' with inverses forms a group, which is denoted by ''X''* and has size <math>|X^*|.</math> One element in ''X'' that does not have an inverse is 0, so <math>|X^*| \leq |X| - 1 = q^2 - 1.</math>

Now <math>M_p \equiv 0 \pmod{q}</math> and <math>\omega \in X</math>, so
:<math>kM_p\omega^{2^{p-2}} = 0</math>
in ''X''.
Then by equation (1), 
:<math>\omega^{2^{p-1}} = -1</math>
in ''X'', and squaring both sides gives 
:<math>\omega^{2^p} = 1.</math>  
Thus <math>\omega</math> lies in ''X''* and has inverse <math>\omega^{2^{p}-1}.</math> Furthermore, the [[order (group theory)|order]] of <math>\omega</math> divides <math>2^p.</math> However <math>\omega^{2^{p-1}} \neq 1</math>, so the order does not divide <math>2^{p-1}.</math> Thus, the order is exactly <math>2^p.</math>

The order of an element is at most the order (size) of the group, so
:<math>2^p \leq |X^*| \leq q^2 - 1 < q^2.</math> 
But ''q'' is the smallest prime factor of the composite <math>M_p</math>, so
:<math>q^2 \leq M_p = 2^p-1.</math> 
This yields the contradiction <math>2^p < 2^p-1</math>. Therefore, <math>M_p</math> is prime.