|
9.2. Special Numbers
177
For a different proof we can use directly the identity
x
2
n
−
1
x
−
1
=
n
−
1
k
=
0
(
x
2
k
+
1
).
(ii) From (i) we have
gcd
(
f
n
,
f
0
)
=
gcd
(
f
n
,
f
1
)
= · · · =
gcd
(
f
n
,
f
n
−
1
)
=
1
for all
n
≥
1; hence gcd
(
f
k
,
f
h
)
=
1 for all
k
=
h
.
(iii) Because
f
1
=
5 and
f
0
· · ·
f
n
−
1
is odd, using (i), it follows that
f
n
ends
in 5
+
2
=
7 for all
n
≥
2.
Problem 9.2.2.
Find all Fermat numbers that can be written as a sum of two
primes.
Solution.
All Fermat numbers are odd. If
f
n
=
p
+
q
for some primes
p
and
q
,
p
≤
q
, then
p
=
2 and
q
>
2. We obtain
q
=
2
2
n
−
1
=
2
2
n
−
1
2
−
1
=
2
2
n
−
1
−
1
2
2
n
−
1
+
1
;
hence 2
2
n
−
1
−
1 must equal 1. That is,
n
=
1 and
f
1
=
2
+
3 is the unique Fermat
number with this property.
An alternative solution uses Problem 1 (iii): if
n
≥
2, then
f
n
ends in 7, so
q
must end in 5. Hence
q
=
5 and 2
+
5
=
f
n
for
n
≥
2. The only Fermat number
with the given property is
f
1
.
Problem 9.2.3.
Show that for any n
≥
2
the prime divisors p of f
n
are of the form
p
=
s
·
2
n
+
2
+
1
.
Solution.
Because
p
|
f
n
, it follows that 2
2
n
≡ −
1
(
mod
p
)
. Hence squaring
gives 2
2
n
+
1
≡
1
(
mod
p
)
. Thus
o
p
(
2
)
|
2
n
+
1
. Since 2
2
n
≡
1
(
mod
p
)
, we have
o
p
(
2
)
=
2
n
+
1
. Thus 2
n
+
1
|
p
−
1. Hence
p
≡
1
(
mod 8
)
and
2
p
=
1. So 2
is a quadratic residue mod
p
and there is some
a
with
a
2
≡
2
(
mod
p
)
. Hence
o
p
(
a
)
=
2
n
+
2
and 2
n
+
2
|
p
−
1, that is,
p
=
s
·
2
n
+
2
+
1 for some
s
.
Additional Problems
Problem 9.2.4.
Find all positive integers
n
such that 2
n
−
1 is a multiple of 3 and
2
n
−
1
3
is a divisor of 4
m
2
+
1 for some integer
m
.
(1999 Korean Mathematical Olympiad)
Problem 9.2.5.
Prove that the greatest prime factor of
f
n
,
n
≥
2, is greater than
2
n
+
2
(
n
+
1
)
.
(2005 Chinese International Mathematical Olympiad Team Selection Test)
178
I Fundamentals, 9. Some Special Problems in Number Theory
9.2.2
Mersenne Numbers
The integers
M
n
=
2
n
−
1,
n
≥
1, are called
Mersenne
2
numbers
. It is clear that
if
n
is composite, then so is
M
n
. Moreover, if
n
=
ab
, where
a
and
b
are integers
greater than 1, then
M
a
and
M
b
both divide
M
n
. But there are primes
n
for which
M
n
is composite, for example 47
|
M
23
, 167
|
M
83
, 263
|
M
131
, and so on.
It is not known if there are infinitely many primes with this property. The
largest known prime is
2
32582657
−
1
,
and it is a Mersenne number. Presently, we know 42 Mersenne numbers that are
primes.
Theorem 9.2.1.
Let p be an odd prime and let q be a prime divisor of M
p
. Then
q
=
2
kp
+
1
for some positive integer k.
Proof.
From the congruence 2
p
≡
1
(
mod
q
)
and from the fact that
p
is a prime,
it follows that
p
is the least positive integer satisfying this property. Using Fer-
mat’s little theorem, we have 2
q
−
1
≡
1
(
mod
q
)
, and hence
p
|
q
−
1. But
q
−
1
is an even integer, so
q
−
1
=
2
kp
, and the conclusion follows.
Problem 9.2.6.
Let p be a prime of the form
4
k
+
3
. Then
2
p
+
1
is a prime if
and only if
2
p
+
1
divides M
p
.
Solution.
Suppose that
q
=
2
p
+
1 is a prime. Then
2
q
=
(
−
1
)
q
2
−
1
8
=
(
−
1
)
p
(
p
+
1
)
2
=
(
−
1
)
2
(
k
+
1
)(
4
k
+
3
)
=
1
;
hence 2 is a quadratic residue mod
q
.
Using Euler’s criterion, it follows that 2
q
−
1
2
≡
1
(
mod
q
)
, that is, 2
p
≡
1
(
mod
q
)
, and the conclusion follows.
If
q
is composite, then it has a prime divisor
q
1
such that
q
1
≤ √
q
. Using
Fermat’s little theorem, we have 2
q
1
−
1
≡
1
(
mod
q
1
)
. But 2
p
≡
1
(
mod
q
1
)
with
p
prime implies that
p
is the least positive integer with the property. Hence
p
|
q
1
−
1, and thus
q
1
≥
p
+
1
>
√
p
, contradicting the choice of
q
1
. Therefore
q
must be a prime and the conclusion follows.
Additional Problems
Problem 9.2.7.
Let
P
∗
denote all the odd primes less than 10000, and suppose
p
∈
P
∗
. For each subset
S
= {
p
1
,
p
2
, . . . ,
p
k
}
of
P
∗
, with
k
≥
2 and not
including
p
, there exists a
q
∈
P
∗
\
S
such that
(
q
+
1
)
|
(
p
1
+
1
)(
p
2
+
1
)
· · ·
(
p
k
+
1
).
2
Marin Mersenne (1588–1648), French monk who is best known for his role as a clearing house
for correspondence with eminent philosophers and scientists and for his work in number theory.
9.2. Special Numbers
179
Find all such possible values of
p
.
(1999 Taiwanese Mathematical Olympiad)
9.2.3
Perfect Numbers
An integer
n
≥
2 is called
perfect
if the sum of its divisors is equal to 2
n
. That
is,
σ (
n
)
=
2
n
. For example, the numbers 6, 28, 496 are perfect. The even perfect
numbers are closely related to Mersenne numbers. It is not known whether any
odd perfect numbers exist.
Theorem 9.2.2.
(Euclid)
If M
k
is a prime, then n
=
2
k
−
1
M
k
is a perfect number.
Proof.
Because gcd
(
2
k
−
1
,
2
k
−
1
)
=
1, and the fact that
σ
is a multiplicative
function, it follows that
σ (
n
)
=
σ (
2
k
−
1
)σ(
2
k
−
1
)
=
(
2
k
−
1
)
·
2
k
=
2
n
.
There is also a partial converse, due to Euler.
Theorem 9.2.3.
If the even positive integer n is perfect, then n
=
2
k
−
1
M
k
for
some positive integer k for which M
k
is a prime.
Proof.
Let
n
=
2
t
u
, where
t
≥
1 and
u
is odd. Because
n
is perfect, we have
σ (
n
)
=
2
n
; hence
σ(
2
t
u
)
=
2
t
+
1
u
. Using again that
σ
is multiplicative, we get
σ(
2
t
u
)
=
σ (
2
t
)σ (
u
)
=
(
2
t
+
1
−
1
)σ(
u
).
This is equivalent to
(
2
t
+
1
−
1
)σ(
u
)
=
2
t
+
1
u
.
Because gcd
(
2
t
+
1
−
1
,
2
t
+
1
)
=
1, it follows that 2
t
+
1
|
σ(
u
)
; hence
σ (
u
)
=
2
t
+
1
v
for some positive integer
v
. We obtain
u
=
(
2
t
+
1
−
1
)v
.
The next step is to show that
v
=
1. If
v >
1, then
σ(
u
)
≥
1
+
v
+
2
t
+
1
−
1
+
v(
2
t
+
1
−
1
)
=
(v
+
1
)
2
t
+
1
> v
·
2
t
+
1
=
σ (
u
),
a contradiction. We get
v
=
1; hence
u
=
2
t
+
1
−
1
=
M
t
+
1
and
σ (
u
)
=
2
t
+
1
.
If
M
t
+
1
is not a prime, then
σ(
u
) >
2
t
+
1
, which is impossible. Finally,
n
=
2
k
−
1
M
k
, where
k
=
t
+
1.
Remark.
Recall that
M
k
is a prime only if
k
is a prime. This fact reflects also in
Theorem 9.2.2 and Theorem 9.2.3.
Problem 9.2.8.
Show that any even perfect number is triangular.
Solution.
Using Theorem 9.2.3, we have
n
=
2
k
−
1
M
k
=
2
k
2
(
2
k
−
1
)
=
m
(
m
+
1
)
2
,
where
m
=
2
k
−
1 and we are done.
180
Do'stlaringiz bilan baham: |
