# A really trivial proof of the Lucas-Lehmer test

> An annotated edition of this paper on Fermat's Library, where scientists and readers explain its ideas, equations and history in the margins. Annotated edition: https://fermatslibrary.com/s/a-really-trivial-proof-of-the-lucas-lehmer-test

- **Authors:** J. W. Bruce
- **Topic:** Mathematics
- **Original:** https://s3-us-west-1.amazonaws.com/fermatslibrary/uploads%2F1459662701775-vqlnlklb75njcg4m-ece303b9a562ae087f5fb04453a7912c%2FA+Really+Trivial+Proof+of+the+Lucas-Lehmer+Test.pdf
- **Pages:** 2
- **Annotations:** 21 comments in 14 threads
- **Featured:** Fermat's Library Journal Club
- **Annotated edition:** https://fermatslibrary.com/s/a-really-trivial-proof-of-the-lucas-lehmer-test

## Annotations

### Annotation 1 (page 1)

Beside the passage: “A Really Trivial Proof of the”

**Annotation** by Luís Batalha (2016-04-03):

> The Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers.  The test was originally developed by Édouard Lucas in 1856 and subsequently improved by Lucas in 1878 and Derrick Henry Lehmer in the 1930s.
>
> Mersenne numbers can be written in the form
>
> $$
> M_n = 2^n-1
> $$
> where $n$ is an integer.
>
> Mersenne numbers are named after the French monk Marin Mersenne (1588–1648) who compiled a list of Mersenne primes. These numbers have very interesting properties, in particular there are conjectures that predict there are an infinite number of Mersenne primes, but these have not been settled.
>
> The largest known prime number is a Mersenne prime $M_{74,207,281}$, proved prime in 2015. One reason for the prevalence of Mersenne primes in the record books is because the Lucas-Lehmer test is a relatively easy test from a computational standpoint for the primality of a Mersenne number. In fact, since $M_{521}$ was proven prime in 1952, the largest known prime has always been a Mersenne prime (with one exception in 1989). See a [history of prime number records](http://primes.utm.edu/notes/by_year.html).
>
> The Lucas–Lehmer test is the primality test used by the [Great Internet Mersenne Prime Search](https://en.wikipedia.org/wiki/Great_Internet_Mersenne_Prime_Search) to locate large primes. This search has been successful in locating many of the largest primes known to date.

**Reply** by Luís Batalha (2016-04-03):

> If you want to learn more about the discovery of $M_{74,207,281}$ it's worth watching this video  [![IMAGE ALT TEXT](https://slack-imgs.com/?c=1&o1=wi400.he300&url=https%3A%2F%2Fi.ytimg.com%2Fvi%2FlEvXcTYqtKU%2Fhqdefault.jpg&width=400&height=300)](https://www.youtube.com/watch?v=lEvXcTYqtKU "How they found the World's Biggest Prime Number")

### Annotation 2 (page 1)

Beside the passage: “In the paper [1] Rosen gave a beautiful and elementary proof of the Lucas-Lehmer primality test for Mersenne numbers, i.e. those of the form M = 2P - 1. This test is very attractive, since it can be easily implemented on a computer, and it gives students the chance of experiencing the thrill of discovering very large …”

**Annotation** by Luís Batalha (2016-04-03):

> A basic theorem about Mersenne numbers states that if $M_p$ is prime, then the exponent $p$ must also be prime.
>
> To prove this let's assume that $p$ is composite $p=ab$. In that case it's possible to write
>
> $$
> M_p= 2^{ab}-1=(2^{a}-1)(1+2^a+2^{2a}+...+2^{(b-1)a})
> $$
>
> which means that $M_p$ is divisible by $2^a-1$ and thus not prime!

**Reply** by Micael Oliveira (2016-04-05):

> It is curious to notice that for any real number a and integer n the relation $ (a^{n} - 1) $ can be rewritten as:
>
> $$ (a^{n} - 1) = (a-1)\cdot P(a) $$
>
> where P(a) is a polynomial. One can prove this by induction. For 1 it is trivial. Let's consider two scenarios where n is even and n is odd.
>
> For n = 2 (even):
>
> $$ (a^{2} - 1) = (a-1)(a+1) $$
>
> For n = 3 (odd):
>
> \begin{eqnarray*}
>
> (a^{3} - 1) &=&  a^{3} - 1 + a^{2} - a^{2}\\
>             &=&  (a^{2} - 1) + a^{3} - a^{2} \\
>             &=&  (a - 1)(a^{2} + a + 1)
>
> \end{eqnarray*}
>
> One can then write that for any integer k:
> \begin{eqnarray*}
>
> (a^{n} - 1) &=&  (a - 1)\sum_{n=0}^{n-1} a^{k}
>
> \end{eqnarray*}

### Annotation 3 (page 1)

Beside the passage: “In the paper [1] Rosen gave a beautiful and elementary proof of the Lucas-Lehmer primality test for Mersenne numbers, i.e. those of the form M = 2P - 1. This test is very attractive, since it can be easily implemented on a computer, and it gives students the chance of experiencing the thrill of discovering very large …”

**Annotation** by Luís Batalha (2016-04-03):

> In pseudocode, the test might be written as
>
> ```
> // Determine if Mp = 2^p − 1 is prime
> Lucas–Lehmer(p)
>     var s = 4
>     var M = 2p − 1
>     repeat p − 2 times:
>         s = ((s × s) − 2) mod M
>     if s == 0 return PRIME else return COMPOSITE
> ```
> The Lucas-Lehmer test reduces substantially the complexity to prove the primality of the number - O($p^2\log p \log \log p$)

### Annotation 4 (page 1)

Beside the passage: “Theorem 1 (LUCAS-LEHMER). Let p be a prime number. Then Mp = 2P - 1 is a prime if Mp diuides Sp_ 1.”

**Annotation** by Aaron Meurer (2016-04-05):

> Is the theorem if and only if?

**Reply** by Luís Batalha (2016-04-05):

> Yes, if $M_p$ doesn't divide $S_{p-1}$ it's not prime.

### Annotation 5 (page 1)

Beside the passage: “We now follow Rosen by setting w = 2 + v3, a; = 2 - 3. One then checks that wa; = 1 and the next result follows easily by induction:”

**Annotation** by Luís Batalha (2016-04-03):

> The $\textbf{overall idea of this proof}$ is to start by assuming that $M_p$ divides $S_{p-1}$, and then consider that $M_p$ is not a prime which will lead us to a contradiction.

**Reply** by Aaron Meurer (2016-04-05):

> $(2+\sqrt{3})(2-\sqrt{3})=2^2 - \sqrt{3}^2 = 4 - 3 = 1$

### Annotation 6 (page 1)

Beside the passage: “It follows from the lemma that if Mp divides Sp, then 22P2 + ai2P-2 0 (mod Mp). Actually we will want to spell this out explicitly, so we write cv 2P2 + = RMp for some integer R. Multiplying this identity by 02Pp-2 we find that”

**Annotation** by Luís Batalha (2016-04-03):

> To prove that this result is equivalent to $S_m = S^2_{m-1}-2$ we just need to calculate $S_{m-1}$
>
> $$
> S^2_{m-1}=(w^{2^{m-2}}+\bar w^{2^{m-2}})^2=w^{2^{m-1}}+\bar w^{2^{m-1}}+2(w\bar w)^{2^{m-2}}=\\
> =w^{2^{m-1}}+\bar w^{2^{m-1}}+2=S_m+2
> $$

### Annotation 7 (page 2)

Beside the passage: “Lemma 2. Let X be a set with a binary operation which is associative and has an identity. Then the set X* of invertible elements in Xforms a group.”

**Annotation** by Luís Batalha (2016-04-03):

> For $X^*$ to form a group we just need to prove the Closure property:
> For all $x_1^-1$, $x_2^-1$ in $X^*$, the result of the operation, $x_1^-1.x_2^-1$, is also in $X^*$.
>
> We know that $x_1.x_1^-1=1$ and $x_2.x_2^-1=1$ but we need to prove that $x_1.x_2$ has an inverse. Now, if we calculate
>
> $$
> x_1.x_2.x_2^{-1}.x_1^{-1}=x_1.1.x_1^{-1}=x_1.x_1^{-1}=1
> $$
>
> and so $x_2^{-1}.x_1^{-1}$ is the inverse of $x_1.x_2$.

**Reply** by Asadullah Khalid Khalid (2020-11-01):

> Does the . operator here represents a binary operation or the multiplication operation ?

**Reply** by Asadullah Khalid Khalid (2020-11-01):

> Does the . operator here represents a binary operation or the multiplication operation ?

### Annotation 8 (page 2)

Beside the passage: “Lemma 3. If G is a finite group then the order of an element is at most the order of the group. If x E G and Xr = 1 then the order of x divides r.”

**Annotation** by Luís Batalha (2016-04-03):

> The order of a group is the number of elements in that group and the order of an element $a$ is the smallest positive integer $m$ such that $a^m = 1$.
>
> To prove Lemma 3 let's consider a group that has 3 elements a,b and 1. If $a \neq aa \neq aaa \neq aaaa $ we have already 4 different elements in the group which is a contradiction since the order of the group is 3. Thus the order of $a\leq3$.

### Annotation 9 (page 2)

Beside the passage: “Proof of Theorem 1: Let Zq denote the set of integers modulo q, and X denote the set (a + bC/: a, b E Zq}. We can define two binary operations on X, namely addition and multiplication, in the obvious manner. So in the case of multiplication, which is the one of interest, we choose representatives in Z[V3] of our …”

**Annotation** by Luís Batalha (2016-04-03):

> The set of all integers which have the same remainder when divided by $q$ is called the $\textbf{congruence class}$ of a modulo $q$. The collection of all congruence classes modulo q is called the $\textbf{set of integers modulo q}$, denoted by $Z_q$
>
> For instance, the set of integers modulo 3 $Z_3$ has three elements which we will call {$\bar0,\bar1,\bar2$}. Don't confuse these elements with the regular integers 0,1,2.  As an example, $\bar 2$ denotes the set of all integers which have remainder 2 when divided by 3  {2,5,8,...}
>
> Now we can perform standard modular arithmetic to determine the addition and multiplication tables for this set. We find that $\bar 1.\bar 1= \bar 1 $, and $\bar 2.\bar 2= \bar 4= \bar 1$. Thus, both of the nonzero elements have inverses! Note that in computing the multiplication I mentioned a new element $\bar 4$ that looks out of place. But it's okay, because we know that $\bar 4 \equiv \bar 1$ mod 3. So we can always do normal arithmetic under the bar and then simplify it afterward. This is why modular arithmetic is so easy!
>
> We see that this can happen in a finite field because there isn't room for numbers to keep getting bigger and bigger. Instead, multiplication "wraps around" until it gets to $\bar1$ and you find your inverse.
>
> This trick only works because $q$ was prime. If $q$ was not prime we could write $q=ab$ as a product of 2 primes. Then, we would not be able to find an inverse for $a$, because in the integers modulo $q$, we have that $\bar a \bar b=\overline{ab} =\bar 0$. So if there were some $\bar c$ such that $\bar a\bar c=1$, then we would have $\bar b = \bar a \bar c \bar b=\bar 0$, a contradiction!

### Annotation 10 (page 2)

Beside the passage: “Proof of Theorem 1: Let Zq denote the set of integers modulo q, and X denote the set (a + bC/: a, b E Zq}. We can define two binary operations on X, namely addition and multiplication, in the obvious manner. So in the case of multiplication, which is the one of interest, we choose representatives in Z[V3] of our …”

**Annotation** by Luís Batalha (2016-04-03):

> Note that $Z_q$ has $q$ elements: {$\bar 0, \bar 1, \bar 2, ..., \overline {q-1}$} and so $X$ has $q\times q = q^2$ elements as we have $q$ options for $a$ and another $q$ options for $b$.  In case of $X^*$ since 0 is non-invertible we have $q^2-1$ elements.

### Annotation 11 (page 2)

Beside the passage: “Now consider w = 2 + C as an element of X. Since q divides Mp it follows that RMP c 2P 2, when viewed as an element of X, is 0. So the equalities noted in (*) and (**) above in X reduce to -o2P = -1, and o2P = 1 respectively. It follows that w lies in X*, and has order 2P. For the order of co clearly divides 2P by …”

**Annotation** by Luís Batalha (2016-04-03):

> Don't forget that we chose $q$ above as a prime divisor of $M_p$ and so $M_p \equiv 0$ modulo $q$, which means that $RM_pw^{2^{p-2}} \equiv 0$ modulo $q$.

### Annotation 12 (page 2)

Beside the passage: “Now consider w = 2 + C as an element of X. Since q divides Mp it follows that RMP c 2P 2, when viewed as an element of X, is 0. So the equalities noted in (*) and (**) above in X reduce to -o2P = -1, and o2P = 1 respectively. It follows that w lies in X*, and has order 2P. For the order of co clearly divides 2P by …”

**Annotation** by Luís Batalha (2016-04-03):

> Note that $\bar w w = 1$ and so $w \in X^*$

### Annotation 13 (page 2)

Beside the passage: “Now consider w = 2 + C as an element of X. Since q divides Mp it follows that RMP c 2P 2, when viewed as an element of X, is 0. So the equalities noted in (*) and (**) above in X reduce to -o2P = -1, and o2P = 1 respectively. It follows that w lies in X*, and has order 2P. For the order of co clearly divides 2P by …”

**Annotation** by Tarit Goswami (2018-12-27):

> Hi,
>
> I am not getting how the order of $\omega$ is $2^p$. In the second equality, we have $w^{2^{p}}=1$, that means order of $\omega$ divides $2^p$. But how $w^{2^{p-1}}=-1$ ensures that there is no smaller power of $\omega$ which equals $1$?

**Reply** by Roy Dong (2019-04-17):

> Let $|\omega|$ denote the order of $\omega$. If $|\omega| < 2^p$ and divides $2^p$, $|\omega|$ must divide $2^{p-1}$, since the only prime factor of $2^p$ is $2$.

### Annotation 14 (page 2)

Beside the passage: “1. M. I. Rosen, A Proof of the Lucas-Lehmer Test, Amer. Math. Monthly, 95 (1988), 855-856.”

**Annotation** by Luís Batalha (2016-04-03):

> If you want to read Rosen's original paper click [here](http://fermatslibrary.com/s/a-proof-of-the-lucas-lehmer-test)

## Full text

Extracted from the PDF. [Annotation N] marks where each annotation above sits.

#### Page 1

A Really Trivial Proof of the [Annotation 1]

Lucas-Lehmer Test

J. W. Bruce

In the paper [1] Rosen gave a beautiful and elementary proof of the Lucas-Lehmer primality test for Mersenne numbers, i.e. those of the form M = 2P - 1. This test [Annotation 2] is very attractive, since it can be easily implemented on a computer, and it gives students the chance of experiencing the thrill of discovering very large (if wellknown) primes for themselves. In this article we show that it is possible to simplify Rosen's proof of the sufficiency of the test a little to eliminate any mention of algebraic numbers or questions concerning splittings of primes. In fact we only use a couple of lemmas from group theory, which are hardly worth glorifying with such a description. Of course it is the sufficiency which allows one to produce the large primes, so the half of the result we prove has its attractions. The necessity requires some basic facts concerning quadratic residues. The proof below might make a pleasant application early on in an abstract algebra course. The author was in receipt of a Fulbright award while this note was written. We start by defining a sequence Sn by setting S1 = 4 and Sn = S2_1 [Annotation 3] - 2.

Theorem [Annotation 4] 1 (LUCAS-LEHMER). Let p be a prime number. Then Mp = 2P - 1 is a prime if Mp diuides Sp_ 1.

We now [Annotation 5] follow Rosen by setting w = 2 + v3, a; = 2 - 3. One then checks that wa; = 1 and the next result follows easily by induction:

2m`-1 -2m-1 Lemma 1. Sm = 2 + s2m

It follows from [Annotation 6] the lemma that if Mp divides Sp, then 22P2 + ai2P-2 0 (mod Mp). Actually we will want to spell this out explicitly, so we write cv 2P2 + = RMp for some integer R. Multiplying this identity by 02Pp-2 we find that

2p-1 sM (tP-1 (2*)

and squaring

W 2P= (RMw 2P2 - 1) ( )

Now assume that Mp is composite, and choose a prime divisor q with q2 ? Mp. (This is where our proof departs from that of Rosen.) At one stage below we need the fact that q obviously is not 2. We are going to use some really elementary results and ideas from group theory.

370 A REALLY TRIVIAL PROOF OF THE LUCAS-LEHMER TEST [April

This content downloaded from 128.240.225.120 on Fri, 20 Jun 2014 11:54:59 AM All use subject to JSTOR Terms and Conditions

#### Page 2

Lemma 2. Let X be a set with a binary operation which is associative and has an identity. Then the set X* of invertible elements in Xforms a group. [Annotation 7]

Proof: Clearly the identity 1 E X8, so we have a non-empty set. We now have only to show that the set X* is closed under the binary operation. But if x1 and x2 are invertible elements with inverses x - 1, x -1 then x1x2 has inverse x 1Xj1.

Lemma 3. If G is a finite group then the order of an element is at most the order of the [Annotation 8] group. If x E G and Xr = 1 then the order of x divides r.

(Results in group theory do not get any easier than this. These results are nowhere near as deep as Lagrange's Theorem for example!)

Proof of Theorem 1: Let [Annotation 9] Zq denote the set of integers modulo q, and X denote the set (a + bC/: a, b E Zq}. We can define two binary operations on X, namely addition and multiplication, in the obvious manner. So in the case of multiplication, which is the one of interest, we choose representatives in Z[V3] of our elements of X compute the product in the usual way, (a1 + b1x/3)(a2 + b2C/i) as (a1a2 + 3b1b2) + (a1b2 + a2b1)C3 and then reduce the coefficients modulo q. In the case of addition we obviously get an abelian group, and for multiplication we clearly have an associative (and commutative) binary operation with identity 1. Let X* denote the group of invertible elements of X with respect to multiplication. Lemma 2 tells us that this is a group, while Lemma 3 [Annotation 10] tells us that the order of any element of X* is at most q2 - 1, since X* contains at least one non-invertible element, namely 0.

Now consider w = 2 + C as an element of X. Since q divides Mp it follows that [Annotation 11] RMP c 2P 2, when viewed as an element of X, is 0. So the equalities noted in (*) and (**) above in X reduce to -o2P = -1, and o2P = 1 respectively. It follows that [Annotation 12] w lies in X*, and has order 2P. For the order of co clearly divides 2P [Annotation 13] by Lemma 3 and the second equality, but cannot be less than 2P by the first. So using Lemma 3 again we deduce that 2P < q2 - 1. However q2 - 1 < Mp - 1= 2P - 2 and we have a contradiction.

REFERENCE

1. M. I. Rosen, A Proof of the Lucas-Lehmer Test, Amer. Math. Monthly, 95 (1988), [Annotation 14] 855-856.

Department of Pure Mathematics The University of Liverpool L69 3BX, UNITED KINGDOM

1993] A REALLY TRIVIAL PROOF OF THE LUCAS-LEHMER TEST 371

This content downloaded from 128.240.225.120 on Fri, 20 Jun 2014 11:54:59 AM All use subject to JSTOR Terms and Conditions

---

Source: [Fermat's Library](https://fermatslibrary.com/) — https://fermatslibrary.com/s/a-really-trivial-proof-of-the-lucas-lehmer-test. More annotated papers: https://fermatslibrary.com/llms.txt
