270 16. Answers to Exercises
add the number of common multiples ofpiandpjfor any two primespi
andpj; then we have to subtract the number of common multiples ofpi,
pj, andpkfor any three primespi,pj, andpk, etc. Just as in the numerical
example, the number of multiples ofpiisn/pi; the number of common
multiples ofpiandpjisn/(pipj); the number of common multiples ofpi,
pj, andpkisn/(pipjpk), etc. So we get
φ(n)=n−n
p 1−···−
n
pr+
n
p 1 p 2+
n
p 1 p 3+···+
n
pr− 1 pr−
n
p 1 p 2 p 2−···.
This is equal to the expression in (6.7). Indeed, if we expand the product,
every term arises by picking either “1” or “−p^1 i” from each factor
(
1 −p^1 i)
,
which gives a term of the form
(−1)k1
pi 1 ···pik.
This is just a typical term in the inclusion-exclusion formula above.
6.9.3. It is not hard to come up with the conjecture that the answer is
n. To prove this, consider the fractionsn^1 ,^2 n,...,nn, and simplify them as
much as possible. We get fractions of the formad, wheredis a divisor of
n,1≤a≤d, and gcd(a, d) = 1. It is also clear that we get every such
fraction. The number of such fractions with a given denominator isφ(d).
Since the total number of fractions we started with isn, this proves our
conjecture.
6.9.4. Forn= 1 and 2 the answer is 1. Suppose thatn>2. Ifkis such
an integer, then so isn−k. So these integers come in pairs adding up ton
(we have to add thatn/2 is not among these numbers). There areφ(n)/ 2
such pairs, so the answer isnφ(n)/2.
6.9.5. The proof is similar to the solution of Exercise 6.5.4.
Lets 1 ,...,skbe the numbers between 1 andbrelatively prime tob;so
k=φ(b). Letribe the remainder ofsiawhen divided byp.Wehave
gcd(b, ri) = 1, since if there were a primepdividing bothbandri, thenp
would also dividesia, which is impossible, since bothsiandaare relatively
prime tob. Second,r 1 ,r 2 ,...,rkare different, sinceri=rj would mean
thatb|sia−sja=(si−sj)a; since gcd(a, b) = 1, this would imply that
b|si−sj, which is clearly impossible. Hence it follows thatr 1 ,r 2 ,...,rk
are just the numberss 1 ,s 2 ,...,sk, in a different order.
Consider the product (s 1 a)(s 2 a)···(ska). On the one hand, we can write
this as
(s 1 a)(s 2 a)···(ska)=(s 1 s 2 ···sk)ak,
on the other,
(s 1 a)(s 2 a)···(ska)≡r 1 r 2 ···rk=s 1 s 2 ···sk (modb).