|
8.2. Quadratic Diophantine Equations
153
such that there exists a subsequence of
(
t
n
, w
n
)
n
≥
1
satisfying the equation
t
2
−
D
w
2
=
k
. This subsequence contains at least two pairs
(
t
s
, w
s
)
,
(
t
r
, w
r
)
for which
t
s
≡
t
r
(
mod
k
)
,
w
s
≡
w
r
(
mod
k
)
, and
t
s
w
r
−
t
r
w
s
=
0, otherwise
t
s
=
t
r
and
w
s
=
w
r
, in contradiction to
|
t
s
−
t
r
| + |
w
s
−
w
r
| =
0.
Let
t
0
=
t
s
t
r
−
D
w
s
w
r
and let
w
0
=
t
s
w
r
−
t
r
w
s
. Then
t
2
0
−
D
w
2
0
=
k
2
.
(
3
)
On the other hand,
t
0
=
t
s
t
r
−
D
w
s
w
r
≡
t
2
s
−
D
w
2
0
≡
0
(
mod
k
)
, and it
follows immediately that
w
0
≡
0
(
mod
k
)
. The pair
(
t
, w)
, where
t
0
=
t
|
k
|
and
w
0
=
w
k
, is a nontrivial solution to equation (1).
We show now that the pair
(
u
n
, v
n
)
defined by (2) satisfies Pell’s equation (1).
We proceed by induction with respect to
n
. By definition,
(
u
1
, v
1
)
is a solution to
equation (1). If
(
u
n
, v
n
)
is a solution to this equation, then
u
2
n
+
1
−
D
v
2
n
+
1
=
(
u
1
u
n
+
D
v
1
v
n
)
2
−
D
(v
1
u
n
+
u
1
v
n
)
2
=
(
u
2
1
−
D
v
2
1
)(
u
2
n
−
D
v
2
n
)
=
1
,
i.e., the pair
(
u
n
+
1
, v
n
+
1
)
is also a solution to equation (1).
It is not difficult to see that for all positive integers
n
,
u
n
+
v
n
√
D
=
(
u
1
+
v
1
√
D
)
n
.
(
4
)
Let
z
n
=
u
n
+
v
n
√
D
=
(
u
1
+
v
1
√
D
)
n
and note that
z
1
<
z
2
<
· · ·
<
z
n
<
· · ·
. We will prove now that all solutions to equation (1) are of the form
(4). Indeed, if equation (1) had a solution
(
u
, v)
such that
z
=
u
+
v
√
D
is
not of the form (4), then
z
m
<
z
<
z
m
+
1
for some integer
m
. Also, we have
1
/
z
m
=
u
m
−
v
m
√
D
. Then 1
< (
u
+
v
√
D
)(
u
m
−
v
m
√
D
) <
u
1
+
v
1
√
D
,
and therefore 1
< (
uu
m
−
D
vv
m
)
+
(
u
m
v
−
u
v
m
)
√
D
<
u
1
+
v
1
√
D
. On the
other hand,
(
uu
m
−
D
vv
m
)
2
−
D
(
u
m
v
−
u
v
m
)
2
=
(
u
2
−
D
v
2
)(
u
2
m
−
D
v
2
m
)
=
1,
i.e.,
(
uu
m
−
D
vv
m
,
u
m
v
−
u
v
m
)
is a solution of (1) smaller than
(
u
1
, v
1
)
, in
contradiction to the assumption that
(
u
1
, v
1
)
was the minimal one.
In order to complete the proof we have only to show that
a
=
uu
m
−
D
vv
m
and
b
=
u
m
v
−
u
v
m
are positive. We have 1
<
a
+
b
√
D
and
a
2
−
Db
2
=
1;
hence 0
<
1
/(
a
+
b
√
D
)
=
a
−
b
√
D
<
1. Now we obtain
a
=
1
2
(
a
+
b
√
D
)
+
1
2
(
a
−
b
√
D
) >
1
2
+
0
>
0
,
b
√
D
=
1
2
(
a
+
b
√
D
)
−
1
2
(
a
−
b
√
D
) >
1
2
−
1
2
=
0
,
so
a
,
b
are positive integers.
154
Remarks.
(1) The identity
u
m
+
v
m
√
D
=
(
u
1
+
v
1
√
D
)
m
,
m
=
0
,
1
,
2
, . . .
,
shows how the fundamental solution generates all solutions.
(2) The relations (1) could be written in the following useful matrix form:
u
n
+
1
v
n
+
1
=
u
1
D
v
1
v
1
u
1
u
n
v
n
,
whence
u
n
v
n
=
u
1
D
v
1
v
1
u
1
n
u
0
v
0
=
u
1
D
v
1
v
1
u
1
1
0
.
(
5
)
If
u
1
D
v
1
v
1
u
1
n
=
a
n
b
n
c
n
d
n
then it is well known that each of
a
n
,
b
n
,
c
n
,
d
n
is a linear combination of
λ
n
1
, λ
n
2
,
where
λ
1
, λ
2
are the eigenvalues of the matrix
u
1
D
v
1
v
1
u
1
. Using (5), after an easy
computation it follows that
u
n
=
1
2
[
(
u
1
+
v
1
√
D
)
n
+
(
u
1
−
v
1
√
D
)
n
]
,
v
n
=
1
2
√
D
[
(
u
1
+
v
1
√
D
)
n
−
(
u
1
−
v
1
√
D
)
n
]
.
(
6
)
(3) The solutions to Pell’s equation given in the form (4) or (6) may be used
in the approximation of the square roots of positive integers that are not perfect
squares. Indeed, if
(
u
n
, v
n
)
are the solutions of equation (1), then
u
n
−
v
n
√
D
=
1
u
n
+
v
n
√
D
,
and so
u
n
v
n
−
√
D
=
1
v
n
(
u
n
+
v
n
√
D
)
<
1
√
D
v
2
n
<
1
v
2
n
,
i.e., the fractions
u
n
/v
n
approximate
√
D
with an error less than 1
/v
2
n
.
It follows that
lim
n
→∞
u
n
v
n
=
√
D
.
(
7
)
Problem 8.2.4.
Consider the sequences
(
u
n
)
n
≥
0
,
(v
n
)
n
≥
0
defined by u
0
=
1
,
v
0
=
0
, and u
n
+
1
=
3
u
n
+
4
v
n
,
v
n
+
1
=
2
u
n
+
3
v
n
, n
≥
1
. Define x
n
=
u
n
+
v
n
,
y
n
=
u
n
+
2
v
n
, n
≥
0
. Prove that y
n
=
x
n
√
2
for all n
≥
0
.
Solution.
We prove by induction that
u
2
n
−
2
v
2
n
=
1
,
n
≥
1
.
(
1
)
8.2. Quadratic Diophantine Equations
155
For
n
=
1 the claim is true. Assuming that the equality is true for some
n
, we
have
u
2
n
+
1
−
2
v
2
n
+
1
=
(
3
u
n
+
4
v
n
)
2
−
2
(
2
u
n
+
3
v
n
)
2
=
u
2
n
−
2
v
2
n
=
1
;
hence (1) is true for all
n
≥
1.
We prove now that
2
x
2
n
−
y
2
n
=
1
,
n
≥
1
.
(
2
)
Indeed,
2
x
2
n
−
y
2
n
=
2
(
u
n
+
v
n
)
2
−
(
u
n
+
2
v
n
)
2
=
u
2
n
−
2
v
2
n
=
1
,
as claimed. It follows that
x
n
√
2
−
y
n
x
n
√
2
+
y
n
=
1
,
n
≥
1
.
Notice that
x
n
√
2
+
y
n
>
1, so
0
<
x
n
√
2
−
y
n
<
1
,
n
≥
1
.
Hence
y
n
=
#
x
n
√
2
$
, as claimed.
Problem 8.2.5.
Show that there exist infinitely many systems of positive integers
(
x
,
y
,
z
,
t
)
that have no common divisor greater than
1
and such that
x
3
+
y
3
+
z
2
=
t
4
.
(2000 Romanian International Mathematical Olympiad Team Selection Test)
First solution.
Let us consider the identity
[
1
3
+
2
3
+ · · · +
(
n
−
2
)
3
] +
(
n
−
1
)
3
+
n
3
=
n
(
n
+
1
)
2
2
.
We may write it in the form
(
n
−
1
)
3
+
n
3
+
(
n
−
1
)(
n
−
2
)
2
2
=
n
(
n
+
1
)
2
2
.
It is sufficient to find positive integers
n
for which
n
(
n
+
1
)/
2 is a perfect
square. Such a goal can be attained.
Let us remark that the equality
(
2
n
+
1
)
2
−
2
(
2
x
)
2
=
1
156
Do'stlaringiz bilan baham: |
