|
II Solutions, 3. Floor Function and Fractional Part
(2) (Landau) If p and q are odd, then
p
−
1
2
k
=
1
%
kq
p
&
+
q
−
1
2
k
=
1
%
kp
q
&
=
(
p
−
1
)(
q
−
1
)
4
.
Solution.
(1) Let
f
: [
0
,
m
] →
0
,
mq
p
,
f
(
x
)
=
q
p
x
. Because gcd
(
p
,
q
)
=
1
and
m
<
p
, we have
n
(
G
f
)
=
1, and the desired equality follows from Theorem
3.2.1.
(2) In the previous identity we take
m
=
p
2
. It follows that
s
=
q
−
1
2
, and the
conclusion follows.
3.3
A Useful Result
Problem 3.3.3.
Let p be an odd prime and let q be an integer that is not divisible
by p. Show that
p
−
1
k
=
1
%
(
−
1
)
k
k
2
q
p
&
=
(
p
−
1
)(
q
−
1
)
2
.
(2005 “Alexandru Myller” Romanian Regional Contest)
Solution.
For
f
:
Z
∗
+
→
R
,
f
(
s
)
=
(
−
1
)
s
s
2
, conditions (i) and (ii) in Theo-
rem 3.3.1 are both satisfied. We obtain
p
−
1
k
=
1
%
(
−
1
)
k
k
2
q
p
&
=
q
p
(
−
1
2
+
2
2
− · · · +
(
p
−
1
)
2
)
−
p
−
1
2
=
q
p
·
p
(
p
−
1
)
2
−
p
−
1
2
;
hence
p
−
1
k
=
1
%
(
−
1
)
k
k
2
q
p
&
=
(
p
−
1
)(
q
−
1
)
2
.
Remarks.
(1) By taking
q
=
1 we get
p
−
1
k
=
1
%
(
−
1
)
k
k
2
p
&
=
0
.
Using now the identity
−
x
=
1
−
x
,
x
∈
R
, the last display takes the form
p
−
1
k
=
1
(
−
1
)
k
%
k
2
p
&
=
1
−
p
2
.
3.3. A Useful Result
265
(2) Similarly, applying Theorem 3.3.1 to
f
:
Z
∗
+
→
R
,
f
(
s
)
=
(
−
1
)
s
s
4
yields
p
−
1
k
=
1
%
(
−
1
)
k
k
4
q
p
&
=
q
(
p
−
1
)(
p
2
−
p
−
1
)
2
−
p
−
1
2
.
Taking
q
=
1 gives
p
−
1
k
=
1
%
(
−
1
)
k
k
4
p
&
=
(
p
−
2
)(
p
−
1
)(
p
+
1
)
2
.
Problem 3.3.4.
Let p be an odd prime. Show that
p
−
1
k
=
1
k
p
−
k
p
≡
p
+
1
2
(
mod
p
).
(2006 “Alexandru Myller” Romanian Regional Contest)
Solution.
For
f
(
s
)
=
s
p
p
, conditions (i) and (ii) in Theorem 3.3.1 are also satis-
fied, and for
q
=
1 we have
p
−
1
k
=
1
%
k
p
p
2
&
=
1
p
p
−
1
k
=
1
k
p
p
−
p
−
1
2
=
1
p
p
−
1
k
=
1
k
p
p
−
1
p
2
p
−
1
k
=
1
k
+
1
p
2
p
(
p
−
1
)
2
−
p
−
1
2
=
1
p
p
−
1
k
=
1
k
p
−
k
p
−
1
p
·
(
p
−
1
)
2
2
.
It follows that
p
−
1
k
=
1
k
p
−
k
p
−
(
p
−
1
)
2
2
=
p
p
k
=
1
%
k
p
p
2
&
,
i.e.,
p
−
1
k
=
1
k
p
−
k
p
≡
(
p
−
1
)
2
2
(
mod
p
).
The conclusion follows since
(
p
−
1
)
2
2
≡
p
2
+
1
2
≡
p
+
1
2
(
mod
p
).
266
II Solutions, 3. Floor Function and Fractional Part
Remarks.
(1) For each
k
=
1
,
2
, . . . ,
p
−
1 denote by
r
k
the remainder when
k
p
is divided by
p
2
. We have
k
p
=
%
k
p
p
2
&
p
2
+
r
k
,
k
=
1
,
2
, . . . ,
p
−
1
,
hence
p
−
1
k
=
1
k
p
=
p
2
p
−
1
k
=
1
%
k
p
p
2
&
+
p
−
1
k
=
1
r
k
= −
p
2
(
p
−
1
)
2
+
p
−
1
k
=
1
r
k
+
p
−
1
k
=
1
k
p
.
It follows that
r
1
+
r
2
+ · · · +
r
p
−
1
=
p
2
(
p
−
1
)
2
.
(2) The formula in our problem shows that the sum of the quotients ob-
tained when
k
p
−
k
is divided by
p
(Fermat’s little theorem) is congruent to
p
+
1
2
modulo
p
.
4
Digits of Numbers
4.1
The Last Digits of a Number
Problem 4.1.4.
In how may zeros can the number
1
n
+
2
n
+
3
n
+
4
n
end for
n
∈
N
?
(1998 St. Petersburg City Mathematical Olympiad)
Solution.
There can be no zeros (e.g.,
n
=
4), one zero
(
n
=
1
)
, or two zeros
(
n
=
2
)
. In fact, for
n
≥
3, 2
n
and 4
n
are divisible by 8, while 1
n
+
3
n
is
congruent to 2 or 4 mod 8. Thus the sum cannot end in three or more zeros.
Problem 4.1.5.
Find the last five digits of the number
5
1981
.
Solution.
First, we prove that 5
1981
=
5
5
(
mod 10
5
)
. We have
5
1981
−
5
5
=
(
5
1976
−
1
)
5
5
=
5
5
[
(
5
8
)
247
−
1
]
=
M
[
5
5
(
5
8
−
1
)
] =
M
[
5
5
(
5
4
−
1
)(
5
4
+
1
)
]
=
M
[
5
5
(
5
−
1
)(
5
+
1
)(
5
2
+
1
)(
5
4
+
1
)
]
=
M
5
2
2
5
=
M
100
,
000
.
Therefore 5
1981
=
M
100
,
000
+
5
5
=
M
100
,
000
+
3125, so 03125 are the
last five digits of the number 5
1981
. Of course, the relation
a
=
M
b
means that
a
is a multiple of
b
.
Problem 4.1.6.
Consider all pairs
(
a
,
b
)
of natural numbers such that the product
a
a
b
b
, written in base
10
, ends with exactly
98
zeros. Find the pair
(
a
,
b
)
for which
the product ab is smallest.
(1998 Austrian–Polish Mathematics Competition)
Solution.
Let
a
2
be the maximum integer such that 2
a
2
|
a
. Define
a
5
,
b
2
, and
b
5
similarly. Our task translates into the following: find
a
,
b
such that
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
T. Andreescu and D. Andrica,
Number Theory
,
DOI: 10.1007/b11856_15,
267
268
II Solutions, 4. Digits of Numbers
min
{
a
5
a
+
b
5
b
,
a
2
a
+
b
2
b
} =
98 and
ab
is minimal. Since 5
|
a
5
a
+
b
5
b
, we
have
a
5
a
+
b
5
b
>
98 and min
{
a
5
a
+
b
5
b
,
a
2
a
+
b
2
b
} =
a
2
a
+
b
2
b
=
98.
Note that if 5
|
gcd
(
a
,
b
)
, then
a
2
a
+
b
2
b
=
98, contradiction. Without loss
of generality, suppose that
a
5
≥
1 and
b
5
=
0. Let
a
=
2
a
2
5
a
5
x
and 2
b
2
y
,
gcd
(
2
,
x
)
=
gcd
(
5
,
x
)
=
gcd
(
2
,
y
)
=
1. Then
a
5
a
=
a
5
(
2
a
2
5
a
5
x
) >
98 and
a
2
a
=
a
2
(
2
a
2
5
a
5
x
)
≤
98. So
a
5
>
a
2
. We consider the following cases.
(a)
a
2
=
0. Then
b
2
(
2
b
2
y
)
=
98. So
b
2
=
1,
y
=
49,
b
=
98. Since
a
5
(
5
a
5
x
)
≥
98 and
x
is odd,
a
=
5
a
5
x
≥
125 for
a
5
≥
3;
x
≥
3 and
a
≥
75 for
a
5
=
2;
x
≥
21 and
a
≥
105 for
a
5
=
1. Hence for
a
2
=
0,
b
=
98,
a
≥
75.
(b)
a
2
≥
1. Then
a
5
≥
2. We have 2
a
2
5
a
5
x
≤
98 and 5
a
5
x
≤
49. Thus
a
5
=
2,
x
=
1,
a
2
=
1,
a
=
50. Then
b
2
b
=
48. Let
b
=
2
b
2
y
. Then
b
2
(
2
b
2
y
)
=
48,
which is impossible.
From the above, we have
(
a
,
b
)
=
(
75
,
98
)
or
(
98
,
75
)
.
Do'stlaringiz bilan baham: |
