Euler's Totient Function

This problem follows on from Clock Arithmetic and More Adventures with Modular Arithmetic.

The function $\phi(n)$ for a positive integer $n$ is defined by $$\phi(n)=\text{The number of positive integers less than } n \text{  which are co-prime to }n.$$

Two numbers are co-prime if the highest factor which is common to both is 1.
$8$ and $15$ are co-prime but $24$ and $15$ are not as they share a factor of $3$.
The symbol "$\phi$" is a greek letter and is pronounced "Phi" (or "Fi").

For example, $\phi(12) = 4$ as the only positive integers less than $12$ which are co-prime to $12$ are $1, 5, 7, $ and $11$.  

Question 1

Show that $\phi(15) = 8$.

Question 2

Investigate $\phi(p)$ where $p$ is a prime number.  Can you find a general expression for $\phi(p)$?

Question 3 

Investigate $\phi(2^n)$ where $n=1, 2, 3, ...$.  Can you find a general expression for $\phi(2^n)$?  What about $\phi(3^n)$?

Can you find a general expression for $\phi(p^n)$ where $p$ is prime?

Question 4

In Question 1 you showed that $\phi(15)=8$.  What are $\phi(3)$ and $\phi(5)$?

Is it true that $\phi(15)=\phi(3) \times \phi(5)$?

Under which conditions is $\phi(nm) = \phi(n) \times \phi(m)$ true?

Question 5

Can you find a general expression for $\phi(n)$?

Extension: Fermat Euler Theorem

Evaluate $x^{\phi(n)} \text{ mod }n$ for different values of $n$ and $x$. 
Under which conditions is it true that $$x^{\phi(n)} \equiv 1 \text{ mod }n \; ?$$

You may find this power modulo calculator useful!

If you have enjoyed working on this problem, then you may enjoy Public Key Cryptography.

We are very grateful to the Heilbronn Institute for Mathematical Research for their generous support for the development of this resource.