158 III More on Divisibility
The sufficiency of the condition in Proposition 30 was proved in Euclid’sElements
(Book IX, Proposition 36). The necessity of the condition was proved over two thou-
sand years later by Euler. The condition is quite restrictive. In the first place, if 2m−1is
prime for somem∈N,thenmmust itself be prime. For, ifm=rs,where1<r<m,
then witha= 2 swe have
2 m− 1 =ar− 1 =(a− 1 )(ar−^1 +ar−^2 +···+ 1 ).A prime of the formMp := 2 p−1issaidtobeaMersenne primein honour
of Mersenne (1644), who gave a list of all primesp≤257 for which, he claimed,
Mpwas prime. However, he included two values ofpfor whichMpis composite and
omitted three values ofpfor whichMpis prime. The correct list is now known to be
p= 2 , 3 , 5 , 7 , 13 , 17 , 19 , 31 , 61 , 89 , 107 , 127.The first four even perfect numbers, namely 6, 28 ,496 and 8128, which correspond to
the valuesp= 2 , 3 ,5 and 7, were known to the ancient Greeks.
ThatM 11 is not prime follows from 2^11 − 1 = 2047 = 23 ×89. The factor 23
is not found simply by guesswork. It was already known to Fermat (1640) that ifp
is an odd prime, then any divisor ofMpis congruent to 1 mod 2p. It is sufficient to
establish this for prime divisors. But ifqis a prime divisor ofMp,then2p≡1modq.
Hence the order of 2 inF×qdividespand, since it is not 1, it must be exactlyp. Hence,
by Lemma II.31 withG=F×q,pdividesq−1. Thusq ≡1modpand actually
q≡1mod2p,sinceqis necessarily odd.
The least 39 Mersenne primes are now known. The hunt for more uses thousands
of linked personal computers and the following test, which was stated by Lucas (1878),
but first completely proved by D.H. Lehmer (1930):
Proposition 31Define the sequence(Sn)recurrently by
S 1 = 4 , Sn+ 1 =S^2 n− 2 (n≥ 1 ).Then, for any odd prime p, Mp:= 2 p− 1 is prime if and only if it divides Sp− 1.
Proof Put
ω= 2 +√
3 ,ω′= 2 −√
3.
Sinceωω′=1, it is easily shown by induction that
Sn=ω^2n− 1
+ω′^2n− 1
(n≥ 1 ).Letqbe a prime and letJdenote the set of all real numbers of the forma+b√
3,
wherea,b ∈ Z. EvidentlyJ is a commutative ring. By identifying two elements
a+b
√
3anda ̃+b ̃√
3ofJwhena≡ ̃aandb≡b ̃modq, we obtain a finite commu-
tative ringJqcontainingq^2 elements. The setJq×of all invertible elements ofJqis a
commutative group containing at mostq^2 −1 elements, since 0∈/Jq×.