Euler's totient function
Problem
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.
Getting Started
Question 1
$15$ has factors $3$ and $5$ (and $1$ and $15$). Write out all the numbers between $1$ and $14$ inclusive and then cross out everything which is a multiple of $3$, or $5$. You should be left with $8$ numbers which are co-prime with $15$.
Question 2
For example, $\phi(7)=6$ as $1, 2, 3, 4, 5$ and $6$ share no common factors with $7$. If one of the first $6$ numbers did share a factor with $7$, then $7$ would not be prime.
Question 3
For example $\phi(3^2)= 6$ since $1, 2,$ _ $, 4, 5,$ _ $, 7, 8$ are coprime with $9$.
Try a few more examples for different prime numbers and different powers before trying to generalise.
Question 4
$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)$?
Question 5
It might be helpful to write $n$ as a product of prime factors, e.g. $n=p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$.
Student Solutions
Question 1: Show that $\phi(15) = 8$.
Rayn, Torsten, Archie, Rupert, Jack, Takumi and Joe from Abingdon, Nayanika from The Tiffin Girls' School, Wiktor from LAE Tottenham, Mohsin from Oasis Academy Hadley and Olivia from Roedean, all in the UK, Ella from Jersey College for Girls in Jersey and Mahdi from Mahatma Gandhi International School in India all found $\phi(15).$ This is Ella's work:
Nayanika showed how to find $\phi(15)$ in a video which also introduces a different famous $\phi$ in mathematics: the golden ratio. Although they are written using the same letter, the golden ratio and Euler's Totient function are not directly related. Click here to see Nayanika's video.
Question 2: Investigate $\phi(p)$ where $p$ is a prime number. Can you find a general expression for $\phi(p)$?
Rayn, Torsten, Archie, Rupert, Jack, Takumi and Joe, Nayanika, Ella, Wiktor, Mohsin, Mahdi and Olivia found an expression for $\phi (p)$. Rayn, Torsten, Archie, Rupert, Jack, Takumi and Joe sent these examples:
This is Mohsin's work:
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)$?
Rayn, Torsten, Archie, Rupert, Jack, Takumi and Joe, Wiktor, Mahdi, Olivia and Mohsin tried some examples and found a general expression for $\phi (p^n).$ This is Mahdi's work for $\phi(2^n)$
This is Olivia's work for $\phi (3^n)$ and $\phi (p^n)$:
Question 4: Under which conditions is $\phi(nm) = \phi(n) \times \phi(m)$ true?
Nayanika and Ella said that $\phi(nm) = \phi(n) \times \phi(m)$ when $m$ and $n$ are prime. This is Ella's work:
Rayn, Torsten, Archie, Rupert, Jack, Takumi and Joe, Ella, Wiktor, Mohsin, Mahdi and Olivia found that it sometimes works when $m$ and $n$ are not prime. This is Olivia's work, with some notes added to the diagram to support some of the algebra:
Question 5: Can you find a general expression for $\phi(n)$?
Rayn, Torsten, Archie, Rupert, Jack, Takumi and Joe and Ella thought about using prime factorisations. Wiktor, Mohsin, Mahdi and Olivia found an expression for $\phi(n)$ using the prime factorisation of $n.$ This is Wiktor's work:
which is equal to
Rayn, Torsten, Archie, Rupert, Jack, Takumi and Joe wrote a python program which computes Euler's Totient Function:
def totient (x):
ans=1
list=[]
list2=[]
counter=0
while x != 1:
for i in range (2,x+1):
if x%i==0:
x=x//i
if i not in list:
list.append(i)
else:
if counter!=i:
list2.append(i)
counter=i
list2.append(i)
break
for i in list2:
while list.count(i)!=0:
list.remove(i)
for item in list:
ans=ans*(item-1)
while len(list2)!=0:
first=list2[0]
power=list2.count(first)
ans=ans*(first**power-first**(power-1))
while list2.count(first)!=0:
list2.remove(first)
return ans
a=int(input("input a number:"))
print(f'phi of {a} is {totient(a)}')
In short, list2 contains the prime factorisation of x, and then the function applies the same formula Wiktor found (but using Wiktor's unsimplified formula).
Extension: Fermat Euler Theorem: Under which conditions is it true that $x^{\phi(n)} \equiv 1 \text{ mod }n \; ?$
Mahdi tried out some examples and came up with a conjecture:
Olivia and Wiktor proved it using similar arguments to each other. This is Olivia's proof, which uses ideas from More Adventures with Modular Arithmetic:
Olivia means that when we multiply each of the numbers $a_1, a_2, a_3, ... , a_{\phi(n)}$ by $x,$ each of the products $a_1x, a_2x, a_3x, ... , a_{\phi(n)}x$ will be a different integer less than $n$ which is coprime to $n.$
Therefore $a_1x, a_2x, a_3x, ... , a_{\phi(n)}x$ and $a_1, a_2, a_3, ... , a_{\phi(n)}$ are the same numbers in some order.
Nayanika submitted two more videos which continues from the video at the top of the solution. In this video, Nayanika talks about the golden ratio and the Fibonacci numbers. Click here to see Nayanika's second video. Can you see how the rectangles in the image at the end are connected to the golden ratio?
Click here to see Nayanika's third video.
Teachers' Resources
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.