 Solution

ID: past-exam-of-the-options-ii-course-of-the-university-of-oxford/2005/c/2/a/i/solution

ϕ (n)

counts the integers

1 \leq a \leq n

n

, equivalently the invertible residue classes modulo

n

. Among

1, \dots, p^{e}

, exactly the

p^{e - 1}

multiples of

p

are not coprime to the prime power. Hence

ϕ (p^{e}) = p^{e} - p^{e - 1} = p^{e} (1 - 1/ p) .

Factor

n = \prod_{p} p^{e_{p}}

. Its distinct prime-power factors are pairwise coprime, so the permitted multiplicativity gives

ϕ (n) = \prod_{p ∣ n} p^{e_{p}} (1 - 1/ p) = n p ∣ n \prod (1 - 1/ p) .

For

n = 1

, the empty product is one and agrees with

ϕ (1) = 1

 New to topics? Read the docs here!