[ Pobierz całość w formacie PDF ]
for all n e" 1.
Let us suppose first that Mp is prime. Let us write P = Mp.
Lemma 4.2 We have
5
= -1.
P
Proof of Lemma Since
24 a" 1 mod 5
it follows that
2p a" 23 mod 5
a" 3 mod 5.
374 4 8
Hence
P = 2p - 1 a" 2 mod 5;
and so, by Proposition 3.19,
5
= -1.
P
It follows from this Lemma and Proposition 4.2 that
±P a" ± mod P
¯
for all ± " Z[É]. In particular,
ÉP a" É mod P.
¯
Hence
ÉP +1 a" ÉÉ mod P
¯
a" É mod P a" -1 mod P.
In other words,
p
É2 a" -1 mod P.
Thus
p
É2 + 1 a" 0 mod P.
p-1
Dividing by É2 ,
p-1 p-1
É2 + É-2 a" 0 mod P,
ie
rp-1 a" 0 mod P.
Conversely, suppose P is a prime factor of Mp. Then
Mp | rp-1 =Ò! rp-1 a" 0 mod P
p-1 p-1
=Ò! É2 + É-2 a" 0 mod P
p
=Ò! É2 + 1 a" 0 mod P
p
=Ò! É2 a" -1 mod P.
But this implies that the order of É mod P is 2p+1. For
p+1 p
É2 = (É2 )2 a" 1 mod P,
so if the order of É mod P is d then
d | 2p+1 =Ò! d = 2e
374 4 9
for some e d" p + 1; and if e d" p then
p
É2 a" 1 mod P.
On the other hand, by the Corollary to Proposition 4.2,
2 2
ÉP a" É mod P =Ò! ÉP -1 a" 1 mod P.
Hence
2
2p+1 | P - 1 = (P + 1)(P - 1).
Now
gcd(P + 1, P - 1) = 2.
It follows that
2p | P + 1 or 2p | P - 1.
The latter is impossible since
2p > Mp e" P > P - 1;
while
2p | P + 1 =Ò! 2p d" P + 1 =Ò! Mp = 2p - 1 d" P =Ò! P = Mp.
Now for the true Lucas-Lehmer test. As we shall see, the proof is a little
harder, which is why we gave the earlier version.
Proposition 4.4 Let the sequence rn be defined by
2
r1 = 4, rn+1 = rn - 2.
Then Mp is prime if and only if
Mp | rp-1.
"
Proof We work in the field Q( 3). By Proposition 3.4, the integers in this field
are the numbers
"
a + b 3 (a, b " Z).
"
By Proposition 3.9, there is unique factorisation in the ring of integers Z[ 3].
We set
" "
· = 1 + 3, = 2 + 3.
"
Lemma 4.3 The units in Z[ 3] are the numbers
n
± (n " N).
374 4 10
Proof of Lemma It is sufficient, by Proposition 3.8, to show that is the smallest
unit > 1. And from the proof of that Proposition, we need only consider units of
the form
"
a + b 3
with a, b e" 0.
" "
Thus the only possible units in the range (1, ) are 3 and 1+ 3 = ·, neither
of which is in fact a unit, since
"
3 = -3, · = -2,
whereas a unit must have norm ±1, by Proposition 3.6.
Lemma 4.4 If rn is the sequence defined in the Proposition then
2n-1 -2n-1
rn = +
for each n e" 1.
Proof of Lemma Let us set
2n-1 -2n-1
sn = +
for n e" 1. Then
2n-1 -2n-1 2
s2 = +
n
2n
= + 2 + -2n
= sn+1 + 2,
ie
sn+1 = s2 - 2.
n
Also
s1 = + -1
= + ¯
= 4.
We conclude that
2n-1 -2n-1
rn = sn = +
for all n e" 1.
Suppose first that P = Mp is prime.
Lemma 4.5 We have
3
= -1.
P
374 4 11
Proof of Lemma We have
Mp = 2p - 1
a" (-1)p - 1 mod 3
a" -1 - 1 mod 3
a" 1 mod 3;
while
Mp a" -1 mod 4.
By the Chinese Remainder Theorem there is just one remainder mod12 with
these remainders mod3 and mod4; and that is 7 a" -5 mod 12. For any odd
prime p,
Mp a" 7 mod 12
Hence
3
= -1.
P
by Proposition 3.18,
It follows from this Lemma and Proposition 4.2 that
±P a" ± mod P
¯
"
for all ± " Z[ 3]. In particular,
P
a" ¯ mod P.
Hence
P +1
a" ¯ mod P
a" mod P a" 1 mod P.
In other words,
2p
a" 1 mod P.
It follows that
2p-1
a" ± mod P.
We want to show that in fact
2p-1
a" -1 mod P.
This is where things get a little trickier than in the first version of the Lucas-
Lehmer test. In effect, we need a number with negative norm. To this end we
introduce
"
· = 1 + 3.
Lemma 4.6 1. · = -2.
374 4 12
2. ·2 = 2 .
Proof of Lemma This is a matter of simple verification:
· = 1 - 3 = -2,
while
"
·2 = (1 + 3)2
"
= 4 + 2 3
= 2 .
By Proposition /refMersenneLemma,
·P a" · mod P,
¯
and so
·P +1 a" ·· - 2 mod P,
¯
ie
p
·2 a" -2 mod P.
By the Lemma, this can be written
p-1
(2 )2 a" -2 mod P,
ie
p-1
2p-1
22 a" -2 mod P,
But by Proposition 3.14,
P -1 2
p-1
2
2 = 22 -1 a" mod P
P
a" 1 mod P,
by Proposition 3.17, since
P = 2p - 1 a" -1 mod 8.
Thus
p-1
22 a" 2 mod P
374 4 13
and so
2p-1
2 a" -2 mod P.
Hence
2p-1
a" -1 mod P.
Thus
2p-1
+ 1 a" 0 mod P.
2p-2
Dividing by ,
2p-2 -2p-2
+ a" 0 mod P,
ie
rp-1 a" 0 mod P.
Conversely, suppose P is a prime factor of Mp. Then
Mp | rp-1 =Ò! rp-1 a" 0 mod P
2p-2 -2p-2
=Ò! + a" 0 mod P
2p-1
=Ò! + 1 a" 0 mod P
2p-1
=Ò! a" -1 mod P.
But (by the argument we used in the proof of the first Lucas-Lehmer test) this
implies that the order of mod P is 2p.
On the other hand, by the Corollary to Proposition 4.2,
2 2
P P -1
a" mod P =Ò! a" 1 mod P.
Hence
2
2p | P - 1 = (P + 1)(P - 1).
Now
gcd(P + 1, P - 1) = 2.
It follows that
2p-1 | P + 1 or 2p-1 | P - 1.
In either case,
Mp - 1
2p-1 d" P + 1 =Ò! P e" 2p-1 - 1 =
2
Mp
=Ò! P e"
3
Mp
=Ò!
P
Since Mp is odd, this implies that
P = Mp,
ie Mp is prime.
374 4 14
4.1.2 Perfect numbers
Mersenne numbers are also of interest because of their intimate connection with
perfect numbers.
Definition 4.2 For n " N, n > 0 we denote the number of divisors of n by d(n),
and the sum of these divisors by Ã(n).
Example: Since 12 has divisors 1, 2, 3, 4, 6, 12,
d(12) = 6, Ã(12) = 28.
Definition 4.3 The number n " N is said to be perfect if
Ã(n) = 2n,
ie if n is the sum of its proper divisors.
Example: The number 6 is perfect, since
6 = 1 + 2 + 3.
Proposition 4.5 If
Mp = 2p - 1
is a Mersenne prime then
2p-1(2p - 1)
is perfect.
Conversely, every even perfect number is of this form.
Proof In number theory, a function f(n) defined on {n " N : n > 0} is said to
be multiplicative if
gcd(m, n) = 1 =Ò! f(mn) = f(m)f(n).
If the function f(n) is multiplicative, and
1 r
n = pe · · · pe
1 r
then
1 r
f(n) = f(pe ) · · · f(pe ).
1 r
[ Pobierz całość w formacie PDF ]