# Euler’s Totient Function and Euler’s Theorem

by Dave
(DAVE)—

Many people have celebrated Euler’s Theorem, but its proof is much less traveled. In this article, I discuss many properties of Euler’s Totient function and reduced residue systems. As a result, the proof of Euler’s Theorem is more accessible. I also work through several examples of using Euler’s Theorem.

CONTENTS

We prove several properties of Euler’s Totient Function and give many examples. We also discuss solving functional equations and reduced residue systems. One of Euler’s most important theorems is then demonstrated and proven.

## Introduction to Euler’s Totient Function

Definition. For each integer $n>1,$ let $\phi (n)$ denote the number of positive integers less than $n$ and relatively prime to $n$ and let $\phi (1)=1.$ The function $\phi$ is called the totient function, or sometimes just, Euler’s $\phi$-function.

Euler’s totient function as many amazing properties. For example, notice that $$\phi (13)=13-1=12,$$ $$\phi \left(5^3\right)=5^2-5^1=20,$$ and $$\phi (35)=\phi (5) \phi (7)=(5-1)(7-1) = 24.$$

## Properties of the Euler’s Function

Lemma. If $p$ is a prime number, then $\phi (p)=p-1.$

Proof. Since $1, 2, 3, \ldots, p-1$ are relatively prime to the prime $p$, $\phi (p)=p-1.$

Lemma. If $p$ is a prime number, then $\phi \left(p^r\right)=p^r-p^{r-1}.$

Proof. By Euclid’s Lemma, the integers $k$ such that $1\leq k\leq p^r$ and $k$ is divisible by $p$ are $p, 2p, 3p, \ldots ,\left(p^{r-1}\right)p.$ Thus the number of positive integers less than $p^r$ and relatively prime to $p^r$ is $$p^r-1-\left(p^{r-1}-1\right)=p^r-p^{r-1}$$ as desired.

Lemma. If $p$ and $q$ are distinct primes, then $\phi (p q)=(p-1)(q-1).$

Proof. By Euclid’s Lemma, an integer $k$ will satisfy $(k,p q)>1$ if and only if $p|k$ or $q|k$ and the number of such $k$ is $(p-1)+(q-1).$ Thus the number of $k$ such that $(k,p q)=1$ and $1\leq k < p q$ is $$p q-1-((p-1)+(q-1))=(p-1)(q-1)$$ as desired.

## Multiplicative Function

Lemma. If $(m,n)=1,$ then $\phi (m n)=\phi (m)\phi (n)$.

Proof. There are $\phi (n)$ congruence classes which are represented by an integer relatively prime to $n$ in $\mathbb{Z}_n.$ Let these representatives be $a_1,\ldots , a_{\phi (n)}.$ The products $a a_1, \ldots, a a_{\phi (n)}$ are all distinct because $(a,n)=1$ and since each product is still relatively prime to $n,$ there is a representative from each of the $\phi (n)$ congruence classes $a_1, \ldots, a_{\phi (n)}.$ Therefore, $$a_1a_2\cdots a_{\phi (n)} \equiv \left(a a_1\right)\left(a a_2\right) \cdots \left(a a_{\phi (n)}\right) \equiv a^{\phi (n)}\left(a_1\cdots a_{\phi (n)} \right)\pmod{n}.$$ Since $\left(a_1\cdots a_{\phi (n)},n\right)=1,$ we have $a^{\phi (n)}\equiv 1 \pmod{n}$ as desired.

## Euler’s Formula for the Totient Function

Theorem. If $n=p_1^{e_1}p_2{}^{e_2}\cdots p_k{}^{e_k}$ is the unique prime factorization of $n,$ then $$\phi (n)=\left(p_1{}^{e_1}-p_1{}^{e_1-1}\right)\left(p_2{}^{e_2}-p_2^{e_2-1}\right)\cdots \left(p_k{}^{e_k}-p_k{}^{e_k-1}\right).$$

Example. Show that if $n$ is an odd integer, then $\phi (4n)=2\phi (n).$

Solution. Since $n$ is an odd integer $(4,n)=1$ and so $\phi (4n)=\phi (4)\phi (n)=2\phi (n).$

Example. Show that if $m$ and $n$ are positive integers then, $m|n \Longrightarrow \phi (m)|\phi (n).$

Solution. Let $n=p_1^{e_1}\cdots p_s{}^{e_s}$ be the unique prime factorization of $n.$ Since $m|n$ we have $m=p_1{}^{f_1}\cdots p_s{}^{f_s}$ where $0\leq f_i\leq e_i$ for $i=1,2, \ldots, s.$ Using $\phi \left(p^{\alpha }\right)=p^{\alpha }-p^{\alpha -1}$ we have \begin{align*} \phi (n) & =\phi \left(p_1^{e_1}\cdots p_s^{e_s}\right) \\ & =\phi \left(p_1^{e_1}\right)\cdots \phi \left(p_s^{e_s}\right) \\ & =\left(p_1^{e_1}-p_1^{e_1-1}\right)\cdots \left(p_s^{e_s}-p_s^{e_s-1}\right) \\ & =p_1^{e_1-1}\left(p_1-1\right)\cdots p_s{}^{e_s-1}\left(p_s-1\right) \\ & =p_1^{e_1-f_1}p_1^{f_1-1}\left(p_1-1\right)\cdots p_s^{e_s-f_s}p_s{}^{f_s-1}\left(p_s-1\right) \\ & =p_1^{e_1-f_1}\cdots p_s{}^{e_s-f_s}p_1^{f_1-1}\left(p_1-1\right)\cdots p_s{}^{f_s-1}\left(p_s-1\right) \\ & =p_1^{e_1-f_1}\cdots p_s{}^{e_s-f_s}\phi \left(p_1{}^{f_1}\right)\cdots \phi \left(p_s{}^{f_s}\right) \\ & =p_1{}^{e_1-f_1}\cdots p_s{}^{e_s-f_s}\phi (m) \end{align*} Therefore, $\phi (m)|\phi (n)$ as desired.

## Solving an Euler Functional Equation

### Euler’s Totient Function

Example. Solve the functional equation $\phi (n)=10$.

Solution. The claim is that $n=2^a3^b11^c$ for some integers $a,b,$ and $c.$ To see this let $\alpha$ be the highest power of $p$ dividing $n,$ then there is an integer $k$ with $(p,k)=1$ and $$\phi (n)=\phi \left(p^{\alpha }k\right)=\phi \left(p^{\alpha }\right)\phi (k)=\left(p^{\alpha }-p^{\alpha -1}\right)\phi (k)=p^{\alpha -1}(p-1)\phi (k)=10.$$ Since $(p-1)|10$ we must have $p-1=1,2,5,$ or $10$ and so $p=2,3,$ or $11.$ Now we should try to bound the exponents $a, b$, and $c$. Since, \begin{equation*} \phi (n)=\phi \left(2^a3^b11^c\right)=\left(2^a-2^{a-1}\right)\left( 3^b-3^{b-1} \right)\left(11^c-11^{c-1}\right)=10 \end{equation*} the exponents $a, b,$ and $c$ must be less than or equal to $2, 1,$ and $1$ respectively. We tabulate to find the solutions.

First we find $$\begin{array}{|c|c|c|c|c|} \hline a & b & c & n & \phi (n) \\ \hline 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 11 & 10 \\ 0 & 1 & 0 & 3 & 2 \\ 0 & 1 & 1 & 33 & 20 \\ 0 & 2 & 0 & 9 & 6 \\ 0 & 2 & 1 & 99 & 60 \\ \hline \end{array}$$ and $$\begin{array}{|c|c|c|c|c|} \hline a & b & c & n & \phi (n) \\ \hline 1 & 0 & 0 & 2 & 1 \\ 1 & 0 & 1 & 22 & 10 \\ 1 & 1 & 0 & 6 & 2 \\ 1 & 1 & 1 & 66 & 20 \\ 1 & 2 & 0 & 18 & 6 \\ 1 & 2 & 1 & 198 & 60 \\ \hline \end{array}$$

Finally, we have $$\begin{array}{|c|c|c|c|c|} \hline a & b & c & n & \phi (n) \\ \hline 2 & 0 & 0 & 4 & 2 \\ 2 & 0 & 1 & 44 & 20 \\ 2 & 1 & 0 & 12 & 4 \\ 2 & 1 & 1 & 132 & 40 \\ 2 & 2 & 0 & 36 & 12 \\ 2 & 2 & 1 & 396 & 120 \\ \hline \end{array}$$

## Solving Another Euler Functional Equation

Example. Solve the functional equation $\phi (n)=12$.

Solution. The claim is that $n=2^a3^b5^c7^d13^e$ for some integers $a,b,c,d,$ and $e.$ To see this let $\alpha$ be the highest power of $p$ dividing $n,$ then $$\phi (n)=12=p^{\alpha -1}(p-1)\phi (k)$$ for some integer $k.$ Since $(p-1)|12$ we must have $p-1=1,2,3,4,6,12$ and so $p=2,3,5,7,13.$ Now we should try to bound the exponents if we can. If $\alpha =2,$ then $p|12$ and so $p=2$ or $p=3.$ Therefore, $c, d$ and $e$ must be $0$ or 1. If $\alpha =3,$ the $\left.p^2\right|12$ and so $p=2.$ Hence, $b$ must be 0,1, or 2. Further, if $a=4,$ then $\left.p^3\right|12$ and so $p\neq 2.$ Therefore, $a$ must be $3$ or less. If $p=5,$ then $12=4\phi (k)$ and so $\phi (k)=3$ which is not possible. We are left with $n=2^a3^b7^d13^e$ and $0\leq a\leq 3,$ $0\leq b\leq 2$, $0\leq d\leq 1,$ and $0\leq e\leq 1.$

### These results are summarized

$$\begin{array}{|c|c|c|c|c|c|} \hline a & b & d & e & n & \phi (n) \\ \hline 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 13 & 12\\ 0 & 0 & 1 & 0 & 7 & 6 \\ 0 & 0 & 1 & 1 & 91 & 72\\ 0 & 1 & 0 & 0 & 3 & 2 \\ 0 & 1 & 0 & 1 & 39 & 24\\ 0 & 1 & 1 & 0 & 21 & 12 \\ 0 & 1 & 1 & 1 & 273 & 144 \\ 0 & 2 & 0 & 0 & 9 & 6 \\ 0 & 2 & 0 & 1 & 117 & 72\\ 0 & 2 & 1 & 0 & 63 & 36 \\ 0 & 2 & 1 & 1 & 819 & 432\\ 1 & 0 & 0 & 0 & 2 & 1 \\ 1 & 0 & 0 & 1 & 26 & 12\\ 1 & 0 & 1 & 0 & 14 & 6 \\ 1 & 0 & 1 & 1 & 182 & 72\\ \hline \end{array}$$

$$\begin{array}{|c|c|c|c|c|c|}\hline a & b & d & e & n & \phi (n) \\ \hline 1 & 1 & 0 & 0 & 6 & 2 \\ 1 & 1 & 0 & 1 & 78 & 24\\ 1 & 1 & 1 & 0 & 42 & 12 \\ 1 & 1 & 1 & 1 & 546 & 144\\ 1 & 2 & 0 & 0 & 18 & 6 \\ 1 & 2 & 0 & 1 & 234 & 72\\ 1 & 2 & 1 & 0 & 126 & 36 \\ 1 & 2 & 1 & 1 & 1638 & 432 \\ 2 & 0 & 0 & 0 & 4 & 2 \\ 2 & 0 & 0 & 1 & 52 & 24\\ 2 & 0 & 1 & 0 & 28 & 12 \\ 2 & 0 & 1 & 1 & 364 & 144\\ 2 & 1 & 0 & 0 & 12 & 4 \\ 2 & 1 & 0 & 1 & 156 & 48\\ 2 & 1 & 1 & 0 & 84 & 24 \\ 2 & 1 & 1 & 1 & 1092 & 288\\ \hline \end{array}$$

### The final computations

$$\begin{array}{|c|c|c|c|c|c|} \hline a & b & d & e & n & \phi (n) \\ \hline 2 & 2 & 0 & 0 & 36 & 12 \\ 2 & 2 & 0 & 1 & 468 & 144\\ 2 & 2 & 1 & 0 & 252 & 72 \\ 2 & 2 & 1 & 1 & 3276 & 864\\ 3 & 0 & 0 & 0 & 8 & 4 \\ 3 & 0 & 0 & 1 & 104 & 48\\ 3 & 0 & 1 & 0 & 56 & 24 \\ 3 & 0 & 1 & 1 & 728 & 288\\ 3 & 1 & 0 & 0 & 24 & 8 \\ 3 & 1 & 0 & 1 & 312 & 96\\ 3 & 1 & 1 & 0 & 168 & 48 \\ 3 & 1 & 1 & 1 & 2184 & 576\\ 3 & 2 & 0 & 0 & 72 & 24 \\ 3 & 2 & 0 & 1 & 936 & 288\\ 3 & 2 & 1 & 0 & 504 & 144 \\ 3 & 2 & 1 & 1 & 6552 & 1728 \\ \hline \end{array}$$

## Reduced Residue System

Before we get to Euler’s theorem there is another very important theorem involving Euler’s totient function.

Definition. A reduced residue system modulo $n$ is a set of $\phi (n)$ integers such that each element of the set is relatively prime to $n,$ and no two different elements of the set are congruent modulo $n.$

Notice the set $A=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}$ is a reduced residue system modulo 13 since $A$ contains $\phi(13)=12$ integers which are all relatively prime with $13$ and no two integers of $A$ are congruent modulo $13$. The set $B=\{1, 5, 7, 11\}$ is a reduced residue system modulo 12 since $B$ contains $\phi(12)=4$ integers which are all relatively prime with $12$ and no two integers of $B$ are congruent modulo $12$. It is not hard to check that the following sets $C$, $D$, and $E$ are each a reduced residue system modulo 28.

$C={1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27}$

$D={\pm 1,\pm 3,\pm 5,\pm 9,\pm 11, \pm 13}$

$E={\pm 5,\pm 15,\pm 25,\pm 45,\pm 55, \pm 65}$

Notice $E$ was obtain from $D$ by multiplying every integer of $D$ by $5$.

## Lemma on Reduced Residue Systems

Lemma. If $\{r_1, r_2, \ldots, r_{\phi(m)}\}$ is a reduced residue system modulo $m$ and $(a,m)=1,$ then $$\{ a r_1, a r_2, \ldots, a r_{\phi(m)} \}$$ is also a reduced residue system modulo $m.$

Proof. For $\{ a r_1, a r_2, \ldots, a r_{\phi(m)} \}$ to be a reduced residue system modulo $m$ we need to show that

\begin{equation*} \neg (a r_i \equiv a r_j) \qquad \text{ for all } 1\leq i < j\leq \phi (m). \end{equation*}

and

\begin{equation} \left(a r_i,m\right)=1 \qquad \text{ for all } 1\leq i\leq \phi (m) \end{equation}

To prove the first one, assume the contrary, $1\leq i < j\leq \phi (m)$ and $a r_i\equiv a r_j \pmod{m}.$ Then $r_i\equiv r_j \pmod{m}$ because $(a,m)=1$. But $r_i\equiv r_j \pmod{m}$ can not happen because $\{ r_1, r_2, \ldots, r_{\phi(m)} \}$ is a reduced residue system modulo $m$. Therefore, $a r_i \equiv a r_j \pmod{m}$ is not true and so the first is proven.

To show the second we suppose $1\leq i\leq \phi (m)$ and that $p$ is a prime divisor of $\left(a r_i,m\right)$. Since $p|m$ we can not have $p\left|r_i\right.$ because $\left(r_i,m\right)=1.$ It follows that, $\left(p,r_i\right)=1$ and $p\left|a r_i.\right.$ By Euclid’s lemma $p|a$. Clearly, $p|a$ and $p|m$ contradict $(a,m)=1.$ Thus there is no prime divisor of $\left(a r_{i},m\right)$ for any $1\leq i\leq \phi (m)$ and so the second is proven. Therefore, $\{ a r_1, a r_2, \ldots, a r_{\phi(m)} \}$ is also a reduced residue system modulo $m.$

## Euler’s Theorem

Theorem. (Euler) If $(a,m)=1,$ then $a^{\phi (m)}\equiv 1 \pmod{m}.$

Proof. Let $\{ r_1, r_2, \ldots, r_{\phi(m)} \}$ denote the reduced residue system modulo $m$ consisting of positive integers less than $m.$ By the Lemma above, we know that $$\{ a r_1, a r_2, \ldots, a r_{\phi(m)} \}$$ is also a reduced residue system modulo $m.$ Moreover, the integers $\{ r_1, r_2, \ldots, r_{\phi(m)} \}$ are congruent to the integers $\{ a r_1, a r_2, \ldots, a r_{\phi(m)} \}$ modulo $m$ in some order. It follows that $$a^{\phi (m)}r_1\cdot r_2 \cdots r_{\phi (m)} \equiv r_1 \cdot r_2 \cdots r_{\phi (m)} \pmod{m}$$ and since $\left(r_1\cdot r_2 \cdots r_{\phi (m)},m\right)=1$ we divide by $r_1\cdot r_2\cdots r_{\phi (m)}$ to obtain Euler’s equation.

## Examples Using Euler’s Theorem

Example. Prove that the solution to the linear congruence $a x\equiv b \pmod{m}$ is $x\equiv a^{\phi (m)-1}b \pmod{m}$ provided $(a,m)=1.$ Then use Euler’s $\phi$-function to solve the linear congruence $4 x\equiv 781 \pmod{1183}$.

Solution. If $(a,m)=1,$ then by Euler’s theorem $a^{\phi (m)}\equiv 1 \pmod{m}$ and so multiplying by $b$ we have $$a^{\phi (m)}b=a\left(a^{\phi (m)-1}b\right)\equiv b \pmod{m}$$ and so $x\equiv a^{\phi (m)-1}b \pmod{m}$ is a solution. Hence this solution is unique. To solve the given linear congruence equation notice $(4,1183)=1$, and so by Euler’s theorem, the solution is $x \equiv a^{\phi (m)-1} b \pmod{m}$ where $a=4,$ $m=1183,$ $b=781,$ and $\phi (1183)=936$. Therefore the unique solution is $x\equiv 4^{935}(781)\equiv 491 \pmod{1183}.$

Example. Find the last digit in the decimal expansion of $$n = 2\cdot(7^{1000}) + 7\cdot(3^{99,999}).$$

Solution. Since $\phi (10)=4$ and $7^{1000}=7^{4(250)},$ by Euler’s Theorem we have, $$7^{1000}=\left(7^4\right)^{250} \equiv 1^{250}\equiv 1 \pmod{10}.$$ So the last digit in the expansion of $7^{1000}$ is 1 and thus the last digit in the expansion of $2\left(7^{1000}\right)$ is of course 2. Further, since $\phi (10)=4$ and $3^{99,999}=3^{4(24999)+3}$ by Euler’s Theorem we have, $$3^{99,999} = \left(3^4 \right)^{24999}3^3 \equiv 27\equiv 7 \pmod{10}.$$ So the last digit in the expansion of $3^{99,999}$ is 7 and thus the last digit in the expansion of $7\left(7^{1000}\right)$ is of course 9. Since the sum of integers with last digit of 2 and last digit of 9 is 1, the last digit of $2\left(7^{1000}\right)+3^{99,999}$ is 1.

## Exercises on Euler’s Totient Function

Exercise. Determine $\phi (n)$ for $n=1,2,3,4,5$ and $6.$

Exercise. Show that $\phi (5186)=\phi (5187)=\phi (5188).$

Exercise. Find the least positive residue of $3^{999,999,999}$ modulo 7 and of $2^{1,000,000}$ modulo 17.

Exercise. Use Euler’s theorem to find the least positive residue of $3^{100,000}$ modulo 35.

Exercise. Suppose $p\equiv 3 \pmod{4}$. Show that $(p+1)/4$ is an integer and is the multiplicative inverse of 4 modulo $p$.

Exercise. Which is true:

(1) if $m|n$, then $\phi(m)|\phi(n)$ or

(2) if $\phi(m)|\phi(n)$, then $m|n$.

Both, neither, or one of them.

Exercise. Show that if $m$ and $k$ are positive integers, then $$\phi \left(m^k\right)=m^{k-1}\phi (m).$$

## More Exercises on Euler’s Totient Function

Exercise. Show that if $a$ and $m$ are positive integers with $(a,m)=(a-1,m)=1,$ then $$1+a+a^2+\cdots +a^{\phi (m)-1}\equiv 0 \pmod{ m}.$$

Exercise. Show that if $c_1,c_2, \ldots ,c_{\phi (m)}$ is a reduced residue system modulo $m,$ where $m$ is a positive integer greater than 2, then $c_1+c_2+c_3+\cdots + c_{\phi (m)}\equiv 0 \pmod{m}.$

Exercise. Find the value of the Euler phi-function for the given integer.

$(1) \quad 100$

$(2) \quad 256$

$(3) \quad 1001$

$(4) \quad 2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13$

$(5) \quad 10!$

$(6) \quad 20!$

Exercise. Find all positive integers $n$ such that $\phi (n)=6.$

Exercise. Find all positive integers $n$ such that $\phi (n)=14.$

Exercise. Find a reduced residue system modulo for each of the following integers.

$(1) \quad 9$

$(2) \quad 10$

$(3) \quad 14$

$(4) \quad 16$

$(5) \quad 17$

## More Exercises on Euler’s Totient Function

Exercise. Solve the congruence $5x\equiv 3 (\text{mod} 14)$ by using Euler’s theorem.

Exercise. Show that $\phi (5186)=\phi (5187)=\phi (5188).$

Exercise. Show that if $n$ is an odd integer, then $\phi (4n)=2\phi (n).$

Exercise. Solve the functional equation $\phi (n)=6$.

Exercise. Find the second to last digit in the decimal expansion of $43^{52}.$

Exercise. Show that if $n$ is an odd integer, then $\phi (4n)=2\phi (n).$

Exercise. Solve the functional equation $\phi (n)=6$.

Exercise. Show that if $m$ and $k$ are positive integers, then $\phi(m^k)=m^{k-1}\phi(m)$.

Exercise. Determine which of the following quadratic congruences has solutions

$(1) \quad 16x^2+5x+1\equiv 0 \pmod{31}$

$(2) \quad 16x^2-5x+1\equiv 0 \pmod{101}.$

Exercise. Let $p$ be an odd prime. Show that the quadratic congruence equation $a x^2+bx +c\equiv 0 \pmod{p}$ has a solution if and only if $$\left(\frac{b^2-4ac}{p}\right)=1.$$

Exercise. Find the second to last digit in the decimal expansion of $43^{52}.$

Exercise. Use Euler’s theorem to find any $x$ that satisfies the linear congruence equation $3x\equiv 13 \pmod{17}.$

Exercise. Determine $\phi (10440125)$.