266 16. Answers to Exercises
(indirect assumption)k
√
n=a/bthennbk=ak, and so the number of times
poccurs in the prime factorization of the left-hand side is not divisible by
k, while the number of times it occurs in the prime factorization of the
right-hand side is divisible byk. A contradiction.
6.4 On the Set of Primes
6.4.1. Just as in the treatment of the casek= 200 above, we subtract the
number of primes up to 10k−^1 from the number of primes up to 10k.By
the Prime Number Theorem, this number is about
10 k
kln 10−
10 k−^1
(k−1) ln 10=
(9k−10)10k−^1
k(k−1) ln 10.
Since
9 k− 10
k− 1
=9−
1
k− 1is very close to 9 ifkis large, we get that the number of primes withk
digits is approximately
9 · 10 k−^1
kln 10
.
Comparing this with the total number of positive integers withkdigits,
which we know is 10k− 10 k−^1 =9· 10 k−^1 , we get
9 · 10 k−^1
kln 10· 9 · 10 k−^1=
1
(ln 10)k≈
1
2. 3 k.
6.5 Fermat’s “Little” Theorem
6.5.1. 4
( 4
2)
=6.4 24 −2 = 14.
6.5.2. (a) We need that each of theprotated copies of a set are different.
Suppose that there is a rotated copy that occursatimes. Then trivially
every other rotated copy occursatimes. But thena|p, so we must have
a=1ora=p. If allprotated copies are the same, then trivially either
k=0ork=p, which were excluded. So we havea= 1 as claimed. (b)
Consider the set of two opposite vertices of a square. (c) If each box contains
psubsets of sizek, the total number of subsets must be divisible byp.
6.5.3.We consider each number to havepdigits by appending zeros at the
front if necessary. We getpnumbers from each numberaby a cyclic shift.
These are all the same when all digits ofaare the same, but all different
otherwise (why? the assumption thatpis a prime is needed here!). So we
getap−anumbers that are divided into classes of sizep.Thusp|ap−a.
6.5.4. Assume thatpa. Consider the producta(2a)(3a)···((p−1)a)=
(p−1)!ap−^1. Letribe the remainder ofiawhen divided byp. Then the