proof of Lucas-Lehmer primality test
The objective of this article is to prove the Lucas-Lehmer primality test:
Let be a prime, and let be the corresponding Mersenne number. Then is prime if and only if divides (equivalently, if and only if ) where the numbers are given by the following recurrence relation:
(Lucas) is prime if and only if , where .
To see that the two are in fact equivalent, let . Then . Thus
Note that . Then
It thus remains to prove Theorem 1. We start with two simple lemmas:
If is prime, then or .
where is the Legendre symbol. Thus
Let be a prime with and . Then .
, so that
But , so that . Thus and therefore
But , so and thus
Putting together the two expressions for , we get . ∎
We are now in a position to prove Theorem 1:
If , choose for a prime. Since , we have . Since also and thus . But , so
Thus the order of divides . It can’t divide since , so its order is precisely . However, or by Lemma 2 and thus . But , so and is in fact prime. ∎