|
I Fundamentals, 9. Some Special Problems in Number Theory
Solution.
Assume that we have a prime
p
such that
p
|
2
n
+
1 and
p
≡ −
1
(
mod 8
)
. If
n
is even, then
p
≡
3
(
mod 4
)
and
−
1
p
=
1, a contradiction. If
n
is odd, 2
n
≡ −
1
(
mod
p
)
, and so
−
2
≡
(
2
n
+
1
2
)
2
(
mod
p
)
; hence
−
2
p
=
1. We
get
(
−
1
)
p
2
−
1
8
(
−
1
)
p
−
1
2
=
1, again a contradiction.
Problem 9.1.5.
Prove that
2
3
n
+
1
has at least n prime divisors of the form
8
k
+
3
.
Solution.
Using the result of the previous problem, we deduce that 2
n
+
1 does
not have prime divisors of the form 8
k
+
7. We will prove that if
n
is odd, then it
has no prime divisors of the form 8
k
+
5 either. Indeed, let
p
be a prime divisor of
2
n
+
1. Again we have 2
n
≡ −
1
(
mod
p
)
and so
−
2
≡
(
2
n
+
1
2
)
2
(
mod
p
)
. Using
the same argument as the one in the previous problem, we deduce that
p
2
−
1
8
+
p
−
1
2
is even, which cannot happen if
p
is of the form 8
k
+
5.
Now, let us solve the additional problem. We will assume
n
>
2 (otherwise,
the verification is trivial). The essential observation is the identity
2
3
n
+
1
=
(
2
+
1
)(
2
2
−
2
+
1
)(
2
2
·
3
−
2
3
+
1
)
· · ·
(
2
2
·
3
n
−
1
−
2
3
n
−
1
+
1
).
Now we will prove that for all 1
≤
i
<
j
≤
n
−
1,
gcd
(
2
2
·
3
i
−
2
3
i
+
1
,
2
2
·
3
j
−
2
3
j
+
1
)
=
3
.
Indeed,
2
3
j
=
(
2
3
i
+
1
)
3
j
−
i
−
1
≡
(
−
1
)
3
j
−
i
−
1
≡ −
1
(
mod 2
3
i
+
1
+
1
),
implying
2
2
·
3
j
−
2
3
j
+
1
≡
3
(
mod 2
3
i
+
1
+
1
).
Therefore the greatest common divisor is at most 3. Since
2
2
·
3
i
−
2
3
i
+
1
≡
1
−
(
−
1
)
+
1
=
3
(
mod 3
),
both quantities are divisible by 3 and therefore the greatest common divisor is 3,
as claimed.
It remains to show that each of the numbers 2
2
·
3
i
−
2
3
i
+
1, with 1
≤
i
≤
n
−
1
has at least one prime divisor of the form 8
k
+
3 different from 3. It would follow in
this case that 2
3
n
+
1 has at least
n
−
1 distinct prime divisors of the form 8
k
+
3
(from the previous remarks), and since it is also divisible by 3, the conclusion
would follow. Fix
i
∈ {
1
,
2
, . . . ,
n
−
1
}
and observe that any prime factor of
2
2
·
3
i
−
2
3
i
+
1, is also a prime factor of 2
3
n
+
1, and thus, from the first remark, it
must be of the form 8
k
+
1 or 8
k
+
3. Because
v
3
(
2
2
·
3
i
−
2
3
i
+
1
)
=
1, it follows
that if all prime divisors of 2
2
·
3
i
−
2
3
i
+
1 except for 3 are of the form 8
k
+
1,
9.1. Quadratic Residues; the Legendre Symbol
175
then 2
2
·
3
i
−
2
3
i
+
1
≡
3
(
mod 8
)
, which is clearly impossible. Thus at least one
prime divisor of 2
2
·
3
i
−
2
3
i
+
1 is different from 3 and is of the form 8
k
+
3, and
so the claim is proved. The conclusion follows.
Problem 9.1.6.
Find a number n between
100
and
1997
such that n
|
2
n
+
2
.
(1997 Asian-Pacific Mathematical Olympiad)
Solution.
The first step would be choosing
n
=
2
p
, for some prime number
p
.
Unfortunately, this cannot work by Fermat’s little theorem. So let us try setting
n
=
2
pq
, with
p
,
q
different prime numbers. We need
pq
|
2
2
pq
−
1
+
1, and so we
must have
−
2
p
=
−
2
q
=
1. Also, using Fermat’s little theorem,
p
|
2
2
q
−
1
+
1
and
q
|
2
2
p
−
1
+
1. A small verification shows that
q
=
3
,
5
,
7 are not good
choices, so let us try
q
=
11. In this case we obtain
p
=
43, and so it suffices
to show that
pq
|
2
2
pq
−
1
+
1 for
q
=
11 and
p
=
43. This is immediate, since
the hard work has already been completed: we have shown that it suffices to have
p
|
2
2
q
−
1
,
q
|
2
2
p
−
1
+
1, and
−
2
p
=
−
2
q
=
1 in order to have
pq
|
2
2
pq
−
1
+
1.
But as one can easily check, all these conditions are satisfied, and the number
2
·
11
·
43
=
946 is a valid answer.
Additional Problems
Problem 9.1.7.
Let
f
,
g
:
Z
+
→
Z
+
functions with the following properties:
(i)
g
is surjective;
(ii) 2
f
2
(
n
)
=
n
2
+
g
2
(
n
)
for all positive integers
n
.
If, moreover,
|
f
(
n
)
−
n
| ≤
2004
√
n
for all
n
, prove that
f
has infinitely many
fixed points.
(2005 Moldavian International Mathematical Olympiad Team Selection Test)
Problem 9.1.8.
Suppose that the positive integer
a
is not a perfect square. Then
a
p
= −
1 for infinitely many primes
p
.
Problem 9.1.9.
Suppose that
a
1
,
a
2
, . . . ,
a
2004
are nonnegative integers such that
a
n
1
+
a
n
2
+ · · · +
a
n
2004
is a perfect square for all positive integers
n
. What is the
minimal number of such integers that must equal 0?
(2004 Mathlinks Contest)
Problem 9.1.10.
Find all positive integers
n
such that 2
n
−
1
|
3
n
−
1.
(American Mathematical Monthly)
Problem 9.1.11.
Find the smallest prime factor of 12
2
15
+
1.
176
I Fundamentals, 9. Some Special Problems in Number Theory
9.2
Special Numbers
9.2.1
Fermat Numbers
Trying to find all primes of the form 2
m
+
1, Fermat noticed that
m
must be a
power of 2. Indeed, if
m
equaled
k
·
h
with
k
an odd integer greater than 1, then
2
m
+
1
=
(
2
h
)
k
+
1
=
(
2
h
+
1
)(
2
h
(
k
−
1
)
−
2
h
(
k
−
2
)
+ · · · −
2
h
+
1
),
and so 2
m
+
1 would not be a prime.
The integers
f
n
=
2
2
n
+
1,
n
≥
0, are called
Fermat numbers
. We have
f
0
=
3
,
f
1
=
5
,
f
2
=
17
,
f
3
=
257
,
f
4
=
65
,
573
.
After checking that these five numbers are primes, Fermat conjectured that
f
n
is a prime for all
n
. But Euler proved that 641
|
f
5
. His argument was the
following:
f
5
=
2
32
+
1
=
2
28
(
5
4
+
2
4
)
−
(
5
·
2
7
)
4
+
1
=
2
28
·
641
−
(
640
4
−
1
)
=
641
2
28
−
639
(
640
2
+
1
)
.
It is still an open problem whether there are infinitely many Fermat primes.
Also, the question whether there are any Fermat primes after
f
4
is still open. The
answer to this question is important, because Gauss proved that a regular polygon
Q
1
Q
2
. . .
Q
n
can be constructed using only a straightedge and compass if and
only if
n
=
2
h
p
1
· · ·
p
k
, where
k
≥
0 and
p
1
, . . . ,
p
k
are distinct Fermat primes.
Gauss was the first to construct such a polygon for
n
=
17.
Problem 9.2.1.
Prove that for f
n
, the nth Fermat number,
(i) f
n
=
f
0
· · ·
f
n
−
1
+
2
,
n
≥
1
;
(ii)
gcd
(
f
k
,
f
h
)
=
1
if k
=
h;
(iii) f
n
ends in
7
for all n
≥
2
.
Solution.
(i) We have
f
k
=
2
2
k
+
1
=
2
2
k
−
1
2
+
1
=
(
f
k
−
1
−
1
)
2
+
1
=
f
2
k
−
1
−
2
f
k
−
1
+
2
;
hence
f
k
−
2
=
f
k
−
1
(
f
k
−
1
−
2
),
k
≥
1
.
(
1
)
Multiplying relations (1) for
k
=
1
, . . . ,
n
yields
f
n
−
2
=
f
0
· · ·
f
n
−
1
(
f
0
−
2
),
and the conclusion follows.
Do'stlaringiz bilan baham: |
