Number Theory: Structures, Examples, and Problems

I Fundamentals, 1. Divisibility
a contradiction, whereas if
a
≥
3, then 5
l
−
1
≥
3
·
2
m
while 5
l
+
1
≤
2
(
2
m
+
s
)
,
another contradiction.
Problem 1.5.4.
Find an integer n with
100
≤
n
≤
1997
such that n divides
2
n
+
2
.
(1997 Asian Pacific Mathematics Olympiad)
Solution.
Note that 2 divides 2
n
+
2 for all
n
. Also, 11 divides 2
n
+
2 if and only
if
n
≡
6
(
mod 10
)
, and 43 divides 2
n
+
2 if and only if
n
≡
8
(
mod 14
)
. Since
n
=
946
=
2
·
11
·
43 satisfies both congruences,
n
divides 2
n
+
2.
Remark.
Actually, one can prove that there are infinitely many
n
such that
n
|
2
n
+
2. Also, any such
n
is even, since by a theorem of W. Sierpi´nski
6
we cannot
have
n
|
2
n
−
1
+
1 unless
n
=
1 (see also Problem 7.1.16).
Problem 1.5.5.
The number
99
. . .
99
(with
1997
nines) is written on a black-
board. Each minute, one number written on the blackboard is factored into two
factors and erased, each factor is (independently) increased or diminished by
2
,
and the resulting two numbers are written. Is it possible that at some point all of
the numbers on the blackboard equal
9
?
(1997 St. Petersburg City Mathematical Olympiad)
Solution.
The answer is No. Indeed, note that 99
. . .
99 (with 1997 nines)
=
10
1997
−
1 is congruent to 3 modulo 4. If 99
. . .
99 (with 1997 nines)
=
ab
,
for some integers
a
and
b
, then for example
a
is congruent to 1 modulo 4 and
b
is congruent to 3 modulo 4. Changing
a
and
b
by 2 in either direction we find
numbers congruent to 3, respectively to 1 modulo 4. Hence at any point we get
numbers of different residues modulo 4, so these numbers cannot be equal.
Problem 1.5.6.
Find the smallest positive integer that can be written both as (i)
a sum of
2002
positive integers (not necessarily distinct), each of which has the
same sum of digits and (ii) as a sum of
2003
positive integers (not necessarily
distinct) each of which has the same sum of digits.
(2002 Russian Mathematical Olympiad)
Solution.
The answer is 10010. First observe that this is indeed a solution:
10010
=
2002
·
5
=
1781
·
4
+
222
·
13, so we may express 10010 as the sum
of 2002 fives or of 1781 fours and 222 thirteens, where 1781
+
222
=
2003. To
prove minimality, observe that a number is congruent modulo 9 to the sum of its
digits, so two positive integers with the same digit sum have the same remainders
modulo 9. Let
k
1
be the digit sum of the 2002 numbers and
k
2
the digit sum of the
2003 numbers. Then 4
k
1
≡
2002
k
1
≡
2003
k
2
≡
5
k
2
(
mod 9
)
. If
k
1
≥
5, the sum
of the 2002 numbers is at least 10010; if
k
2
≥
5, the sum of the 2003 numbers
is greater than 10010. Since
k
1
+
k
2
≡
0
(
mod 9
)
, we have
k
1
+
k
2
≥
9. Hence
either
k
1
≥
5 or
k
2
≥
5, and the minimal integer is 10010.
6
Wacław Sierpi´nski (1882–1969), Polish mathematician with fundamental work in the area of set
theory, point set topology, and number theory.

---