[ Pobierz całość w formacie PDF ]
r1 =4
r2 =(42 - 2) mod 31 = 14 mod 31 = 14
r3 =(142 - 2) mod 31 = 194 mod 31 = 8
r4 =(82 - 2) mod 31 = 62 mod 31 = 0.
Hence by the Lucas-Lehmer test, M5 =31 is prime.
Exercise 12.3. Show using the Lucas-Lehmer test that M7 = 127 is prime.
Remark 12.1. Note that the Lucas-Lehmer test for Mp =2p - 1 takes only
p -1 steps. On
other hand, if one attempts to prove Mp prime by testing
all primes ≤
Mp one must consider about 2 steps. This is MUCH larger
than p in general.
2
the
p
2
Chapter 13
The Functions σ and τ
Definition 13.1. For n0 define:
τ(n) = the number of positive divisors of n,
σ(n) = the sum of the positive divisors of n.
Example 13.1. 12 = 3 · 22 has positive divisors
1, 2, 3, 4, 6, 12.
Hence
τ(12) = 6
and
σ(12) =1+2+3+4+6+12=28.
Definition 13.2. A positive divisor d of n is said to be a proper divisor
of n if d n. We denote the sum of all proper divisors of n by σ∗(n).
Note that if n ≥ 2 then
σ∗(n) =σ(n) - n.
Example 13.2. σ∗(12) = 16.
Definition 13.3. n1 is perfect if σ∗(n) =n.
Example 13.3. The proper divisors of 6 are 1, 2 and 3.
Therefore 6 is perfect.
47
So σ∗(6) = 6.
48
CHAPTER 13. THE FUNCTIONS σ AND τ
Exercise 13.1. Prove that 28 is perfect.
The next theorem shows a simple way to compute σ(n) and τ(n) from
the prime factorization of n.
Theorem 13.1. Let
r ≥ 1,
where p1 p2 · · · pr are primes and ei ≥ 0 for each i ∈ {1, 2, . . . , r}.
Then
(1) τ(n) =(e1 +1)(e2 +1) · · · (er +1)
Before proving this let’s look at an example. Take n =72 =8 · 9 =23 · 32.
The theorem says
τ(72) = (3 + 1)(2 + 1) = 12
Lemma 13.1. Let n = ab where a 0, b 0 and gcd(a, b) = 1.
σ(n) =σ(a)σ(b).
Then
Proof. Since a and b have only 1 as a common factor, using the Fundamental
Theorem of Arithmetic it is easy to see that d | ab ⇔ d = d1d2 where d1 | a
1
2
r
1
2
r
n = pe pe · · · pe ,
.
1
1
e2+1
pe
+1 - 1
p2
- 1
pe
+1 - 1
(2) σ(n) =
p1 - 1
p2 - 1
· · ·
r
r
pr - 1
24 - 1
33 - 1
2 - 1
3 - 1
σ(72) =
=15 · 13 = 195.
[Proof of Theorem 13.1 (1)] From the Fundamental Theorem of Arithmetic
every positive factor d of n will have its prime factors coming from those of
n. Hence d | n iff d = pf pf · · · pf where for each i:
0 ≤ fi ≤ ei.
That is, for each fi we can choose a value in the set of ei +1 numbers
{0, 1, 2, . . . , ei}. So, in all, there are (e1 +1)(e2 +1) · · · (er + 1) choices for
the exponents f1, f2, . . . , fr. So (1) holds.
[Proof of (2)] We first establish two lemmas.
1
2
1
2
r
r
49
and d2 | b. That is, the divisors of ab are products of the divisors of a and
the divisors of b. Let
1, a1, . . . , as
denote the divisors of a and let
1, b1, . . . , bt
denote the divisors of b. Then
σ(a) =1 +a1 + a2 + · · · + as,
σ(b) =1 +b1 + b2 + · · · + bt.
The divisors of n = ab can be listed as follows
1, b1, b2, . . . , bt,
a1 · 1, a1 · b1, a1 · b2, . . . , a1 · bt,
a2 · 1, a2 · b1, a2 · b2, . . . , a2 · bt,
.
.
.
as · 1, as · b1, as · b2, . . . , as · bt.
It is important to note that since gcd(a, b) = 1, aibj = akb implies that
ai = ak and bj = b . That is there are no repetitions in the above array.
If we sum each row we get
1+b1 + · · · + bt = σ(b)
a11+a1b1 + · · · + a1bt = a1σ(b)
.
.
.
as · 1+asb1 + · · · + asbt = asσ(b).
By adding these partial sums together we get
σ(n) =σ(b) +a1σ(b) +a2σ(b) +· · · + a3σ(b)
=(1 +a1 + a2 + · · · + as)σ(b)
= σ(a)σ(b).
This proves the lemma.
50
CHAPTER 13. THE FUNCTIONS σ AND τ
Lemma 13.2. If p is a prime and k ≥ 0 we have
.
Proof. Since p is prime, the divisors of pk are 1, p, p2, . . . , pk. Hence
σ(pk) =1 +p + p2 + · · · + pk =
,
p - 1
as desired.
Proof of Theorem 13.1 (2) (continued). Let n = pe pe · · · pe . Our proof is
by induction on r. If r =1, n = pe and the result follows from Lemma 13.2.
Suppose the result is true when 1 ≤ r ≤ k. Consider now the case r = k +1.
That is, let
and by Lemma 13.2
and it follows that
σ(n) =
1
.
So the result holds for r = k + 1. By PMI it holds for r ≥ 1.
Exercise 13.2. Find σ(n) and τ(n) for the following values of n.
(1) n = 900
(2) n = 496
(3) n =32
pk+1 - 1
p - 1
σ(pk) =
pk+1 - 1
1
2
1
2
r
r
1
1
k+1
1
k
n = pe · · · pe pe
1
k
k+1
where the primes p1, . . . , pk, pk+1 are distinct and ei ≥ 0. Let a = pe · · · pe ,
b = pe
. Clearly gcd(a, b) = 1. So by Lemma 13.1 we have σ(n) =σ(a)σ(b).
By the induction hypothesis
pe
+1 - 1
pe
+1 - 1
p1 - 1
pk - 1
1
k
1
k
k+1
k+1
1
k
σ(a) =
· · ·
1
k
k+1
k+1
pe
+1 - 1
σ(b) =
pk+1 - 1
1
pe
+1 - 1
p1 - 1
1
· · ·
k+1
k+1
pe
+1 -
pk+1 - 1
51
(4) n = 128
(5) n = 1024
Exercise 13.3. Determine which (if any) of the numbers in Exercise 13.2
are perfect.
Exercise 13.4. Does Lemma 13.1 hold if we replace σ by σ∗? [Hint: The
answer is no, but find explicit numbers a and b such that the result fails yet
gcd(a, b) =1.]
52
CHAPTER 13. THE FUNCTIONS σ AND τ
Chapter 14
Perfect
Primes
Numbers and Mersenne
If you do a search for perfect numbers up to 10, 000 you will find only the
following perfect numbers:
6 =2 · 3,
[ Pobierz całość w formacie PDF ]