### Clock Squares

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

### Always Perfect

Show that if you add 1 to the product of four consecutive numbers the answer is ALWAYS a perfect square.

### Polite Numbers

A polite number can be written as the sum of two or more consecutive positive integers, for example 8+9+10=27 is a polite number. Can you find some more polite, and impolite, numbers?

# Euler's Totient Function

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