234 CHAPTER 7 NUMBER THEORY
called the digital sum of n.
(b) Prove that the digital sum of the product of
any two twin primes, other than 3 and 5, is 8.
(Twin primes are primes that are consecutive
odd numbers, such as 17 and 19.)
(c) (IMO 1975) Let N = 44444444. Find
l(f(f(n))), without a calculator.
7.2. 12 Prove, using the pigeonhole principle, that
there must be a power of 17 that ends with the digits
0000 I. Can you generalize this?
7.2. 13 The order of a modulo p is defined to be the
smallest positive integer k such that ak = I (mod pl.
Show that the order of a must divide p -I, if p is a
prime.
7.2. 14 Let p be a prime. Show that if J< = I (mod p)
for all nonzero x, then p - I divides k.
7.2.15 Let {an}n::o:O be a sequence of integers satisfy
ing an+ I = 2an + I. Is there an ao so that the sequence
consists entirely of prime numbers?
7.2.16 Prove Fermat's little theorem by induction on
a (you'll need the binomial theorem).
7.2.17 Our discussion of Fermat's little theorem in
volved the quantity (p - I)!, Please reread the proof of
Wilson's theorem (Example 3.1.9 on page 68), which
states that if p is prime, then (p - I)! = - I (mod p).
7.2.18 The Chinese Remainder Theorem. Consider
the following simultaneous congruence.
x=3 (mod II),
x = 5 (mod 6).
It is easy to find a solution, x = 47, by inspection.
Here's another method. Since 61-II, we can find a
linear combination of 6 and II that equals one, for ex
ample, ( -I). II + 2·6 = I. Now compute
5·(-1)·11 +3·2·6= -19.
This number is a solution, modulo 66 = 6· II. Indeed,
47 =-19 (mod 66).
(a) Why does this work?
(b) Note that the two moduli (which were II and 6
in the example) must be relatively prime. Showby example that there may not always be a so
lution to a simultaneous congruence if the two
moduli share a factor.(c) Let m 1-n, let a and b be arbitrary, and let
x simultaneously satisfy the congruences x = a
(mod m) and x = b (mod n). The algorithm
described above will produce a solution for x.
Show that this solution is unique modulo mn.
(d) Show that this algorithm can be extended to any
finite number of simultaneous congruences, as
long as the moduli are pairwise relatively prime.
(e) Show that there exist three consecutive num
bers, each of which is divisible by the 1999th
power of an integer.
(f) Show that there exist 1999 consecutive num
bers, each of which is divisible by the cube of
an integer.
7.2.19 (USAMO 1995) Let p be an odd prime. The
sequence (an)n::o:O is defined as follows: ao = 0, a, =
1, ... ,ap_ 2 =p-2 and, for all n"2p-l, an is the
least integer greater than an-, that does not form an
arithmetic sequence of length p with any of the pre
ceding terms. Prove that, for all n, an is the number
obtained by writing n in base p -I and reading the
result in base p.
7.2.20 (Putnam 1995) The number dld 2 ... d 9 has
nine (not necessarily distinct) decimal digits. The
number e I e 2 ... e 9 is such that each of the nine 9-digit
numbers formed by replacing just one of the digits di
is d,d 2 " .d 9 by the corresponding digit ei (1 :S i:S 9)
is divisible by 7. The number !lh ... 19 is related
to el e 2 ... e 9 in the same way: that is, each of the
nine numbers formed by replacing one of the ei by
the corresponding Ii is divisible by 7. Show that,
for each i, di -Ii is divisible by 7. (For example, if
d,d 2 " .d 9 = 199501996, then e6 may be 2 or 9, since
199502996 and 199509996 are multiples of 7.)
7.2.21 (Putnam 1994) Suppose a, b, c, d are integers
with 0 :S a :S b :S 99, 0 :S c :S d :S 99. For any integer
i, let ni = IOli + 100 i. Show that if na +nh is congru
ent to nc + nd mod 10 100, then a = c and b = d.