|
II Solutions, 9. Some Special Problems in Number Theory
might try to see whether this number divides 12
2
15
+
1. Let
q
=
2
16
+
1. Then
12
2
15
+
1
=
2
q
−
1
·
3
q
−
1
2
+
1
≡
3
q
−
1
2
+
1
(
mod
q
).
It remains to see whether
(
3
/
q
)
= −
1. The answer is positive (use the quad-
ratic reciprocity law), so indeed 3
(
q
−
1
)/
2
+
1
≡
0
(
mod 2
)
and 2
16
+
1 is the
smallest prime factor of the number 12
2
15
+
1.
9.2
Special Numbers
9.2.1
Fermat Numbers
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)
Solution.
The answer is all
n
=
2
k
, where
k
=
1
,
2
, . . .
.
First observe that 2
≡ −
1
(
mod 3
)
. Hence 3
|
2
n
−
1 if and only if
n
is even.
Suppose, by way of contradiction, that
l
≥
3 is a positive odd divisor of
n
.
Then 2
l
−
1 is not divisible by 3 but it is a divisor of 2
n
−
1, so it is a divisor of
4
m
2
+
1 as well. On the other hand, 2
l
−
1 has a prime divisor
p
of the form 4
r
+
3.
Then
(
2
m
)
2
≡ −
1
(
mod 4
r
+
3
)
, but we have that a square cannot be congruent
to
−
1 modulo a prime of the form 4
r
+
3 (see also Problem 1 in Section 7.1).
Therefore,
n
is indeed of the form 2
k
for
k
≥
1. For such
n
, we have
2
n
−
1
3
=
(
2
2
1
+
1
)(
2
2
2
+
1
)(
2
2
3
+
1
)
· · ·
(
2
2
k
−
1
+
1
).
The factors on the right side are all relatively prime, since they are Fermat
numbers. Therefore by the Chinese remainder theorem, there is a positive integer
c
simultaneously satisfying
c
≡
2
2
i
−
1
(
mod 2
2
i
+
1
)
for all
i
=
1
,
2
, . . . ,
k
−
1
and
c
≡
0
(
mod 2
)
. Putting
c
=
2
m
, 4
m
2
+
1 is a multiple of
2
n
−
1
3
, as desired.
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)
Solution.
From Problem 9.2.3 we can write
f
n
=
s
i
=
1
(
1
+
2
n
+
2
r
i
)
k
i
,
(
1
)
9.2. Special Numbers
333
where
p
i
=
1
+
2
n
+
2
r
i
are distinct primes and
k
i
≥
1. Taking relation (1) modulo
4
n
+
2
, it follows that
0
≡
s
i
=
1
k
i
r
i
(
mod 2
n
+
2
),
and hence
s
i
=
1
k
i
r
i
≥
2
n
+
2
.
From (1) it is clear that
f
n
≥
(
1
+
2
n
+
2
)
k
1
+···+
k
s
;
hence
k
1
+ · · · +
k
s
≤
lg
(
1
+
2
2
n
)
lg
(
1
+
2
n
+
2
)
,
where lg
x
is log
2
x
.
It follows that
2
n
+
2
≤
max
1
≤
i
≤
s
r
i
s
j
=
1
k
j
≤
max
1
≤
i
≤
s
r
i
lg
(
1
+
2
2
n
)
lg
(
1
+
2
n
+
2
)
.
Assume that
max
1
≤
i
≤
s
r
i
≤
n
. Applying the last inequality, we get
2
n
+
2
≤
n
lg
(
1
+
2
2
n
)
lg
(
1
+
2
n
+
2
)
<
n
lg
(
1
+
2
2
n
)
(
n
+
2
)
lg 2
,
i.e.,
n
+
2
n
·
2
n
+
2
<
log
2
(
1
+
2
2
n
),
hence 2
2
n
+
2
<
1
+
2
2
n
, a contradiction. Therefore max
1
≤
i
≤
s
r
i
≥
n
+
1, and
max
1
≤
i
≤
s
p
i
>
2
n
+
2
(
n
+
1
)
.
9.2.2
Mersenne Numbers
Problem 9.2.7.
Let P
∗
denote the set of all 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
).
Find all such possible values of p.
(1999 Taiwanese Mathematical Olympiad)
334
II Solutions, 9. Some Special Problems in Number Theory
Solution.
Direct calculation shows that the set
T
of Mersenne primes less that
10000 is
{
M
2
,
M
3
,
M
5
,
M
7
,
M
13
} = {
3
,
7
,
31
,
127
,
8191
}
.
The number 2
11
−
1 is not prime; it equals 23
·
89. We claim that this is the set of
all possible values of
p
.
If some prime
p
is not in
T
, then look at the set
S
=
T
. Then there must be
some prime
q
∈
S
less than 10000 such that
(
q
+
1
)
|
(
M
2
+
1
)(
M
3
+
1
)(
M
5
+
1
)(
M
7
+
1
)(
M
13
+
1
)
=
2
30
.
Thus,
q
+
1 is a power of 2 and
q
is a Mersenne prime less than 10000, and
therefore
q
∈
T
=
S
, a contradiction.
On the other hand, suppose
p
is in
T
. Suppose we have a set
S
= {
p
1
,
p
2
, . . .
,
p
k
} ⊆
P
∗
not including
p
, with
k
≥
2 and
p
1
<
p
2
<
· · ·
<
p
k
. Suppose, by
way of contradiction that for all
q
∈
P
∗
such that
(
q
+
1
)
|
(
p
1
+
1
)
· · ·
(
p
k
+
1
)
,
we have
q
∈
S
. Then
4
|
(
p
1
+
1
)(
p
2
+
1
)
⇒
M
2
∈
S
,
8
|
(
M
2
+
1
)(
p
2
+
1
)
⇒
M
3
∈
S
,
32
|
(
M
2
+
1
)(
M
3
+
1
)
⇒
M
5
∈
S
,
128
|
(
M
2
+
1
)(
M
5
+
1
)
⇒
M
7
∈
S
,
8192
|
(
M
3
+
1
)(
M
5
+
1
)(
M
7
+
1
)
⇒
M
13
∈
S
.
Then
p
, a Mersenne prime under 10000, must be in
S
, a contradiction. There-
fore there is some prime
q
<
10000 not in
S
with
q
+
1
|
(
p
1
+
1
)
· · ·
(
p
k
+
1
)
,
as desired. This completes the proof.
9.2.3
Perfect Numbers
Problem 9.2.9.
Prove that if n is an even perfect number, then
8
n
+
1
is a perfect
square.
Solution.
From Problem 1, we have
n
=
m
(
m
+
1
)
2
for some positive integer
m
;
hence
8
n
+
1
=
4
m
(
m
+
1
)
+
1
=
(
2
m
+
1
)
2
.
Problem 9.2.10.
Show that if k is an odd positive integer, then
2
k
−
1
M
k
can be
written as the sum of the cubes of the first
2
k
−
1
2
odd positive integers. In particular,
any perfect number has this property.
Solution.
Standard summation formulas verify that
n
i
=
1
(
2
i
−
1
)
3
=
n
2
(
2
n
2
−
1
).
9.3. Sequences of Integers
335
With
n
=
2
k
−
1
2
, the right-hand side becomes 2
k
−
1
(
2
k
−
1
)
; that is, 2
k
−
1
M
k
,
and we are done.
Do'stlaringiz bilan baham: |
