# Euler's Totient Function

##### Age 16 to 18Challenge Level

Question 1

$15$ has factors $3$ and $5$ (and $1$ and $15$).  Write out all the numbers between $1$ and $14$ inclusive and then cross out everything which is a multiple of $3$, or $5$.  You should be left with $8$ numbers which are co-prime with $15$.

Question 2

For example, $\phi(7)=6$ as $1, 2, 3, 4, 5$ and $6$ share no common factors with $7$.  If one of the first $6$ numbers did share a factor with $7$, then $7$ would not be prime.

Question 3

For example $\phi(3^2)= 6$ since $1, 2,$ _ $, 4, 5,$ _ $, 7, 8$ are coprime with $9$.
Try a few more examples for different prime numbers and different powers before trying to generalise.

Question 4

$24$ can be written as $3 \times 8$.  Is it true that $\phi(24) = \phi(3) \times \phi(8)$?
Alternatively $24$ can be written as $4 \times 6$.  Is it true that $\phi(24) = \phi(4) \times \phi(6)$?

Question 5

It might be helpful to write $n$ as a product of prime factors, e.g. $n=p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$.