|
1.7. Numerical Systems
243
Solution.
Let
d
i
be the digit associated with 10
i
in the base-10 representation of
n
, so that
n
=
d
m
d
m
−
1
. . .
d
0
for some integer
m
≥
0 (where
d
m
=
0). The stumps
of
n
are
"
m
j
=
k
d
j
10
j
−
k
for
k
=
1
,
2
, . . . ,
m
, and their sum is
T
(
n
)
=
m
k
=
1
m
j
=
k
d
j
10
j
−
k
=
m
j
=
1
d
j
j
k
=
1
10
j
−
k
=
m
j
=
1
d
j
j
−
1
k
=
0
10
k
=
m
j
=
1
d
j
10
j
−
1
10
−
1
.
Hence,
9
T
(
n
)
=
m
j
=
1
d
j
(
10
j
−
1
)
=
m
j
=
1
10
j
d
j
−
m
j
=
1
d
j
=
m
j
=
0
10
j
d
j
−
m
j
=
0
d
j
=
n
−
S
(
n
),
as desired.
Problem 1.7.21.
Let p be a prime number and m a positive integer. Show that
there exists a positive integer n such that there exist m consecutive zeros in the
decimal representation of p
n
.
(2001 Japanese Mathematical Olympiad)
Solution.
It is well known that if gcd
(
s
,
t
)
=
1, then
s
k
≡
1
(
mod
t
)
for some
k
>
0: indeed, of all the positive powers of
s
, some two
s
k
1
<
s
k
2
must be
congruent modulo
t
, and then
s
k
2
−
k
1
≡
1
(
mod
t
)
.
First suppose that
p
=
2
,
5. Then gcd
(
p
,
10
m
+
1
)
=
1, so there exists a
k
>
1 such that
p
k
≡
1
(
mod 10
m
+
1
)
. Then
p
k
=
a
·
10
m
+
1
+
1, so there are
m
consecutive zeros in the decimal representation of
p
k
.
Now suppose that
p
=
2. We claim that for any
a
, some power of 2 has
the following final
a
digits:
a
−
log 2
a
zeros, followed by the
log 2
a
digits
of 2
a
. Because gcd
(
2
,
5
a
)
=
1, there exists
k
such that 2
k
≡
1
(
mod 5
a
)
. Let
b
=
k
+
a
. Then 2
b
≡
2
a
(
mod 5
a
)
, and 2
b
≡
0
≡
2
a
(
mod 2
a
)
. Hence, 2
b
≡
2
a
(
mod 10
a
)
. Because 2
a
<
10
a
, it follows that 2
b
has the required property.
Now simply choose
a
such that
a
−
log 2
a
≥
m
(for instance, we could
choose
a
=
9
m
+
1
1
−
log 2
:
). Then 2
b
contains at least
m
consecutive zeros, as desired.
Finally, the case
p
=
5 is done analogously to the case
p
=
2.
Remark.
In fact, the property holds for every integer
p
≥
2. If
p
is a power of 2,
it is trivial. Otherwise, one can prove using Kronecker’s
1
theorem (stating that for
1
Leopold Kronecker (1823–1891), German mathematician with many contributions in the theory
of equations. He made major contributions in elliptic functions and the theory of algebraic numbers.
244
II Solutions, 1. Divisibility
α
∈
R
\
Q
the set of
{
n
α
}
with
n
∈
N
is dense in
[
0
,
1
]
) that the numbers
p
n
can
start with any combination of digits we may need, in particular with 1 00
. . .
0
m
times
.
Problem 1.7.22.
Knowing that
2
29
is a
9
-digit number whose digits are distinct,
without computing the actual number determine which of the ten digits is missing.
Justify your answer.
Solution.
It is not difficult to see that when divided by 9, the remainder is 5. The
ten-digit number containing all digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 is a multiple of 9,
because the sum of its digits has this property. So, in our nine-digit number, 4 is
missing.
Problem 1.7.23.
It is well known that the divisibility tests for division by
3
and
9
do not depend on the order of the decimal digits. Prove that
3
and
9
are the
only positive integers with this property. More exactly, if an integer d
>
1
has
the property that d
|
n implies d
|
n
1
, where n
1
is obtained from n through an
arbitrary permutation of its digits, then d
=
3
or d
=
9
.
Solution.
Let
d
be a
k
-digit number. Then among the
(
k
+
2
)
-digit numbers start-
ing with 10 there is at least one that is divisible by
d
. Denote it by 10
a
1
a
2
· · ·
a
k
.
The assumption implies that both numbers
a
1
a
2
· · ·
a
k
10 and
a
1
a
2
· · ·
a
k
01 are di-
visible by
d
, and then so is their difference. This difference equals 9, and the proof
is finished, since
d
may be only some divisor of 9.
Remark.
The following problem, given in an old Russian Mathematical Olympi-
ad, is much more restrictive and difficult:
Suppose that d
>
1
has the property that d
|
n implies d
|
n
1
, where n
1
is
obtained from n by reversing the order of its digits. Then d
|
99
.
Try to solve this
problem.
2
Powers of Integers
2.1
Perfect Squares
Problem 2.1.14.
Let x
,
y
,
z be positive integers such that
1
x
−
1
y
=
1
z
.
Let h be the greatest common divisor of x
,
y
,
z. Prove that hx yz and h
(
y
−
x
)
are perfect squares.
(1998 United Kingdom Mathematical Olympiad)
Solution.
Let
x
=
ha
,
y
=
hb
,
z
=
hc
. Then
a
,
b
,
c
are positive integers such
that gcd
(
a
,
b
,
c
)
=
1. Let gcd
(
a
,
b
)
=
g
. So
a
=
ga
,
b
=
gb
and
a
and
b
are
positive integers such that
gcd
(
a
,
b
)
=
gcd
(
a
−
b
,
b
)
=
gcd
(
a
,
a
−
b
)
=
1
.
We have
1
a
−
1
b
=
1
c
⇔
c
(
b
−
a
)
=
ab
⇔
c
(
b
−
a
)
=
a
b
g
.
Since gcd
(
a
,
b
,
c
)
=
1, we have gcd
(
g
,
c
)
=
1 and hence
g
|
b
−
a
. Since
gcd
(
b
−
a
,
a
)
=
gcd
(
b
−
a
,
b
)
=
1, we also have
b
−
a
|
g
. Hence
b
−
a
=
g
and
c
=
a
b
. Thus
hx yz
=
h
4
g
2
c
2
and
h
(
y
−
x
)
=
h
2
g
2
are perfect squares.
Problem 2.1.15.
Let b be an integer greater than
5
. For each positive integer n,
consider the number
x
n
=
11
. . .
1
n
−
1
22
. . .
2
n
5
,
written in base b. Provethat the following condition holds if and only if b
=
10
:
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
T. Andreescu and D. Andrica,
Number Theory
,
DOI: 10.1007/b11856_13,
245
246
II Solutions, 2. Powers of Integers
There exists a positive integer M such that for every integer n greater than M, the
number x
n
is a perfect square.
(44th International Mathematical Olympiad Shortlist)
First solution.
Assume that
b
≥
6 has the required property. Consider the se-
quence
y
n
=
(
b
−
1
)
x
n
. From the definition of
x
n
we easily find that
y
n
=
b
2
n
+
b
n
+
1
+
3
b
−
5
.
Then
y
n
y
n
+
1
=
(
b
−
1
)
2
x
n
x
n
+
1
is a perfect square for all
n
>
M
. Also,
straightforward calculation implies
b
2
n
+
1
+
b
n
+
2
+
b
n
+
1
2
−
b
3
2
<
y
n
y
n
+
1
<
b
2
n
+
1
+
b
n
+
2
+
b
n
+
1
2
+
b
3
2
.
Hence for every
n
>
M
there is an integer
a
n
such that
|
a
n
|
<
b
3
and
y
n
y
n
+
1
=
(
b
2
n
+
b
n
+
1
+
3
b
−
5
)(
b
2
n
+
2
+
b
n
+
2
+
3
b
−
5
)
=
b
2
n
+
1
+
b
n
+
1
(
b
+
1
)
2
+
a
n
2
.
(1)
Now considering this equation modulo
b
n
we obtain
(
3
b
−
5
)
2
≡
a
2
n
, so that
assuming that
n
>
3, we get
a
n
= ±
(
3
b
−
5
)
.
If
a
n
=
3
b
−
5, then substituting in (1) yields
1
4
b
2
n
(
b
4
−
14
b
3
+
45
b
2
−
52
b
+
20
)
=
0
,
with
b
=
10 the only solution greater than 5. Also, if
a
n
= −
3
b
+
5, we similarly
obtain
1
4
(
b
4
−
14
b
3
−
3
b
2
+
28
b
+
20
)
−
2
b
n
+
1
(
3
b
2
−
2
b
−
5
)
=
0
for each
n
, which is impossible.
For
b
=
10 we have
x
n
=
10
n
+
5
3
2
for all
n
(see Problem 2.1.8). This proves
the statement.
Do'stlaringiz bilan baham: |
