|
II Solutions, 5. Basic Principles in Number Theory
triples
(
r
0
,
r
1
,
r
2
)
,
(
r
1
,
r
2
,
r
3
), . . . , (
r
m
3
,
r
m
3
+
1
,
r
m
3
+
2
)
. Since
r
t
can take
m
val-
ues, it follows by the pigeonhole principle that at least two triples are equal. Let
p
be the smallest number such that the triple
(
r
p
,
r
p
+
1
,
r
p
+
2
)
is equal to another
triple
(
r
q
,
r
q
+
1
,
r
q
+
2
)
,
p
<
q
≤
m
3
. We claim that
p
=
0.
Assume by way of contradiction that
p
≥
1. Using the hypothesis, we have
r
p
≡
r
p
−
1
+
r
p
r
p
+
1
(
mod
m
)
and
r
q
+
2
≡
r
q
−
1
+
r
q
r
q
+
1
(
mod
m
).
Since
r
p
=
r
q
,
r
p
+
1
=
r
q
+
1
and
r
p
+
2
=
r
q
+
2
, it follows that
r
p
−
1
=
r
q
−
1
, so
(
r
p
−
1
,
r
p
,
r
p
+
1
)
=
(
r
q
−
1
,
r
q
,
r
q
+
1
)
, which is a contradiction to the minimality of
p
. Hence
p
=
0, so
r
q
=
r
0
=
0, and therefore
x
q
≡
0 mod
m
.
Problem 5.1.12.
Prove that among seven arbitrary perfect squares there are two
whose difference is divisible by 20.
(Mathematical Reflections)
First solution.
It is easy to check that perfect squares can give one of the follow-
ing residues: 1
,
2
,
4
,
8
,
16
(
mod 20
)
.
By the pigeonhole principle we conclude that among seven perfect squares
we must have at least two that have the same residue modulo 20. Hence their
difference is divisible by 20 and our proof is complete.
Second solution.
Note that for all integers
x
we have
x
2
≡
1
,
2
,
4
,
8
,
16
(
mod
m
)
and we have six distinct possible residues. If we have seven arbitrary perfect
squares
x
2
1
,
x
2
2
,
x
2
3
,
x
2
4
,
x
2
5
,
x
2
6
,
x
2
7
, by the pigeonhole principle, there are two
squares
x
2
i
and
x
2
j
with the same residue and they satisfy the requirement.
Third solution.
Observe that by the pigeonhole principle, there are at least four
perfect squares that all have the same parity. Now note that for any integer
n
,
we have
n
2
≡ −
1
,
0
,
1
(
mod 5
)
. Again by the pigeonhole principle, out of these
four perfect squares, we have at least two perfect squares, say
a
2
and
b
2
, such that
a
2
≡
b
2
(
mod 5
)
. This implies that 5
|
a
2
−
b
2
. Also, 2
|
a
−
b
and 2
|
a
+
b
,
since both
a
and
b
have the same parity. Hence, 4
|
a
2
−
b
2
, but gcd
(
5
,
4
)
=
1;
thus we have 20
|
a
2
−
b
2
, and we are done.
5.2
Mathematical Induction
Problem 5.2.7.
Let p be an odd prime. The sequence
(
a
n
)
n
≥
0
is defined as fol-
lows: a
0
=
0
, a
1
=
1
, . . .
, a
p
−
2
=
p
−
2
, and for all n
≥
p
−
1
, a
n
is the least
positive integer that does not form an arithmetic sequence of length p with any of
the preceding terms. Prove that for all n, a
n
is the number obtained by writing n
in base p
−
1
and reading the result in base p.
(1995 USA Mathematical Olympiad)
5.2. Mathematical Induction
279
Solution.
Our proof uses the following result.
Lemma.
Let B
= {
b
0
,
b
1
,
b
2
, . . .
}
, where b
n
is the number obtained by writing n
in base p
−
1
and reading the result in base p. Then
(a) for every a
∈
B, there exists d
>
0
such that a
−
kd
∈
B for k
=
1
,
2
, . . . ,
p
−
1
; and
(b) B contains no p-term arithmetic progression.
Proof.
Note that
b
∈
B
if and only if the representation of
b
in base
p
does not
use the digit
p
−
1.
(a) Since
a
∈
B
, when
a
is written in base
p
at least one digit is
p
−
1. Let
d
be the positive integer whose representation in base
p
is obtained from that of
a
by replacing each
p
−
1 by 1 and each digit other than
p
−
1 by 0. Then none of
the numbers
a
−
d
,
a
−
2
d
, . . .
,
a
−
(
p
−
1
)
d
has
p
−
1 as a digit when written
in base
p
, and the result follows.
(b) Let
a
,
a
+
d
,
a
+
2
d
, . . . ,
a
+
(
p
−
1
)
d
be an arbitrary
p
-term arithmetic
progression of nonnegative integers. Let
δ
be the rightmost nonzero digit when
d
is written in base
p
, and let
α
be the corresponding digit in the representation of
a
in base
p
. Then
α, α
+
δ, . . . , α
+
(
p
−
1
)δ
is a complete set of residues modulo
p
. It follows that at least one of the numbers
a
,
a
+
d
, . . . ,
a
+
(
p
−
1
)
d
has
p
−
1
as a digit when written in base
p
. Hence at least one term of the given arithmetic
progression does not belong to
B
.
Let
(
a
n
)
n
≥
0
be the sequence defined in the problem. To prove that
a
n
=
b
n
for all
n
≥
0, we use mathematical induction. Clearly
a
0
=
b
0
=
0. Assume
that
a
k
=
b
k
for 0
≤
k
≤
n
−
1, where
n
≥
1. Then
a
n
is the smallest integer
greater than
b
n
−
1
such that
{
b
0
,
b
1
, . . . ,
b
n
−
1
,
a
n
}
contains no
p
-term arithmetic
progression. By part (i) of the proposition,
a
n
∈
B
, so
a
n
≥
b
n
. By part (ii) of the
proposition, the choice of
a
n
=
b
n
does not yield a
p
-term arithmetic progression
with any of the preceding terms. It follows by induction that
a
n
=
b
n
for all
n
≥
0.
Problem 5.2.8.
Suppose that x
,
y, and z are natural numbers such that x y
=
z
2
+
1
. Prove that there exist integers a
,
b
,
c, and d such that x
=
a
2
+
b
2
,
y
=
c
2
+
d
2
, and z
=
ac
+
bd.
(Euler’s problem)
Solution.
We prove the claim by strong induction on
z
. For
z
=
1, we have
(
x
,
y
)
=
(
1
,
2
)
or
(
2
,
1
)
; in the former (resp. latter) case, we can set
(
a
,
b
,
c
,
d
)
=
(
1
,
0
,
1
,
1
)
(resp.
(
0
,
1
,
1
,
1
)
).
Suppose that the claim is true whenever
z
<
z
0
, and that we wish to prove
it for
(
x
,
y
,
z
)
=
(
x
0
,
y
0
,
z
0
)
, where
x
0
y
0
=
z
2
0
+
1. Without loss of generality,
assume that
x
0
≤
y
0
. Consider the triple
(
x
1
,
y
1
,
z
1
)
=
(
x
0
,
x
0
+
y
0
−
2
z
0
,
z
0
−
x
0
)
,
so that
(
x
0
,
y
0
,
z
0
)
=
(
x
1
,
x
1
+
y
1
+
2
z
1
,
x
1
+
z
1
)
.
First, using the fact that
x
0
y
0
=
z
2
0
+
1, it is easy to check that
(
x
,
y
,
z
)
=
(
x
1
,
y
1
,
z
1
)
satisfies
x y
=
z
2
+
1.
280
Do'stlaringiz bilan baham: |
