The Lucas–Lehmer test (LLT) is a primality test for Mersenne number...
A basic theorem about Mersenne numbers states that if $M_p$ is prim...
In pseudocode, the test might be written as ``` // Determine i...
Is the theorem if and only if?
The $\textbf{overall idea of this proof}$ is to start by assuming t...
To prove that this result is equivalent to $S_m = S^2_{m-1}-2$ we j...
For $X^*$ to form a group we just need to prove the Closure propert...
The order of a group is the number of elements in that group and th...
The set of all integers which have the same remainder when divided ...
Note that $Z_q$ has $q$ elements: {$\bar 0, \bar 1, \bar 2, ..., \o...
Don't forget that we chose $q$ above as a prime divisor of $M_p$ an...
Note that $\bar w w = 1$ and so $w \in X^*$
Hi, I am not getting how the order of $\omega$ is $2^p$. In the...
If you want to read Rosen's original paper click [here](http://ferm...
A
Really Trivial Proof of the
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
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 well-
known) 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
-
2.
Theorem
1
(LUCAS-LEHMER).
Let
p
be a
prime
number. Then
Mp
=
2P
-
1
is
a
prime if
Mp
diuides
Sp_
1.
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:
2m`-1
-2m-1
Lemma
1.
Sm
=
2
+
s2m
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
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
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.
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
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
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
multiplica-
tion, 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
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
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
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),
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

Discussion

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. 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") Yes, if $M_p$ doesn't divide $S_{p-1}$ it's not prime. $(2+\sqrt{3})(2-\sqrt{3})=2^2 - \sqrt{3}^2 = 4 - 3 = 1$ Is the theorem if and only if? Note that $\bar w w = 1$ and so $w \in X^*$ 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$) 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 $$ 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. Does the . operator here represents a binary operation or the multiplication operation ? 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! Does the . operator here represents a binary operation or the multiplication operation ? 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$. 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$. 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$. 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$. If you want to read Rosen's original paper click [here](http://fermatslibrary.com/s/a-proof-of-the-lucas-lehmer-test) 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*} 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$? 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! 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.