[ 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 ]
