|
8.3. Nonstandard Diophantine Equations
327
so
(
a
+
1
)
|
b
and
a
is even. On the other hand, taking the first equation mod
a
2
after applying the binomial expansion yields
1
≡
c
1
a
+
1
(
mod
a
2
),
so
c
is divisible by
a
and is even as well. Write
a
=
2
a
1
and
c
=
2
c
1
. Then
2
b
a
b
1
=
a
b
=
(
a
+
1
)
c
−
1
=
((
a
+
1
)
c
1
−
1
)((
a
+
1
)
c
1
+
1
).
It follows that gcd
((
a
+
1
)
c
1
−
1
, (
a
+
1
)
c
1
+
1
)
=
2. Therefore, using the fact
that 2
a
1
is a divisor of
(
a
+
1
)
c
1
−
1, we may conclude that
(
a
+
1
)
c
1
−
1
=
2
a
b
1
(
a
+
1
)
c
1
+
1
=
2
b
−
1
.
We must have 2
b
−
1
>
2
a
b
1
⇒
a
1
=
1. Then these equations give
c
1
=
1 and
b
=
3. Therefore the only solution is
(
x
,
y
,
z
)
=
(
1
,
2
,
1
)
.
9
Some Special Problems in
Number Theory
9.1
Quadratic Residues; the Legendre Symbol
Problem 9.1.7.
Let f
,
g
:
Z
+
→
Z
+
be 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)
Solution.
Let
p
n
be the sequence of prime numbers of the form 8
k
+
3. There are
infinitely many such integers. This is a trivial consequence of Dirichlet’s theorem,
but you can find an elementary proof at the end of solution to Problem 9.1.8. It is
obvious that for all
n
we have
2
p
n
=
(
−
1
)
p
2
n
−
1
8
= −
1
.
Using the condition (i) we can find
x
n
such that
g
(
x
n
)
=
p
n
for all
n
. It follows
that 2
f
2
(
x
n
)
=
x
2
n
+
p
2
n
, which can be rewritten as 2
f
2
(
x
n
)
≡
x
2
n
(
mod
p
n
)
.
Because
2
p
n
= −
1, the last congruence shows that
p
n
|
x
n
and
p
n
|
f
(
x
n
)
. Thus
there exist sequences of positive integers
a
n
,
b
n
such that
x
n
=
a
n
p
n
,
f
(
x
n
)
=
b
n
p
n
for all
n
. Clearly, (ii) implies the relation 2
b
2
n
=
a
2
n
+
1. Finally, using the
property
|
f
(
n
)
−
n
| ≤
2004
√
n
, we infer that
2004
√
x
n
≥
f
(
x
n
)
x
n
−
1
=
b
n
a
n
−
1
,
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
T. Andreescu and D. Andrica,
Number Theory
,
DOI: 10.1007/b11856_20,
329
330
II Solutions, 9. Some Special Problems in Number Theory
that is,
lim
n
→∞
a
2
n
+
1
a
n
=
√
2
.
The last relation immediately implies that lim
n
→∞
a
n
=
1. Therefore, starting
from a certain
n
, we have
a
n
=
1
=
b
n
, that is,
f
(
p
n
)
=
p
n
. The conclusion now
follows.
Problem 9.1.8.
Suppose that the positive integer a is not a perfect square. Then
a
p
= −
1
for infinitely many primes p.
Solution.
One may assume that
a
is square-free. Let us write
a
=
2
e
q
1
q
2
· · ·
q
n
,
where
q
i
are distinct odd primes and
e
∈ {
0
,
1
}
. Let us assume first that
n
≥
1
and consider some odd distinct primes
r
1
, . . . ,
r
k
each of them different from
q
1
, . . . ,
q
n
. We will show that there exists a prime
p
, different from
r
1
, . . . ,
r
k
,
such that
a
p
= −
1. Let
s
be a quadratic nonresidue modulo
q
n
.
Using the Chinese remainder theorem, we can find a positive integer
b
such
that
⎧
⎪
⎪
⎨
⎪
⎪
⎩
b
≡
1
(
mod
r
i
),
1
≤
i
≤
k
,
b
≡
1
(
mod 8
),
b
≡
1
(
mod
q
i
),
1
≤
i
≤
n
−
1
,
b
≡
s
(
mod
q
n
).
Now write
b
=
p
1
· · ·
p
m
with
p
i
odd primes, not necessarily distinct. Using
the quadratic reciprocity law, it follows immediately that
m
i
=
1
2
p
i
=
m
i
=
1
(
−
1
)
p
2
i
−
1
8
=
(
−
1
)
b
2
−
1
8
=
1
and
m
j
=
1
q
i
p
j
=
m
j
=
1
(
−
1
)
p j
−
1
2
·
qi
−
1
2
p
j
q
i
=
(
−
1
)
qi
−
1
2
·
b
−
1
2
b
q
i
=
b
q
i
for all
i
∈ {
1
,
2
, . . . ,
n
}
. Hence
m
i
=
1
a
p
i
=
7
m
j
=
1
2
p
j
8
e n
i
=
1
m
j
=
1
q
i
p
j
=
n
i
=
1
b
q
i
=
b
q
n
=
s
q
n
= −
1
.
Thus, there exists
i
∈ {
1
,
2
, . . . ,
m
}
such that
a
p
i
= −
1. Because
b
≡
1
(
mod
r
i
)
, 1
≤
i
≤
k
, we also have
p
i
∈ {
1
,
2
, . . .
} \ {
r
1
, . . . ,
r
k
}
, and the claim is
proved.
9.1. Quadratic Residues; the Legendre Symbol
331
The only remaining case is
a
=
2. By Theorem 9.1.2,
2
p
= −
1 if and only if
p
2
−
1
8
is odd, i.e., if and only if
p
≡ ±
3
(
mod 8
)
. Thus we need to show there are
infinitely many primes congruent to
±
3
(
mod 8
)
. Suppose to the contrary that
there are only finitely many such primes
p
1
, . . . ,
p
n
with
p
1
=
3 and consider
N
=
8
p
2
· · ·
p
n
+
3. None of the
p
i
divide
N
and neither does 2. Hence every
prime divisor of
N
must be
±
1
(
mod 8
)
. But this is impossible, since
N
≡
3
(
mod 8
)
. Thus there must be infinitely many primes of this form.
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
maximal possible number of nonzero a
i
’s?
(2004 Mathlinks Contest)
Solution.
Suppose that
a
1
,
a
2
, . . . ,
a
k
are positive integers such that
a
n
1
+
a
n
2
+
· · · +
a
n
k
is a perfect square for all
n
. We will show that
k
is a perfect square.
In order to prove this, we will use Problem 9.1.8 and show that
k
p
=
1 for all
sufficiently large prime
p
. This is not a difficult task. Indeed, consider a prime
p
greater than any prime divisor of
a
1
a
2
· · ·
a
k
. Using Fermat’s little theorem,
a
p
−
1
1
+
a
p
−
1
2
+ · · · +
a
p
−
1
k
≡
k
(
mod
p
)
, and since
a
p
−
1
1
+
a
p
−
1
2
+ · · · +
a
p
−
1
k
is
a perfect square, it follows that
k
p
=
1. Thus
k
is a perfect square. And now the
problem becomes trivial, since we must find the greatest perfect square smaller
than 2004. A quick computation shows that this is 44
2
=
1936, and so the desired
minimal number is 68.
Problem 9.1.10.
Find all positive integers n such that
2
n
−
1
|
3
n
−
1
.
(American Mathematical Monthly)
Solution.
We will prove that
n
=
1 is the only solution to the problem. Suppose
that
n
>
1 is a solution. Then 2
n
−
1 cannot be a multiple of 3; hence
n
is odd.
Therefore, 2
n
≡
8
(
mod 12
)
. Because any odd prime different from 3 is of one
of the forms 12
k
±
1, 12
k
±
5, and since 2
n
−
1
≡
7
(
mod 12
)
, it follows that
2
n
−
1 has at least one prime divisor of the form 12
k
±
5; call it
p
. Obviously,
we must have
(
3
/
p
)
=
1, and using the quadratic reciprocity law we finally
obtain
(
p
/
3
)
=
(
−
1
)
(
p
−
1
)/
2
. On the other hand
(
p
/
3
)
=
(
±
2
/
3
)
= −
(
±
1
)
.
Consequently,
−
(
±
1
)
=
(
−
1
)
(
p
−
1
)/
2
= ±
1, which is the desired contradiction.
Therefore the only solution is
n
=
1.
Problem 9.1.11.
Find the smallest prime factor of
12
2
15
+
1
.
Solution.
Let
p
be this prime number. Because
p
|
12
2
16
−
1, we find that
o
p
(
12
)
|
2
16
. Since 12
2
15
≡ −
1
≡
1
(
mod
p
)
, we find that
o
p
(
12
)
=
2
16
,
and so 2
16
|
p
−
1. Therefore
p
≥
1
+
2
16
. But it is well known that 2
16
+
1 is a
prime (and if you do not believe it, you can check; it is not that difficult). So, we
332
Do'stlaringiz bilan baham: |
