by the chinese remainder theorem, if p,q are distinct primes,
thus it suffices to find , where r is the highest power of p that divides n, for each prime p in the factorization of n.
by counting (never underestimate the power of counting),
so for n = 10, for example, 10 = (2)(5).
φ(2) = 1, φ(5) = 4, so φ(10) = φ(2)φ(5) = (1)(4) = 4.