Skip to main content
### Number and algebra

### Geometry and measure

### Probability and statistics

### Working mathematically

### For younger learners

### Advanced mathematics

# Euler's Totient Function

## You may also like

### Curvy Equation

### Digital Equation

### Frosty the Snowman

Links to the University of Cambridge website
Links to the NRICH website Home page

Nurturing young mathematicians: teacher webinars

30 April (Primary), 1 May (Secondary)

30 April (Primary), 1 May (Secondary)

Or search by topic

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

This problem asks you to use your curve sketching knowledge to find all the solutions to an 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 is melting. Can you use your knowledge of differential equations to find out how his volume changes as he shrinks?