You may also like

Curvy Equation

This problem asks you to use your curve sketching knowledge to find all the solutions to an equation.

Digital Equation

Can you find a three digit number which is equal to the sum of the hundreds digit, the square of the tens digit and the cube of the units digit?

Frosty the Snowman

Frosty the Snowman is melting. Can you use your knowledge of differential equations to find out how his volume changes as he shrinks?

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.