|
8
Diophantine Equations
8.1
Linear Diophantine Equations
Problem 8.1.4.
Solve in integers the equation
(
x
2
+
1
)(
y
2
+
1
)
+
2
(
x
−
y
)(
1
−
x y
)
=
4
(
1
+
x y
).
Solution.
The equation is equivalent to
x
2
y
2
−
2
x y
+
1
+
x
2
+
y
2
−
2
x y
+
2
(
x
−
y
)(
1
−
x y
)
=
4
,
or
(
x y
−
1
)
2
+
(
x
−
y
)
2
+
2
(
x
−
y
)(
1
−
x y
)
=
4
.
Hence
(
1
−
x y
+
x
−
y
)
2
=
4, and consequently,
|
(
1
+
x
)(
1
−
y
)
| =
2.
We have two cases:
(i)
|
x
+
1
| =
1 and
|
y
−
1
| =
2, giving
(
0
,
3
)
,
(
0
,
−
1
)
,
(
−
2
,
3
)
and
(
−
2
,
−
1
)
,
and
(ii)
|
x
+
1
| =
2 and
|
y
−
1
| =
1, giving
(
1
,
2
)
,
(
1
,
0
)
,
(
−
3
,
2
)
and
(
−
3
,
0
)
.
Problem 8.1.5.
Determine the side lengths of a right triangle if they are integers
and the product of the legs’ lengths equals three times the perimeter.
(1999 Romanian Mathematical Olympiad)
First solution.
Let
a
,
b
,
c
be the lengths of the triangle’s sides. We have
a
2
=
b
2
+
c
2
and
bc
=
3
(
a
+
b
+
c
).
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
T. Andreescu and D. Andrica,
Number Theory
,
DOI: 10.1007/b11856_19,
311
312
II Solutions, 8. Diophantine Equations
Let
P
=
a
+
b
+
c
. Then
bc
=
3
P
and
b
2
+
c
2
=
(
b
+
c
)
2
−
2
bc
=
(
P
−
a
)
2
−
6
P
=
P
2
+
a
2
−
2
a P
−
6
P
.
It follows that
a
2
=
P
2
+
a
2
−
2
a P
−
6
P
,
so
P
=
2
a
+
6
,
that is,
a
=
b
+
c
−
6
.
We have then
b
2
+
c
2
=
b
2
+
c
2
+
2
bc
−
12
b
−
12
c
+
36
if and only if
bc
−
6
b
−
6
c
+
18
=
0
,
that is,
(
b
−
6
)(
c
−
6
)
=
18
.
Analyzing the ways in which 18 can be written as a product of integers, we
find the following solutions:
(
a
,
b
,
c
)
∈{
(
25
,
7
,
24
),(
25
,
24
,
7
),(
17
,
8
,
15
),(
17
,
15
,
8
),(
15
,
9
,
12
),(
15
,
12
,
9
)
}
.
Second solution.
From
bc
=
3
(
a
+
b
+
c
)
, we get
bc
−
3
b
−
3
c
=
3
a
and square
to get
(
bc
−
3
b
−
3
c
)
2
=
9
a
2
=
9
(
b
2
+
c
2
)
. From there multiplying out gives
bc
[
(
b
−
6
)(
c
−
6
)
−
18
] =
0. Since
bc
=
0, we get
(
b
−
6
)(
c
−
6
)
=
18, and
enumerating the factors of 18 gives the list of solutions.
Problem 8.1.6.
Let a
,
b, and c be positive integers, each two of them being rel-
atively prime. Show that
2
abc
−
ab
−
bc
−
ca is the largest integer that cannot
be expressed in the form xbc
+
yca
+
zab, where x
,
y, and z are nonnegative
integers.
(24th International Mathematical Olympiad)
Solution.
We will solve the problem in two steps.
First step.
The number 2
abc
−
ab
−
bc
−
ca
cannot be expressed in the required
form. Assume the contrary, that
2
abc
−
ab
−
bc
−
ca
=
xbc
+
yca
+
zab
,
where
x
,
y
,
z
≥
0. Then, one obtains the combination
2
abc
=
bc
(
x
+
1
)
+
ca
(
y
+
1
)
+
ab
(
z
+
1
),
8.2. Quadratic Diophantine Equations
313
where
x
+
1
>
0,
y
+
1
>
0,
z
+
1
>
0. This leads to the divisibility
a
|
bc
(
x
+
1
)
.
Since
a
is relatively prime to
b
and
c
,
a
divides
x
+
1 and then
a
≤
x
+
1.
Using similar arguments,
b
≤
y
+
1 and
c
≤
z
+
1. Thus, 2
abc
=
bc
(
x
+
1
)
+
ca
(
y
+
1
)
+
ab
(
z
+
1
)
≥
3
abc
. This is a contradiction.
Second step.
Any number
N
,
N
>
2
abc
−
ab
−
bc
−
ca
, can be expressed in
the form
N
=
xbc
+
yca
+
zab
.
Since gcd
(
ab
,
bc
,
ca
)
=
1, by Theorem 8.1.1 we can write
N
=
abx
+
bcy
+
caz
for some integers
x
,
y
,
z
. If
(
x
,
y
,
z
)
is one solution, then so is
(
x
±
c
,
y
∓
a
,
z
)
.
Hence we may assume 0
≤
x
≤
c
−
1. Similarly, if
(
x
,
y
±
a
,
z
∓
b
)
is a solution,
so we may assume 0
≤
y
≤
a
−
1. But then
z
=
1
ac
[
N
−
abx
−
bcy
]
>
1
ac
[
2
abc
−
ab
−
bc
−
ca
−
ab
(
c
−
1
)
−
bc
(
b
−
1
)
] = −
1
.
Thus
z
is again a nonnegative integer and we are done.
Remark.
One can prove that if
a
1
,
a
2
, . . . ,
a
k
∈
Z
are positive integers such that
gcd
(
a
1
, . . . ,
a
k
)
=
1, then any sufficiently large
n
is a linear combination with
nonnegative coefficients of
a
1
, . . . ,
a
k
. The smallest such
n
for
k
≥
4 is unknown.
This is the famous problem of Frobenius.
8.2
Quadratic Diophantine Equations
8.2.1
Pythagorean Equations
Problem 8.2.3.
Find all Pythagorean triangles whose areas are numerically equal
to their perimeters.
First solution.
From (3), the side lengths of such a triangle are
k
(
m
2
−
n
2
),
2
kmn
,
k
(
m
2
+
n
2
).
The condition in the problem is equivalent to
k
2
mn
(
m
2
−
n
2
)
=
2
km
(
m
+
n
),
which reduces to
kn
(
m
−
n
)
=
2
.
A simple case analysis shows that the only possible triples
(
k
,
m
,
n
)
are
(
2
,
2
,
1
)
,
(
1
,
3
,
2
)
,
(
1
,
3
,
1
)
, yielding the Pythagorean triangles 6
−
8
−
10 and
5
−
12
−
13.
Second solution.
This solution does not use Theorem 8.2.1, and it is similar to
the solution of Problem 8.1.5. Rewrite the equation
a
+
b
+
c
=
ab
/
2 as 2
c
=
ab
−
2
a
−
2
b
and square to get 4
(
a
2
+
b
2
)
=
4
c
2
=
(
ab
−
2
a
−
2
b
)
2
and rearrange
to get
ab
[
(
a
−
4
)(
b
−
4
)
−
8
] =
0. Then the solutions follow from the factors of 8.
314
II Solutions, 8. Diophantine Equations
Problem 8.2.4.
Prove that for every positive integer n there is a positive integer k
such that k appears in exactly n nontrivial Pythagorean triples.
(American Mathematical Monthly)
First solution.
We will prove by induction that 2
n
+
1
appears in exactly
n
Pythag-
orean triples. The base case
n
=
1 holds for
(
3
,
2
2
,
5
)
, and that is the only such
triple. Assume that
(
x
k
,
y
k
,
z
k
)
, where
x
k
=
u
2
k
−
v
2
k
,
y
k
=
2
u
k
v
k
,
z
k
=
u
2
k
+
v
2
k
,
k
=
1
, . . . ,
n
, are the
n
triples containing 2
n
+
1
. Then
(
2
x
k
,
2
y
k
,
2
z
k
)
,
k
=
1
, . . . ,
n
, are
n
imprimitive Pythagorean triples containing 2
n
+
2
, and
(
2
2
n
+
2
−
1
,
2
n
+
2
, 2
2
n
+
2
+
1
)
is the only such primitive triple.
No other triple with this property exists. Indeed, if
(
u
2
−
v
2
,
2
u
v,
u
2
+
v
2
)
were a triple containing 2
n
+
2
, then we would have the following cases:
(i)
u
2
+
v
2
=
2
n
+
2
. Simplifying by the greatest possible power of 2, we get
a
2
+
b
2
=
2
k
, where
a
and
b
are not both even. Then the left-hand side is congruent
to 1 or 2
(
mod 4
)
, while the right-hand side is 0
(
mod 4
)
, a contradiction.
(ii) 2
u
v
=
2
n
+
2
. We simplify again by the greatest power of 2 and obtain
ab
=
2
s
, where
a
>
b
are not both even and
s
≥
1. It follows that
a
=
2
s
and
b
=
1, yielding the triple generated by
(
2
2
s
−
1
,
2
s
+
1
,
2
2
s
+
1
)
multiplied by a
power of 2, which is clearly among the imprimitive triples
(
2
x
k
,
2
y
k
,
2
z
k
)
.
(iii)
u
2
−
v
2
=
2
n
+
2
. Simplifying again by the greatest power of 2, we arrive at
a
2
−
b
2
=
2
t
, where
a
and
b
are not both even and
t
≥
3. If one of
a
and
b
is even,
then the left-hand side is odd, while the right-hand side is even, a contradiction.
If
a
and
b
are both odd, then
a
−
b
=
2 and
a
+
b
=
2
t
−
1
, yielding
a
−
2
t
−
2
and
b
=
2
t
−
2
−
1. Again, we get a triple generated by
(
2
t
,
2
(
2
2
t
−
4
−
1
),
2
(
2
2
t
−
4
+
1
))
multiplied by a power of 2, which is clearly already an imprimitive triple of the
form
(
2
x
k
,
2
y
k
,
2
z
k
)
.
Do'stlaringiz bilan baham: |
