|
II Solutions, 8. Diophantine Equations
Solution.
We consider the equation mod 11. Since
(
x
5
)
2
=
x
10
≡
0 or 1
(
mod 11
)
for all
x
, we have
x
5
≡ −
1, 0, or 1
(
mod 11
)
, so the right-hand side is either 6,
7, or 8 modulo 11. However, all squares are 0, 1, 3, 4, 5, or 9 modulo 11, so the
equation
y
2
=
x
5
−
4 has no integer solutions.
Problem 8.3.14.
Let m
,
n
>
1
be integers. Solve in positive integers the equation
x
n
+
y
n
=
2
m
.
(2003 Romanian Mathematical Olympiad)
Solution.
Let
d
=
gcd
(
x
,
y
)
and
x
=
da
,
y
=
db
, where
(
a
,
b
)
=
1. it is easy to
see that
a
and
b
are both odd numbers and
a
n
+
b
n
=
2
k
, for some integer
k
.
Suppose that
n
is even. Since
a
2
≡
b
2
≡
1
(
mod 8
)
, we have also
a
n
≡
b
n
≡
1
(
mod 8
)
. Since 2
k
=
a
n
+
b
n
≡
2
(
mod 8
)
, we conclude that
k
=
1 and
a
=
b
=
1, and thus
x
=
y
=
d
. The equation becomes
x
n
=
2
m
−
1
, and it has an
integer solution if and only if
n
is a divisor of
m
−
1 and
x
=
y
=
2
m
−
1
n
.
Consider the case that
n
is odd. From the decomposition
a
n
+
b
n
=
(
a
+
b
)(
a
n
−
1
−
a
n
−
2
b
+
a
n
−
3
b
2
− · · · +
b
n
−
1
),
we easily get
a
+
b
=
2
k
=
a
n
+
b
n
, since the second factor above is odd. In this
case
a
=
b
=
1, and the proof goes along the lines of the previous case.
To conclude, the given equations have solutions if and only if
m
−
1
n
is an inte-
ger, and in this case
x
=
y
=
2
m
−
1
n
.
Problem 8.3.15.
For a given positive integer m, find all pairs
(
n
,
x
,
y
)
of positive
integers such that m
,
n are relatively prime and
(
x
2
+
y
2
)
m
=
(
x y
)
n
, where n
,
x
,
y
can be represented in terms of m.
(1995 Korean Mathematical Olympiad)
Solution.
If
(
n
,
x
,
y
)
is a solution, then the AM–GM inequality yields
(
x y
)
n
=
(
x
2
+
y
2
)
m
≥
(
2
x y
)
m
> (
x y
)
m
,
so
n
>
m
. Let
p
be a common prime divisor of
x
and
y
and let
p
a
x
,
p
b
y
.
Then
p
(
a
+
b
)
n
(
x y
)
n
=
(
x
2
+
y
2
)
m
. Suppose
b
>
a
. Since
p
2
a
x
2
,
p
2
b
y
2
, we
see that
p
2
a
x
2
+
y
2
and
p
2
am
(
x
2
+
y
2
)
m
. Thus 2
am
=
(
a
+
b
)
n
>
2
an
and
m
>
n
, a contradiction. Likewise,
a
>
b
produces a contradiction, so we must
have
a
=
b
and
x
=
y
. This quickly leads to
x
=
2
t
for some integer
t
, and all
solutions are of the form
(
n
,
x
,
y
)
=
(
2
t
+
1
,
2
t
,
2
t
)
for nonnegative integers
t
. Substituting into the equation, we conclude that there
is a solution only if
m
is even, and then
t
=
m
2
.
8.3. Nonstandard Diophantine Equations
325
8.3.3
Exponential Diophantine Equations
Problem 8.3.19.
Determine all triples
(
x
,
k
,
n
)
of positive integers such that
3
k
−
1
=
x
n
.
(1999 Italian Mathematical Olympiad)
Solution.
All triples of the form
(
3
k
−
1
,
k
,
1
)
for positive integers
k
, and
(
2
,
2
,
3
)
.
The solutions when
n
=
1 are obvious. Now,
n
cannot be even because then 3
could not divide 3
k
=
(
x
n
2
)
2
+
1 (because no square is congruent to 2 modulo 3).
Also, we must have
x
=
1.
Assume that
n
>
1 is odd and
x
≥
2. Then 3
k
=
(
x
+
1
)
"
n
−
1
i
=
0
(
−
x
)
i
,
implying that both
x
+
1 and
"
n
−
1
i
=
0
(
−
x
)
i
are powers of 3. Because
x
+
1
≤
x
2
−
x
+
1
≤
"
n
−
1
i
=
0
(
−
x
)
i
, we must have 0
≡
"
n
−
1
i
=
0
(
−
x
)
i
≡
n
(
mod
x
+
1
)
,
so that
x
+
1
|
n
. Specifically, this means that 3
|
n
.
Write
x
=
x
n
/
3
, then we have 3
k
−
1
=
(
x
)
3
. Thus repeating the argument
of the previous paragraph, now with
n
=
3, shows
x
+
1
|
3. Hence
x
=
2 and
therefore
x
=
2 and
n
=
3.
Remark.
In fact, 8 and 9 are the only consecutive powers (other than the trivial
0, 1), as recently proved.
Problem 8.3.20.
Find all pairs of nonnegative integers x and y that satisfy the
equation
p
x
−
y
p
=
1
,
where p is a given odd prime.
(1995 Czech–Slovak Match)
Solution.
If
(
x
,
y
)
is a solution, then
p
x
=
y
p
+
1
=
(
y
+
1
)(
y
p
−
1
− · · · +
y
2
−
y
+
1
),
and so
y
+
1
=
p
n
for some
n
. If
n
=
0, then
x
=
y
=
0 and
p
may be arbitrary.
Otherwise,
p
x
=
(
p
n
−
1
)
p
+
1
=
p
np
−
p
·
p
n
(
p
−
1
)
+
p
2
p
n
(
p
−
2
)
+ · · · −
p
p
−
2
p
2
n
+
p
·
p
n
.
Since
p
is a prime, all of the binomial coefficients are divisible by
p
. Hence
all terms are divisible by
p
n
+
1
, and all but the last by
p
n
+
2
. Therefore the highest
power of
p
dividing the right side is
p
n
+
1
, and so
x
=
n
+
1. We also have
0
=
p
np
−
p
·
p
n
(
p
−
1
)
+
p
2
p
n
(
p
−
2
)
+ · · · −
p
p
−
2
p
2
n
.
326
II Solutions, 8. Diophantine Equations
For
p
=
3 this reads 0
=
3
3
n
−
3
·
3
2
n
, which occurs only for
n
=
1, yielding
x
=
y
=
2. For
p
≥
5, the coefficient
p
p
−
2
is not divisible by
p
2
, so every term
but the last on the right side is divisible by
p
2
n
+
2
, while the last term is not. Since
the terms sum to 0, this is impossible.
Hence the only solutions are
x
=
y
=
0 for all
p
and
x
=
y
=
2 for
p
=
3.
Problem 8.3.21.
Let x
,
y
,
z be integers with z
>
1
. Show that
(
x
+
1
)
2
+
(
x
+
2
)
2
+ · · · +
(
x
+
99
)
2
=
y
z
.
(1998 Hungarian Mathematical Olympiad)
Solution.
Suppose, to the contrary, that there are integers
x
,
y
,
z
such that
z
>
1,
and
(
x
+
1
)
2
+
(
x
+
2
)
2
+ · · · +
(
x
+
99
)
2
=
y
z
.
We notice that
y
z
=
(
x
+
1
)
2
+
(
x
+
2
)
2
+ · · · +
(
x
+
99
)
2
=
99
x
2
+
2
(
1
+
2
+ · · · +
99
)
x
+
(
1
2
+
2
2
+ · · · +
99
2
)
=
99
x
2
+
2
·
99
·
100
2
x
+
99
·
100
·
199
6
=
33
(
3
x
2
+
300
x
+
50
·
199
),
which implies that 3
|
y
. Since
z
≥
2, 3
2
|
y
z
, but 3
2
does not divide 33
(
3
x
2
+
300
x
+
50
·
199
)
, we have a contradiction. So our assumption in fact must be false,
and the original statement in the problem is correct.
Problem 8.3.22.
Determine all solutions
(
x
,
y
,
z
)
of positive integers such that
(
x
+
1
)
y
+
1
+
1
=
(
x
+
2
)
z
+
1
.
(1999 Taiwanese Mathematical Olympiad)
Solution.
Let
a
=
x
+
1,
b
=
y
+
1,
c
=
z
+
1. Then
a
,
b
,
c
≥
2 and
a
b
+
1
=
(
a
+
1
)
c
,
((
a
+
1
)
−
1
)
b
+
1
=
(
a
+
1
)
c
.
Taking the equations mod
(
a
+
1
)
yields
(
−
1
)
b
+
1
≡
0, so
b
is odd.
Taking the second equation mod
(
a
+
1
)
2
after applying the binomial expan-
sion yields
b
1
(
a
+
1
)(
−
1
)
b
−
1
+
(
−
1
)
b
+
1
≡
0
(
mod
(
a
+
1
)
2
),
Do'stlaringiz bilan baham: |
