7.3 NUMBER THEORETIC FUNCTIONS 237since any number that shares a factor with 12 will be a mUltiple of either 2 or 3 (or
both). Now PIE implies that1M 2 UM 31 = IM 21 + IM 3 1-IM 2 nM 31 ·
Because 21-3, we can rewrite M 2 nM 3 as M 6. Thus we have
cp(12) = 12 -1M 2 UM 31 = 12 - (IM 21 + 1M 3 !) + IM 61 = 12 -( 6 +^4 ) +^2 =^4.
7.3. 10 Let p and q be distinct primes. Show that
(a) cp(p) = p-l,
(b) cp(pr) = pr _ pr-l = pr-l(p _l) = pr ( (^1) - �).
(c) cp (pq) = (p - 1)( q - 1) = pq ( (^1) - �) ( (^1) - � ).
(d) cp(prl)=pr-l(p _l)qS-l(ql)=prqs(I�) ( 1 - �).
These special cases above certainly suggest that cp is multiplicative. This is easy to
verify with PIE. For example, suppose that n contains only the distinct primes p,q, w.
If we let Mk denote the number of positive multiples of k less than or equal to n, we
have
cp(n) = n - (IMpl + IMql + IMwl) + (IMpql + IMpwl + IMqwl) -IMpqwl·
In general,but since p, q, w all divide n, we can drop the brackets;
cp(n) =n-(� + �+�) + (�+�+�) -�,
pqw pq pw qw pqw
and this factors beautifully asIf we write n = pr qSw, we have
cp(n) = pr (1 -�) qS (1 -�) w (1 _ ± ) = cp(pr)cp(qs)cp(w^1 ),
(2)using the formulas in 7.3.10. This argument certainly generalizes to any number of
distinct primes, so we have established that cp is multiplicative. And in the process, we
developed an intuitively reasonable formula. For example, consider 360 = 23. 32 .5.
Our formula says thatcp( 360 ) = 360 (1 -�) (1 -�) (1-�) ,