Computing phi(36)

Question

Verify that $\varphi(36) = 12$ by counting the coprime integers.

Solution

Direct count. The integers in $\{1,\ldots,36\}$ coprime with $36 = 2^2\cdot 3^2$ are those divisible neither by $2$ nor by $3$: $1,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 25,\ 29,\ 31,\ 35.$ There are $\boxed{12}$. Verification with the formula for $n=p^a q^b$: $\varphi(36) = 36\left(1-\tfrac12\right)\left(1-\tfrac13\right) = 36\cdot\tfrac12\cdot\tfrac23 = 12. \checkmark$

Links

Topics: Probability distributions
Concepts: Euler’s function
Skills: Computing
People: Leonhard Euler (Eulero)
Exercise type: Expression evaluation