Challenge Level

*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.*