Find the Euler totient function $\phi (n)$ of the following numbers:
(a) 15 (b) 64 (c) 200 (d) 1000 (e) 1001 (f) 666
We will use Proposition (5.4), that if $p$ is prime and $k$ is a natural number then $\phi (p^k) = p^k - p^{k−1} = p^{k−1} (p− 1)$.
We will also use the multiplicative property of the Euler totient function, Theorem (5.5), that $\phi (m \times n) = \phi (m) \times \phi (n)$ provided $\gcd(m, n) = 1$.
(a) The prime decomposition of 15 is $15=3 \times 5$. Since $\gcd(3,5)=1$, we can use the multiplicity of $\phi$,
$ \phi(15)= \phi(3) \times \phi(5) = (3-1)(5-1) = 8$
(b) Since $64=2^6$, we have
$ \phi(64) = \phi(2^6) = 2^5(2-1) = 32 $
(c) Since $\gcd(2^3, 5^2)=1$, we can use the multiplicity of $\phi$,
$ \phi(200) = \phi(2^3 \times 5^2) = \phi(2^3) \times \phi(5^2) = 2^2(2-1) \times 5^1(5-1) = 80$
(d) Since $\gcd(2^3, 5^3)=1$, we have
$ \phi(1000) = \phi(2^3 \times 5^3) = \phi(2^3) \times \phi(5^3) = 2^2(2-1) \times 5^2(5-1) = 400 $
(e) The prime decomposition of 1001 is $1001 = 7 \times 11 \times 13$, and so
$ \phi(10001) = \phi(7) \times \phi(11) \times \phi(13) = (7-1) \times (11-1) \times (13-1) = 720 $
(f) The prime factorisation of 666 is $666 = 2 \times 3^2 \times 37$, and so
$ \phi(666) = \phi(2) \times \phi(3^2) \times \phi(37) = (2-1) \times 3^1(3-1) \times (37-1) = 216$