|
Second solution.
In problems of this type, computing
z
n
=
√
x
n
asymptotically
usually works.
From lim
n
→∞
b
2
n
(
b
−
1
)
x
n
=
1 we infer that lim
n
→∞
b
n
z
n
=
√
b
−
1. Furthermore,
from
(
bz
n
+
z
n
+
1
)(
bz
n
−
z
n
+
1
)
=
b
2
x
n
−
x
n
+
1
=
b
n
+
2
+
3
b
2
−
2
b
−
5
we obtain
lim
n
→∞
(
bz
n
−
z
n
+
1
)
=
b
√
b
−
1
2
.
2.1. Perfect Squares
247
Since the
z
n
’s are integers for all
n
≥
M
, we conclude that
bz
n
−
z
n
+
1
=
b
√
b
−
1
2
for all
n
sufficiently large. Hence
b
−
1 is a perfect square, and moreover,
b
divides
2
z
n
+
1
for all large
n
. Hence
b
divides 2
x
n
+
1
≡
10
(
mod
b
)
for all large
n
. It
follows that
b
|
10; hence the only possibility is
b
=
10.
Problem 2.1.16.
Do there exist three natural numbers greater than
1
, such that
the square of each, minus one, is divisible by each of the others?
(1996 Russian Mathematical Olympiad)
Solution.
Such integers do not exist. Suppose
a
≥
b
≥
c
satisfy the desired
condition. Since
a
2
−
1 is divisible by
b
, the numbers
a
and
b
are relatively prime.
Hence the number
c
2
−
1, which is divisible by
a
and
b
, must be a multiple of
ab
,
so in particular
c
2
−
1
≥
ab
. But
a
≥
c
and
b
≥
c
, so
ab
≥
c
2
, a contradiction.
Problem 2.1.17.
(a) Find the first positive integer whose square ends in three
4
’s.
(b) Find all positive integers whose squares end in three
4
’s.
(c) Show that no perfect square ends with four
4
’s.
(1995 United Kingdom Mathematical Olympiad)
Solution.
It is easy to check that 38
2
=
1444 is the first positive integer whose
square ends in three 4’s. Now let
n
be any such positive integer. Then
n
2
−
38
2
=
(
n
−
38
)(
n
+
38
)
is divisible by 1000
=
2
3
·
5
3
. Hence at least one of
n
−
38,
n
+
38 is divisible by 4, and thus both are, since their difference is 76
=
4
·
19.
Since 5
76, then 5 divides only one of the two factors. Consequently
n
−
38 or
n
+
38 is a multiple of 4
·
5
3
=
500, so we have
n
=
500
k
±
38. It is easy to check
that the square of all numbers of this form (where
k
is a positive integer) end in
three 4’s.
Note that (c) follows from Problem 2.1.12.
Problem 2.1.18.
Let abc be a prime. Prove that b
2
−
4
ac cannot be a perfect
square.
(Mathematical Reflections)
First solution.
Assume that
b
2
−
4
ac
is a perfect square and then let
b
2
−
4
ac
=
k
2
,
k
∈
N
. We have
4
a
·
abc
=
4
a
·
(
100
a
+
10
b
+
c
)
=
400
a
2
+
40
ab
+
4
ac
=
(
20
a
+
b
)
2
−
(
b
2
−
4
ac
)
=
(
20
a
+
b
+
k
)(
20
a
+
b
−
k
).
(
∗
)
Since
a
,
b
,
k
∈
N
, then
(
20
a
+
b
+
k
)
∈
Z
and
(
20
a
+
b
−
k
)
∈
Z
. Since
abc
is a prime, then according to
(
∗
)
,
abc
|
(
20
a
+
b
+
k
)
or
abc
|
(
20
a
+
b
−
k
).
248
II Solutions, 2. Powers of Integers
It follows that
abc
≤
20
a
+
b
+
k
or
abc
≤
20
a
+
b
−
k
. This leads to a
contradiction, since 20
a
+
b
+
k
<
abc
and 20
a
+
b
−
k
<
abc
. Hence,
abc
cannot be a perfect square. This completes our proof.
Second solution.
It is clear that
a
,
b
,
c
∈
N
,
a
=
0, and gcd
(
a
,
b
,
c
)
=
1. If
x
1
=
u
and
x
2
=
v
are the solutions of the equation
ax
2
+
bx
+
c
=
0, then we
obtain the factorization
ax
2
+
bx
+
c
=
a
(
x
−
u
)(
x
−
v)
. On the other hand, if
the discriminant
D
=
b
2
−
4
ac
=
h
2
,
h
∈
N
, is a perfect square, the solutions of
the equation
ax
2
+
bx
+
c
are rational. The factorization is such that
a
x
−
−
b
+
h
2
a
x
−
−
b
−
h
2
a
=
p
,
where
p
is prime. We have
x
=
10 and
abc
=
a
·
10
2
+
b
·
10
+
c
=
p
; thus
(
2
ax
+
b
−
h
)(
2
ax
+
b
+
h
)
=
4
ap
.
Since
b
and
h
have the same parity, we get
ax
+
b
−
h
2
ax
+
b
+
h
2
=
ap
.
One of the factors on the left-hand side should be divisible by
p
, but clearly
ax
+
b
−
h
2
,
ax
+
b
+
h
2
≤
100, a contradiction. Thus
b
2
−
4
ac
cannot be a
perfect square.
Problem 2.1.19.
For each positive integer n, denote by s
(
n
)
the greatest integer
such that for all positive integers k
≤
s
(
n
)
, n
2
can be expressed as a sum of
squares of k positive integers.
(a) Prove that s
(
n
)
≤
n
2
−
14
for all n
≥
4
.
(b) Find a number n such that s
(
n
)
=
n
2
−
14
.
(c) Prove that there exist infinitely many positive integers n such that
s
(
n
)
=
n
2
−
14
.
(33rd International Mathematical Olympiad)
Solution.
(a) Representing
n
2
as a sum of
n
2
−
13 squares is equivalent to repre-
senting 13 as a sum of numbers of the form
x
2
−
1,
x
∈
N
, such as 0
,
3
,
8
,
15
, . . .
.
But it is easy to check that this is impossible, and hence
s
(
n
)
≤
n
2
−
14.
(b) Let us prove that
s
(
13
)
=
13
2
−
14
=
155. Observe that
13
2
=
8
2
+
8
2
+
4
2
+
4
2
+
3
2
=
8
2
+
8
2
+
4
2
+
4
2
+
2
2
+
2
2
+
1
2
=
8
2
+
8
2
+
4
2
+
3
2
+
3
2
+
2
2
+
1
2
+
1
2
+
1
2
.
2.1. Perfect Squares
249
Given any representation of
n
2
as a sum of
m
squares one of which is even,
we can construct a representation as a sum of
m
+
3 squares by dividing the
square into four equal squares. Thus the first equality enables us to construct
representations with 5
,
8
,
11
, . . . ,
155 squares, the second to construct ones with
7
,
10
,
13
, . . . ,
154 squares, and the third with 9
,
12
, . . . ,
153 squares. It remains
only to represent 13
2
as a sum of
k
=
2
,
3
,
4
,
6 squares. This can be done as
follows:
13
2
=
12
2
+
5
2
=
12
2
+
4
2
+
3
2
=
11
2
+
4
2
+
4
2
+
4
2
=
12
2
+
3
2
+
2
2
+
2
2
+
2
2
+
2
2
.
(c) We shall prove that whenever
s
(
n
)
=
n
2
−
14 for some
n
≥
13, it also
holds that
s
(
2
n
)
=
(
2
n
)
2
−
14. This will imply that
s
(
n
)
=
n
2
−
14 for any
n
=
2
t
·
13.
If
n
2
=
x
2
1
+ · · · +
x
2
r
, then we have
(
2
n
)
2
=
(
2
x
1
)
2
+ · · · +
(
2
x
r
)
2
. Replacing
(
2
x
i
)
2
with
x
2
i
+
x
2
i
+
x
2
i
+
x
2
i
as long as it is possible, we can obtain representations
of
(
2
n
)
2
consisting of
r
,
r
+
3
, . . . ,
4
r
squares. This gives representations of
(
2
n
)
2
into
k
squares for any
k
≤
4
n
2
−
62. Further, we observe that each number
m
≥
14
can be written as a sum of
k
≥
m
numbers of the form
x
2
−
1,
x
∈
N
, which is
easy to verify. Therefore if 2
n
2
≤
k
≤
4
n
2
−
14, it follows that 4
n
2
−
k
is a sum
of
k
numbers of the form
x
2
−
1 (since
k
≥
4
n
2
−
k
≥
14), and consequently 4
n
2
is a sum of
k
squares.
Remark.
One can find exactly the value of
s
(
n
)
for each
n
:
s
(
n
)
=
⎧
⎨
⎩
1
,
if
n
has a prime divisor congruent to 3 mod 4
,
2
,
if
n
is of the form 5
·
2
k
,
k
a positive integer
,
n
2
−
14
,
otherwise
.
Problem 2.1.20.
Let A be the set of positive integers representable in the form
a
2
+
2
b
2
for integers a
,
b with b
=
0
. Show that if p
2
∈
A for a prime p, then
p
∈
A.
(1997 Romanian International Mathematical Olympiad Team Selection Test)
Solution.
The case
p
=
2 is easy, so assume
p
>
2. Note that if
p
2
=
a
2
+
2
b
2
,
then 2
b
2
=
(
p
−
a
)(
p
+
a
)
. In particular,
a
is odd, and since
a
cannot be divisible
by
p
, gcd
(
p
−
a
,
p
+
a
)
=
gcd
(
p
−
a
,
2
p
)
=
2. By changing the sign of
a
, we
may assume that
p
−
a
is not divisible by 4, and so
|
p
+
a
| =
m
2
,
|
p
−
a
| =
2
n
2
.
Since
|
a
|
<
|
p
|
, both
p
+
a
and
p
−
a
are actually positive, so we have
2
p
=
m
2
+
2
n
2
, so
p
=
n
2
+
2
(
m
/
2
)
2
.
250
Do'stlaringiz bilan baham: |
