You may also like

Clock Squares

Can you find a way of predicting the value of large square numbers with the help of our power modulo calculator?

Secondary Toughnuts

These secondary problems have not yet been solved. Can you be the first?

Clock Arithmetic

What happens if we change the rules and make the usual straight number line into a circle?

Euler's Totient Function

Age 16 to 18
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.