Euler's Totient Function

Why do this problem?

This problem follows on from Clock Arithmetic and More Adventures with Modular Arithmetic. The ideas introduced in this problem are used in the article Public Key Cryptography and in the Public Key Cryptography Interactivity.

Euler's Totient Function and the Fermat Euler theorem are usually studied early on in a University Mathematics degree.

Possible approach

This is an ideal problem for students to work on in pairs and justify their findings to each other.  The class can come together to discuss question 5. 

For the extension, students can use the power mod calulator to gather results and make conjectures.  A possible starting point would be to use $n=15$ and $\phi(n)=8$ (as used in question 1) and then take $x=1, 2, 3, ..., 14$ and see which values of $x$ satisfy $x^{\phi(15)} \equiv 1 \text{ mod }15$.

Key questions

If $p$ is prime, then can any of the numbers $1, 2, 3, ..., p-1$ share a common factor greater than $1$ with $p$?

$24$ can be written as $3 \times 8$.  Is it true that $\phi(24)=\phi(3)\times \phi(8)$?
Alternatively $24$ can be written as $4 \times 6$.  Is it true that $\phi(24)=\phi(4)\times \phi(6)$?

Possible support

Encourage students to work systematically and organise their results to help them spot patterns.

Possible extension

After working on this problem, students might like to work through the article Public Key Cryptography and try out the Public Key Cryptography Interactivity.