Number Theory: Structures, Examples, and Problems

II Solutions, 9. Some Special Problems in Number Theory
(d) 2
≤
a
<
m
. Rewrite
(
a
2
+
b
2
)/(
ab
+
1
)
=
m
2
as
b
2
−
m
2
ab
+
a
2
−
m
2
=
0
.
We know that
t
=
b
is a root of the quadratic equation
t
2
−
m
2
at
+
a
2
−
m
2
=
0
.
(
1
)
Thus
m
4
a
2
+
4
m
2
−
4
a
2
, the discriminant of the equation, must be a perfect
square. But
(
m
2
a
+
1
)
2
=
m
4
a
2
+
2
m
2
a
+
1
>
m
4
a
2
+
4
m
2
−
4
a
2
> (
m
2
a
)
2
for 2
≤
a
<
m
. So the discriminant cannot be a perfect square, a contradiction.
(e)
a
>
m
. Again
t
=
b
is a root of (1). It is easy to check that
t
=
m
2
a
−
b
=
c
also satisfies the equation. We have
bc
=
a
2
−
m
2
>
0; since
b
≥
0,
c
>
0. Since
a
>
0 and
c
>
0,
ac
+
1
>
0, we have
c
2
+
a
2
ca
+
1
=
m
2
.
Since
c
>
0,
b
≥
a
, and
bc
=
a
2
−
m
2
<
a
2
, we have
c
<
a
. Thus
(
c
,
a
)
is a
valid pair. Also, it cannot be of the form
(
a
n
,
a
n
+
1
)
, or else
(
a
,
b
)
=
(
a
n
+
1
,
m
2
a
n
+
1
−
a
n
)
=
(
a
n
+
1
,
a
n
+
2
).
But then,
c
+
a
<
a
+
a
≤
b
+
a
, as desired.
From the above, we see that our assumption is false. Therefore every pair
satisfying the original equation must be of the described form.
Second solution.
Note that if
a
=
0, then necessarily
b
=
m
, so
(
a
,
b
)
=
(
a
0
,
a
1
)
.
Also note that there is no solution with
a
,
b
both nonzero but of opposite signs.
Thus any other solution has
b
≥
a
>
0. If
(
a
,
b
)
is a solution, then one easily
checks that
(
a
,
m
2
a
−
b
)
is again a solution. Since
a
>
0, this means we must have
m
2
a
−
b
≥
0. Since
b
(
m
2
a
−
b
)
=
a
2
−
m
2
<
a
2
and
b
>
a
, we must also have
m
2
a
−
b
<
a
. Thus we have produced a smaller nonnegative solution. Because
we cannot reduce the solution indefinitely, reducing in this way must eventually
reach
(
0
,
m
)
. Therefore the original solution must have been
(
a
n
,
a
n
+
1
)
for some
n
.
Problem 9.3.14.
Let b
,
c be positive integers, and define the sequence a
1
,
a
2
, . . .
by a
1
=
b, a
2
=
c, and
a
n
+
2
= |
3
a
n
+
1
−
2
a
n
|
for n
≥
1
. Find all such
(
b
,
c
)
for which the sequence a
1
,
a
2
, . . .
has only a finite
number of composite terms.
(2002 Bulgarian Mathematical Olympiad)

---

9.3. Sequences of Integers
341
Solution.
The only solutions are
(
p
,
p
)
for
p
not composite,
(
2
p
,
p
)
for
p
not
composite, and
(
7
,
4
)
.
The sequence
a
1
,
a
2
, . . .
cannot be strictly decreasing because each
a
n
is a
positive integer, so there exists a smallest
k
≥
1 such that
a
k
+
1
≥
a
k
. Define a
new sequence
b
1
,
b
2
, . . .
by
b
n
=
a
n
+
k
−
1
, so
b
2
≥
b
1
,
b
n
+
2
= |
3
b
n
+
1
−
2
b
n
|
for
n
≥
1, and
b
1
,
b
2
, . . .
has only a finite number of composite terms. Now, if
b
n
+
1
≥
b
n
,
b
n
+
2
= |
3
b
n
+
1
−
2
b
n
| =
3
b
n
+
1
−
2
b
n
=
b
n
+
1
+
2
(
b
n
+
1
−
b
n
)
≥
b
n
+
1
,
so by induction
b
n
+
2
=
3
b
n
+
1
−
2
b
n
for
n
≥
1.
Using the general theory of linear recursion relations (a simple induction proof
also suffices), we have
b
n
=
A
·
2
n
−
1
+
B
for
n
≥
1, where
A
=
b
2
−
b
1
,
B
=
2
b
1
−
b
2
. Suppose (for contradiction) that
A
=
0. Then
b
n
is an increasing sequence, and since it contains only finitely
many composite terms,
b
n
=
p
for some prime
p
>
2 and some
n
≥
1. But then
b
n
+
l
(
p
−
1
)
would be divisible by
p
and thus composite for
l
≥
1, because
b
n
+
l
(
p
−
1
)
=
A
·
2
n
−
1
·
2
l
(
p
−
1
)
+
B
≡
A
·
2
n
−
1
+
B
≡
b
n
≡
0
(
mod
p
)
by Fermat’s little theorem. This is a contradiction, so
A
=
0 and
b
n
=
b
1
for
n
≥
1. Therefore
b
1
is not composite; let
b
1
=
p
, where
p
=
1 or
p
is prime.
We now return to the sequence
a
1
,
a
2
, . . .
, and consider different possible
values of
k
. If
k
=
1, we have
a
1
=
b
1
=
b
2
=
a
2
=
p
, so
b
=
c
=
p
for
p
not composite. If
k
>
1, consider that
a
k
−
1
>
a
k
by the choice of
k
, but
a
k
+
1
= |
3
a
k
−
2
a
k
−
1
|
, and
a
k
+
1
=
b
2
=
b
1
=
a
k
, so
a
k
+
1
=
2
a
k
−
1
−
3
a
k
, and
thus
a
k
−
1
=
2
p
. For
k
=
2, this means that
b
=
2
p
,
c
=
p
for
p
not composite.
If
k
>
2, the same approach yields
a
k
−
2
=
3
a
k
−
1
±
a
k
2
=
7
2
p
or
5
2
p
,
so
p
=
2. For
k
=
3, this gives solutions
b
=
7 or
b
=
5,
c
=
4. Because
3
·
5
±
4
2
and
3
·
7
±
4
2
are not integers, there are no solutions for
k
>
3.
Remark.
The reader may try to prove the following more general statement:
Let
f
∈
Z
[
X
1
, . . . ,
X
k
]
be a polynomial and F
(
n
)
=
f
(
n
,
2
n
,
3
n
, . . . , (
k
−
1
)
n
)
,
n
≥
1
. If
lim
n
→∞
F
(
n
)
= ∞
, then the set of primes dividing the terms of the
sequence
(
F
(
n
))
n
≥
1
is infinite.

---

342
II Solutions, 9. Some Special Problems in Number Theory
9.3.3
Nonstandard Sequences of Integers
Problem 9.3.21.
Let
{
a
n
}
be a sequence of integers such that for n
≥
1
,
(
n
−
1
)
a
n
+
1
=
(
n
+
1
)
a
n
−
2
(
n
−
1
).
If
2000
divides a
1999
, find the smallest n
≥
2
such that
2000
divides a
n
.
(1999 Bulgarian Mathematical Olympiad)
Solution.
First, we note that the sequence
a
n
=
2
n
−
2 works. Then writing
b
n
=
a
n
−
(
2
n
−
2
)
gives the recursion
(
n
−
1
)
b
n
+
1
=
(
n
+
1
)
b
n
.
For
n
≥
2, observe that
b
n
=
b
2
n
−
1
k
=
2
k
+
1
k
−
1
=
b
2
n
k
=
3
k
n
−
2
k
=
1
k
=
n
(
n
−
1
)
2
b
2
.
Thus when
n
≥
2, the solution to the original equation of the form
a
n
=
2
(
n
−
1
)
+
n
(
n
−
1
)
2
c
for some constant
c
. Plugging in
n
=
2 shows that
c
=
a
2
−
2 is an integer.
Now, because 2000
|
a
1999
we have
2
(
1999
−
1
)
+
1999
·
1998
2
c
≡
0
(
mod 2000
).
This implies
−
4
+
1001
c
≡
0
(
mod 2000
),
hence
c
≡
4
(
mod 2000
).
Then 2000
|
a
n
exactly when
2
(
n
−
1
)
+
2
n
(
n
−
1
)
≡
0
(
mod 2000
)
⇔
(
n
−
1
)(
n
+
1
)
≡
0
(
mod 1000
).
The number
(
n
−
1
)(
n
+
1
)
is divisible by 8 exactly when
n
is odd, and it is divisible
by 125 exactly when either
n
−
1 or
n
+
1 is divisible by 125. The smallest
n
≥
2
satisfying these requirements is
n
=
249.
Problem 9.3.22.
The sequence
(
a
n
)
n
≥
0
is defined by a
0
=
1
, a
1
=
3
, and
a
n
+
2
=
a
n
+
1
+
9
a
n
if n is even
,
9
a
n
+
1
+
5
a
n
if n is odd
.
Prove that
(a)
"
2000
k
=
1995
a
2
k
is divisible by
20
,
(b) a
2
n
+
1
is not a perfect square for any n
=
0
,
1
,
2
, . . .
.
(1995 Vietnamese Mathematical Olympiad)

---

9.3. Sequences of Integers
343
Solution.
(a) We will first prove that the sum is divisible by 4, then by 5. Note
that
a
n
+
2
≡
a
n
+
1
+
a
n
(
mod 4
)
whether
n
is odd or even. The sequence modulo
4 thus proceeds 1, 3, 0, 3, 3, 2, 1, 3,
. . .
in a cycle of 6, so the sum of squares
of any six consecutive terms is congruent to 1
2
+
3
2
+
0
2
+
3
2
+
3
2
+
2
2
≡
0
(
mod 4
)
.
Now let us work modulo 5, in which case
a
n
+
2
≡
a
n
+
1
+
4
a
n
if
n
is even and
a
n
+
2
≡
4
a
n
+
1
if
n
is odd. Hence the sequence modulo 5 proceeds 1, 3, 2, 3, 1, 4,
3, 2, 4, 1, 2, 3,
. . .
in a cycle of 8 beginning with
a
2
. This means that
a
2
1995
+· · ·+
a
2
2000
≡
a
2
3
+· · ·+
a
2
8
≡
3
2
+
1
2
+
4
2
+
3
2
+
2
2
+
4
2
≡
0
(
mod 5
).
(b) From part (a) we have
a
2
n
+
1
≡
2 or 3
(
mod 4
)
, which implies that
a
2
n
+
1
is not a square.
Problem 9.3.23.
Prove that for any natural number a
1
>
1
, there exists an in-
creasing sequence of natural numbers a
1
,
a
2
, . . .
such that a
2
1
+
a
2
2
+ · · · +
a
2
k
is
divisible by a
1
+
a
2
+ · · · +
a
k
for all k
≥
1
.
(1995 Russian Mathematical Olympiad)
Solution.
We will prove in fact that any finite sequence
a
1
, . . . ,
a
k
with the prop-
erty can be extended by a suitable
a
k
+
1
. Let
s
k
=
a
1
+ · · · +
a
k
and
t
k
=
a
2
1
+ · · · +
a
2
k
. Then we are seeking
a
k
+
1
such that
a
k
+
1
+
s
k
|
a
2
k
+
1
+
t
k
. This is
clearly equivalent to
a
k
+
1
+
s
k
|
s
2
k
+
t
k
. Why not, then, choose
a
k
+
1
=
s
2
k
−
s
k
+
t
k
?
Certainly this is greater than
a
k
and ensures that the desired property is satisfied.
Problem 9.3.24.
The sequence a
0
,
a
1
,
a
2
, . . .
satisfies
a
m
+
n
+
a
m
−
n
=
1
2
(
a
2
m
+
a
2
n
)
for all nonnegative integers m and n with m
≥
n. If a
1
=
1
, determine a
n
.
(1995 Russian Mathematical Olympiad)
Solution.
The relations
a
2
m
+
a
2
m
=
2
(
a
2
m
+
a
0
)
=
4
(
a
m
+
a
m
)
imply
a
2
m
=
4
a
m
,
as well as
a
0
=
0. Thus we compute
a
2
=
4,
a
4
=
16. Also,
a
1
+
a
3
=
(
a
2
+
a
4
)/
2
=
10 so
a
3
=
9. At this point we guess that
a
i
=
i
2
for all
i
≥
1.
We prove our guess by induction on
i
. Suppose that
a
j
=
j
2
for
j
<
i
. Then
the given equation with
m
=
i
−
1,
j
=
1 gives
a
i
=
1
2
(
a
2
i
−
2
+
a
2
)
−
a
i
−
2
=
2
a
i
−
1
+
2
a
1
−
a
i
−
2
=
2
(
i
2
−
2
i
+
1
)
+
2
−
(
i
2
−
4
i
+
4
)
=
i
2
.
Problem 9.3.25.
The sequence of real numbers a
1
,
a
2
,
a
3
, . . .
satisfies the initial
conditions a
1
=
2
, a
2
=
500
, a
3
=
2000
as well as the relation
a
n
+
2
+
a
n
+
1
a
n
+
1
+
a
n
−
1
=
a
n
+
1
a
n
−
1

---

344
II Solutions, 9. Some Special Problems in Number Theory
for n
=
2
,
3
,
4
, . . .
Prove that all the terms of this sequence are positive integers
and that
2
2000
divides the number a
2000
.
(1999 Slovenian Mathematical Olympiad)
First solution.
From the recursion relation it follows that
a
n
+
2
a
n
−
1
=
a
2
n
+
1
for
n
=
2
,
3
, . . .
. No term of our sequence can equal 0, and hence it is possible to
write
a
n
+
2
a
n
+
1
a
n
=
a
n
+
1
a
n
a
n
−
1
(
1
)
for
n
=
2
,
3
, . . .
. It follows by induction that the value of the expression
a
n
+
1
a
n
a
n
−
1
is constant, namely equal to
a
3
/
a
2
a
1
=
2. Thus
a
n
+
2
=
2
a
n
a
n
+
1
and all terms of
the sequence are positive integers.
From this new relation, we also know that
a
n
+
1
/
a
n
is an even integer for all
positive integers
n
. Write
a
2000
=
a
2000
a
1999
a
1999
a
1998
· · ·
a
2
a
1
a
1
.
In this product each of the 1999 fractions is divisible by 2, and
a
1
=
2 is even
as well. Thus
a
2000
is indeed divisible by 2
2000
.
Second solution.
Note that
a
n
=
2
F
n
+
2
−
1
·
5
3
F
n
−
1
, proved by induction by using
equation (1) in the previous solution, where
F
n
are the Fibonacci numbers,
n
≥
1.
Hence the divisibility is a consequence of
F
2002
≥
2001.
Problem 9.3.26.
Let k be a fixed positive integer. We define the sequence a
1
,
a
2
,
. . .
by a
1
=
k
+
1
and the recursion a
n
+
1
=
a
2
n
−
ka
n
+
k for n
≥
1
. Prove that
a
m
and a
n
are relatively prime for distinct positive integers m and n.
First solution.
We claim that
a
n
=
n
−
1
i
=
0
a
i
+
k
,
n
>
0
,
assuming that
a
0
=
1. Since
a
j
+
1
−
k
=
a
j
(
a
j
−
k
)
, we have
a
n
−
k
=
n
−
1
j
=
1
a
j
+
1
−
k
a
j
−
k
=
n
−
1
j
=
1
a
j
,
which is what we wanted.
Therefore, we have that
a
n
≡
k
(
mod
a
i
)
for
i
<
n
. Hence, if there exist
integers
d
>
1,
x
,
y
≥
1 such that
d
|
a
x
and
d
|
a
y
,
d
divides
k
. We now show

---

9.3. Sequences of Integers
345
that for
i
>
0,
a
i
≡
1
(
mod
k
)
by induction on
i
. For the base case,
a
1
=
k
+
1
≡
1
(
mod
k
)
. Now assume that
a
i
≡
1
(
mod
k
)
. Then,
a
i
+
1
≡
a
2
i
−
ka
i
+
k
≡
a
2
i
≡
1
(
mod
k
)
. Thus, because all common divisors
d
of
a
x
and
a
y
must be divisors
of
k
, we have
a
x
≡
1
(
mod
d
)
and
a
y
≡
1
(
mod
d
)
. Therefore, no such divisors
exist and
a
i
is relatively prime to
a
j
for all
i
,
j
>
0, as desired.
Second solution.
First, by induction on
n
, it follows that
a
n
≡
1
(
mod
k
)
for
all
n
. Then it follows by induction on
m
that
a
m
≡
k
(
mod
a
n
)
for all
m
>
n
.
Therefore for
m
>
n
we have gcd
(
a
m
,
a
n
)
=
gcd
(
k
,
a
n
)
=
gcd
(
k
,
1
)
=
1.
Problem 9.3.27.
Suppose the sequence of nonnegative integers a
1
, a
2
, . . .
, a
1997
satisfies
a
i
+
a
j
≤
a
i
+
j
≤
a
i
+
a
j
+
1
for all i
,
j
≥
1
with i
+
j
≤
1997
. Show that there exists a real number x such
that a
n
= 
nx
for all
1
≤
n
≤
1997
.
(1997 USA Mathematical Olympiad)
Solution.
Any
x
that lies in all of the half-open intervals
I
n
=
1
a
n
n
,
a
n
+
1
n
,
n
=
1
,
2
, . . . ,
1997
,
will have the desired property. Let
L
=
max
1
≤
n
≤
1997
a
n
n
=
a
p
p
and
U
=
min
1
≤
n
≤
1997
a
n
+
1
n
=
a
q
+
1
q
.
We shall prove that
a
n
n
<
a
m
+
1
m
,
or equivalently,
ma
n
<
n
(
a
m
+
1
)
(
∗
)
for all
m
,
n
ranging from 1 to 1997. Then
L
<
U
, since
L
≥
U
implies that
(
∗
)
is
violated when
n
=
p
and
m
=
q
. Any point
x
in
[
L
,
U
)
has the desired property.
We prove
(
∗
)
for all
m
,
n
ranging from 1 to 1997 by strong induction. The
base case
m
=
n
=
1 is trivial. The induction step splits into three cases. If
m
=
n
, then
(
∗
)
certainly holds. If
m
>
n
, then the induction hypothesis gives
(
m
−
n
)
a
n
<
n
(
a
m
−
n
+
1
)
, and adding
n
(
a
m
−
n
+
a
n
)
≤
na
m
yields
(
∗
)
. If
m
<
n
,
then the induction hypothesis yields
ma
n
−
m
< (
n
−
m
)(
a
m
+
1
)
, and adding
ma
n
≤
m
(
a
m
+
a
n
−
m
+
1
)
gives
(
∗
)
.
Problem 9.3.28.
The sequence
{
a
n
}
is given by the following relation:
a
n
+
1
=
a
n
−
1
2
,
if a
n
≥
1
,
2
a
n
1
−
a
n
,
if a
n
<
1
.

---

346
II Solutions, 9. Some Special Problems in Number Theory
Given that a
0
is a positive integer, a
n
=
2
for each n
=
1
,
2
, . . . ,
2001
, and
a
2002
=
2
, find a
0
.
(2002 St. Petersburg City Mathematical Olympiad)
Solution.
Answer:
a
0
=
3
·
2
2002
−
1.
Suppose we are given
a
n
+
1
. Then there are exactly two possibilities for
a
n
. If
a
n
≥
1, then the first rule gives
a
n
=
2
a
n
+
1
+
1 (which is at least 1 as required). If
a
n
<
1, then the second rule gives
a
n
=
a
n
+
1
a
n
+
1
+
2
(which is less than 1 as required).
Thus the problem amounts to the following: Start with
a
2002
=
2 and repeatedly
apply one of the two transformations
a
n
=
2
a
n
+
1
+
1
,
a
n
+
1
a
n
+
1
+
2
.
Suppose you never again get
a
n
=
2 and suppose
a
0
is an integer. Then what
is
a
0
?
If we apply the first rule 2002 times, then
a
n
+
1 doubles every step (and in