|
3.3. A Useful Result
75
Additional Problems
Problem 3.3.3.
Let
p
be an odd prime and let
q
be an integer that is not divisible
by
p
. Shows that
p
−
1
k
=
1
%
(
−
1
)
k
k
2
q
p
&
=
(
p
−
1
)(
q
−
1
)
2
.
(2005 “Alexandru Myller” Romanian Regional Contest)
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)
4
Digits of Numbers
4.1
The Last Digits of a Number
Let
a
n
a
1
· · ·
a
0
be the decimal representation of the positive integer
N
. The last
digit of
N
is
l
(
N
)
=
a
0
, and for
k
≥
2, the last
k
digits of
N
are
l
k
(
N
)
=
a
k
−
1
· · ·
a
0
. These simple concepts appear in numerous situations.
It is useful to point out the last digit of
k
n
, where
k
=
2
,
3
, . . . ,
9 and
n
>
0:
l
(
2
n
)
=
⎧
⎪
⎪
⎨
⎪
⎪
⎩
6
,
n
≡
0
(
mod 4
),
2
,
n
≡
1
(
mod 4
),
4
,
n
≡
2
(
mod 4
),
8
,
n
≡
3
(
mod 4
),
l
(
3
n
)
=
⎧
⎪
⎪
⎨
⎪
⎪
⎩
1
,
n
≡
0
(
mod 4
),
3
,
n
≡
1
(
mod 4
),
9
,
n
≡
2
(
mod 4
),
7
,
n
≡
3
(
mod 4
),
l
(
4
n
)
=
6
,
n
≡
0
(
mod 2
),
4
,
n
≡
1
(
mod 2
),
l
(
5
n
)
=
5
,
l
(
6
n
)
=
6
,
l
(
7
n
)
=
⎧
⎪
⎪
⎨
⎪
⎪
⎩
1
,
n
≡
0
(
mod 4
),
7
,
n
≡
1
(
mod 4
),
9
,
n
≡
2
(
mod 4
),
3
,
n
≡
3
(
mod 4
),
l
(
8
n
)
=
⎧
⎪
⎪
⎨
⎪
⎪
⎩
6
,
n
≡
0
(
mod 4
),
8
,
n
≡
1
(
mod 4
),
4
,
n
≡
2
(
mod 4
),
2
,
n
≡
3
(
mod 4
),
l
(
9
n
)
=
1
,
n
≡
0
(
mod 2
),
9
,
n
≡
1
(
mod 2
).
It is clear that if
l
(
N
)
=
0, then
l
n
(
N
n
)
=
0
. . .
0
n
times
, and if
l
(
N
)
=
1, then
l
(
N
n
)
=
1 for all
n
≥
2.
Problem 4.1.1.
What is the final digit of
. . .
((
7
7
)
7
)
7
. . .
7
?
There are 1001
7
’s in the formula.
Solution.
The final digit of a (decimal) number is its remainder modulo 10. Now
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
77
T. Andreescu and D. Andrica,
Number Theory
,
DOI: 10.1007b11856_4,
78
I Fundamentals, 4. Digits of Numbers
7
2
=
49
≡ −
1
(
mod 10
)
. So 7
7
=
(
7
2
)
3
·
7
≡ −
7
(
mod 10
)
, and
(
7
7
)
7
≡
(
−
7
)
7
≡ −
(
7
7
)
≡ −
(
−
7
)
≡
7
(
mod 10
).
Proceeding in this way, we see that
(
7
7
)
7
7
≡ −
7
(
mod 10
)
, and in general,
. . .
((
7
7
)
7
)
7
. . .
7
≡ ±
7
(
mod 10
),
where the sign is
+
if altogether there is an odd number of 7’s in the formula, and
−
if there is an even number of 7’s. Now, 1001 is odd. So the final digit of the
given formula is 7.
Problem 4.1.2.
Prove that every positive integer has at least as many (positive)
divisors whose last decimal digit is
1
or
9
as divisors whose last digit is
3
or
7
.
(1997 St. Petersburg City Mathematical Olympiad)
Solution.
Let
d
1
(
m
),
d
3
(
m
),
d
7
(
m
),
d
9
(
m
)
be the numbers of divisors of
m
ending
in 1, 3, 7, 9, respectively. We prove the claim by induction on
m
; it holds obviously
for
m
a prime power, and if
m
is composite, write
m
=
pq
with
p
,
q
coprime,
and note that
d
1
(
m
)
−
d
3
(
m
)
−
d
7
(
m
)
+
d
9
(
m
)
=
(
d
1
(
p
)
−
d
3
(
p
)
−
d
7
(
p
)
+
d
9
(
p
))(
d
1
(
q
)
−
d
3
(
q
)
−
d
7
(
q
)
+
d
9
(
q
)).
For instance,
d
3
(
m
)
=
d
1
(
p
)
d
3
(
q
)
+
d
3
(
p
)
d
1
(
q
)
+
d
7
(
p
)
d
9
(
q
)
+
d
9
(
p
)
d
7
(
q
).
Problem 4.1.3.
Find the least positive integer n with the following properties:
(a) the last digit of its decimal representation is
6
;
(b) by deleting the last digit
6
and replacing it in front of the remaining digits
one obtains a number four times greater than the given number.
(4th International Mathematical Olympiad)
Solution.
Let
n
=
10
k
a
k
+
10
k
−
1
a
k
−
1
+ · · · +
10
a
1
+
6 be the required number.
Writing
n
in the form
n
=
10
N
+
6, where 10
k
−
1
<
N
<
10
k
, the condition (b)
becomes:
4
(
10
N
+
6
)
=
6
·
10
k
+
N
.
Thus, we obtain
39
N
=
6
·
10
k
−
24
,
and equivalently
13
N
=
2
(
10
k
−
4
).
4.2. The Sum of the Digits of a Number
79
Thus, we obtain that 10
k
≡
4
(
mod 13
)
.
It is more convenient to write
(
−
3
)
k
≡
4
(
mod 13
).
From the conditions of the problem, the least
k
with this property is required.
We have
(
−
3
)
2
≡
9
(
mod 13
), (
−
3
)
3
≡ −
27
(
mod 13
)
≡ −
1
(
mod 13
),
(
−
3
)
5
≡
(
−
3
)
2
(
−
3
)
3
≡ −
9
≡
4
(
mod 13
).
Then,
k
=
5 is the least positive solution of the equation. Thus,
13
N
=
2
·
99996
⇒
N
=
15384
⇒
n
=
153846
.
This number satisfies (b).
Additional Problems
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)
Problem 4.1.5.
Find the last 5 digits of the number 5
1981
.
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)
4.2
The Sum of the Digits of a Number
For a positive integer
N
=
a
n
a
n
−
1
· · ·
a
0
in decimal representation we denote by
S
(
N
)
the sum of its digits
a
0
+ · · · +
a
n
−
1
+
a
n
. Problems involving the function
S
defined above appear frequently in various contexts. We present a few basic
properties.
(1)
S
(
N
)
=
N
−
9
"
k
≥
1
#
N
10
k
$
;
(2) 9
|
N
−
S
(
N
)
;
(3) (subadditivity):
S
(
N
1
+
N
2
)
≤
S
(
N
1
)
+
S
(
N
2
)
;
(4)
S
(
N
1
N
2
)
≤
min
(
N
1
S
(
N
2
),
N
2
S
(
N
1
))
;
(5) (submultiplicity):
S
(
N
1
N
2
)
≤
S
(
N
1
)
S
(
N
2
)
.
Property (2) is in fact Property 1.7.2, Criterion 1(b).
80
Do'stlaringiz bilan baham: |
