[ Pobierz całość w formacie PDF ]
number n is prime is
2
H" .
log n
Thus the probability that Mp is prime is
2
H" .
p log 2
So the expected number of Mersenne primes is
2 1
H"
log 2 pn
where pn is the nth prime.
But again by the Prime Number Theorem
pn H" n log n.
Thus the expected number of Mersenne primes is
2 1
H" = ",
log 2 n log n
since
1
n log n
diverges, eg by comparison with
X
1
= log log X + C.
x log x
374 4 3
4.1.1 The Lucas-Lehmer test
Mersenne numbers are important because there is a simple test, announced by
Lucas and proved rigorously by Lehmer, for determining whether or not Mp is
prime. (There are many necessary tests for primality, eg if p is prime then
2p a" 2 mod p.
What is rare is to find a necessary and sufficient test for the primality of numbers
in a given class, and one which is moreover relatively easy to implement.) For this
reason, all recent record primes have been Mersenne primes.
We shall give two slightly different versions of the Lucas-Lehmer test. The
first is only valid if p a" 3 mod 4, while the second applies to all Mersenne num-
bers. The two tests are very similar, and equally easy to implement. We are giving
the first only because the proof of its validity is rather simpler. So it should be
viewed as an introduction to the second, and true, Lucas-Lehmer test.
"
Both proofs are based on arithmetic in quadratic fields: the first in Q( 5), and
"
the second in Q( 3); and both are based on the following result.
"
Proposition 4.2 Suppose is an integer in the field Q( m); and suppose P is
an odd prime with P m. Then
P
if = 1,
m
P a"
P
if = -1.
ó
m
Proof Suppose
"
= a + b m,
where a, b are integers if m a" 1 mod 4, and half-integers if m a" 1 mod 4.
In fact these cases do not really differ; for 2 is invertible modP , so we may
consider a as an integer modP if 2a " Z. Thus
" "
P P P -1
2
P a" aP + aP -1b m + aP -2bm + + bP m m mod P.
1 2
Now
P
P |
r
if 1 d" r d" P - 1. Hence
"
P -1
2
P a" aP + bP m m mod P
By Fermat s Little Theorem,
aP a" a mod P, bP a" b mod P.
374 4 4
Also
P -1 m
2
m a" mod P,
P
by Proposition 3.15. Thus
"
P
P a" a + b m mod P,
m
ie
m
= 1 =! P a" mod P,
P
m
= -1 =! P a" mod P.
P
"
Corollary 4.1 For all integers in Q( m,
2
P a" mod P.
We may regard this as the analogue of Fermat s Little Theorem
aP a" a mod P
for quadratic fields.
There is another way of establishing this result, which we shall sketch briefly.
It depends on considering the ring
A = Z[]/(P ).
formed by the remainders
mod P
"
of integers in Q( m).
2
There are P elements in this ring, since each " Z[] is congruent modP
to just one of the numbers
"
a + b m
where a, b " Z and
0 d" a, b
"
There are no nilpotent elements in the ring A if P m; for if = a + b m
then
P | 2 =! P | 2ab, P | a2 + b2m
=! P | a, b.
Thus
2 a" 0 mod P =! a" 0 mod P,
374 4 5
from which it follows that, if n > 0,
n a" 0 mod P =! a" 0 mod P,
A ring without non-zero nilpotent elements is said to be semi-simple. It is not
hard to show that a finite semi-simple commutative ring is a direct sum of fields.
Now there is just one field (up to isomorphism) containing pe elements for
each prime power pe, namely the galois field GF(pe). It follows that either
2
1. Z[]/(P ) GF(P ); or
=
2. Z[]/(P ) GF(P ) " GF(P ).
=
The non-zero elements in GF(pe) form a multiplicative group GF(pe) with
pe - 1 elements. It follows from Legendre s Theorem that
e
a = 0 =! ap -1 = 1
in GF(pe). Hence
e
ap = a
for all a " GF(pe).
Thus in the first case,
2
P a"
for all " Z[]/(P ); while in the second case we even have
P a"
for all " Z[]/(P ), since this holds in each of the constituent fields.
In the first case we can go further. The galois field GF(pe) is of characteristic
p, ie
pa = a + a = 0,
for all ainGF(pe). Also, the map
a ! ap
is an automorphism of GF(pe). (This follows by essentially the same argument
that we used above to show that P a" or above.)
In particular, the map
! P mod P
is an automorphism of our field
Z[]/(P ).
On the other hand, the map
!
374 4 6
is also an automorphism of Z[]/(P ), since
P | =! P | .
Moreover, this is the only automorphism of Z[]/(P ) apart from the identity map,
since any automorphism must send
" "
m mod P ! m mod P.
The automorphism
! P mod P
is not the identity map, since the equation
xP - x = 0
has at mos P solutions in the field Z[]/(P ). We conclude that
P a" mod P.
If Z[] is a principal ideal domain the second case arises if and only if P splits,
which by Proposition 3.14 occurs when
m
= 1.
P
Explicitly, if
P = 12,
then
Z[]/(P ) Z[]/(1) " Z[]/(2)
=
= GF(P ) " GF(P ).
Proposition 4.3 Suppose p a" 3 mod 4. Let the sequence rn be defined by
2
r1 = 3, rn+1 = rn - 2.
Then Mp is prime if and only if
Mp | rp-1.
"
Proof We work in the field Q( 5). By Proposition 3.4, the integers in this field
are the numbers
a + b (a, b " Z)
where
"
1 + 5
= .
2
By Proposition 3.9, there is unique factorisation in the ring of integers Z[].
374 4 7
Lemma 4.1 If rn is the sequence defined in the Proposition then
n n
rn = 2 + -2
for each n e" 1.
Proof of Lemma Let us set
n n
sn = 2 + -2
for n e" 0. Then
2
n n
s2 = 2 + -2
n
n+1 n+1
= 2 + 2 + -2
= sn+1 + 2,
ie
sn+1 = s2 - 2.
n
Also
s0 = + -1
= -
"
= 5,
and so
s1 = s2 - 2 = 3.
We conclude that
n n
[ Pobierz całość w formacie PDF ]