Euler's Theorem

Section 4.4 Euler's Theorem

Objectives

Define Euler's totient function $ϕ (n),$ compute its values for small $n,$ and prove general statements about $ϕ (n) .$
State and apply Euler's Theorem and Fermat's Little Theorem to solve congruences and prove other results.
Apply Fermat's Little Theorem to primality testing.

First, let's restate the definition of Euler's totient function (introduced in Exploration 3.2.1).

Definition 4.4.1. Euler's Totient Function.

Euler's totient function (or Euler's phi-function) is the function $ϕ : N \to N$ defined by

ϕ (n) = | {k \in N : 1 \leq k \leq n, gcd (k, n) = 1} | .

Video: Euler's Phi Function

Example 4.4.2. $ϕ (1)$ and $ϕ (8)$ .

We have $\phi(1) = 1$ since $1$ is the only integer in $\{1\}$ relatively prime with 1.

Also $\phi(8) = 4\text{,}$ since there are four numbers in the set $\{1,2,\ldots,8\}$ relatively prime with 8: they are 1, 3, 5, and 7.

Checkpoint 4.4.3. $ϕ (n)$ for small $n$ .

The table below lists values of $\phi(m)$ for small values of $m\text{.}$ Complete the table for $m = 11, 12, \ldots, 20\text{.}$

Table 4.4.4. Values of $\phi(n)$

$n$	integers $1 \leq k \leq n$	$\phi(n)$
	such that $\gcd(k,n)=1$
1	1	1
2	1	1
3	1, 2	2
4	1, 3	2
5	1, 2, 3, 4	4
6	1, 5	2
7	1, 2, 3, 4, 5, 6	6
8	1, 3, 5, 7	4
9	1, 2, 4, 5, 7, 8	6
10	1, 3, 7, 9	4
11
12
13
14
15
16
17
18
19
20

If $p$ is prime, then by definition all integers from $1$ to $p - 1$ are relatively prime with $p .$ This implies the following result:

Proposition 4.4.5. $ϕ (p)$ .

If $p$ is prime, then $ϕ (p) = p - 1 .$

Checkpoint 4.4.6. Converse of Proposition 4.4.5.

Is the converse of the above statement true? That is, if $n \gt 2$ is an integer such that $\phi(n) = n-1\text{,}$ does it necessarily follow that $n$ is prime?

Justify your answer.

Checkpoint 4.4.7. $ϕ (p^{k})$ .

If $p$ is prime and $k \in \mathbb{N}\text{,}$ prove that $\phi(p^k) = p^k - p^{k-1}\text{.}$

Checkpoint 4.4.8. $ϕ (p q)$ .

If $p$ and $q$ are prime, prove that $\phi(pq) = (p-1)(q-1)\text{.}$

Hint

Theorem 3.2.6

Now we can state Euler's Theorem then prove Fermat's Little Theorem, which is a special case.

Video: Two Theorems in Number Theory

Theorem 4.4.9. Euler's Theorem.

If $a, n \in N$ with $gcd (a, n) = 1,$ then

a^{ϕ (n)} \equiv 1 (\mod n) .

Theorem 4.4.10. Fermat's Little Theorem (FLT).

If $a \in N$ and $p$ is prime such that $p ∤ a,$ then

a^{p - 1} \equiv 1 (\mod p) .

Proof.

If $p$ is prime with $p \nmid a\text{,}$ we have $\gcd(a,p) = 1\text{.}$ So we can use Theorem 4.4.9 on $a$ and $m = p\text{.}$ Since $\phi(p) = p-1$ by Proposition 4.4.5, the result follows.

Although Theorem 4.4.10 is a special case of Theorem 4.4.9, it was Theorem 4.4.10 that was actually proven first—in 1736, also by Euler [1]. Only in 1763 did Euler publish the generalization that is Euler's Theorem [2].

Example 4.4.11. Example of Theorem 4.4.9.

Take $n = 8$ and $a = 7$ so that $\gcd(a,n) = 1\text{.}$ By Theorem 4.4.9 we have

\begin{equation*} 7^{\phi(8)} \equiv 1 \Mod{8} \Rightarrow 7^4 \equiv 1 \Mod{8}\text{.} \end{equation*}

Example 4.4.12. Compute the Remainder.

Compute $3^{2020} \mmod 113\text{.}$

Solution

Since $\gcd(3,113) = 1\text{,}$ we can apply Theorem 4.4.9. In fact, 113 is prime, so Theorem 4.4.10 applies here, so we know that

\begin{equation*} 3^{112} \equiv 1 \Mod{13}\text{.} \end{equation*}

Using the Theorem 1.3.2 on 2020 we get $2019 = 18\cdot 112 + 4\text{.}$ Hence

\begin{equation*} 3^{2020} \equiv (3^{112})^{18} \cdot 3^4 \Mod{113} \equiv 81 \Mod{113}\text{.} \end{equation*}

So $3^{2020} \mmod 113 = 81\text{.}$

Checkpoint 4.4.13. Compute the Remainder.

Compute $6^{6777} \mmod 667\text{.}$

Hint

$667 = 23 \times 29.$

The idea behind the proof of Theorem 4.4.9 is that for $a, n \in N$ relatively prime, multiplying each element of the set

S = {y \in {1, 2, \dots, n} : gcd (y, n) = 1}

by $a$ induces a permutation of the set modulo $n .$ We give first an example with numbers.

Example 4.4.14. Why Theorem 4.4.9 holds, for $a = 4$ and $n = 9$ .

Let $a = 4$ and $n = 9\text{.}$ Then $\phi(9) = 6\text{,}$ since the integers $S = \{1,2,4,5,7,8\}$ are relatively prime with $9\text{.}$

Multiplying each number in $S$ by 4 and reducing modulo 9, we have

$S = $	$\{$1	2	4	5	7	8$\}$
	$\downarrow$	$\downarrow$	$\downarrow$	$\downarrow$	$\downarrow$	$\downarrow$	(multiply by $a = 4$)
	4	8	16	20	28	32
	$\downarrow$	$\downarrow$	$\downarrow$	$\downarrow$	$\downarrow$	$\downarrow$	(reduce modulo 9)
	$\{$4	8	7	2	1	5$\}$	$\rightarrow$ same as $S\text{!}$

What this means is that $S$ and $\{4y : y \in S\}$ contain the same numbers modulo 9; so when we take the product of all elements in these sets, the results must be congruent modulo 9 as well:

\begin{equation*} (4\cdot 1)(4\cdot 2)(4\cdot 4)(4 \cdot 5)(4\cdot 7)(4\cdot 8) \equiv (1)(2)(4)(5)(7)(8)\Mod{9}\text{.} \end{equation*}

Since each element of $S$ is relatively prime with 9, we can apply Proposition 4.2.15 to cancel each term, and we are left with

\begin{equation*} (4)(4)(4)(4)(4)(4) \equiv 1 \Mod{9} \Rightarrow 4^{\phi(9)} \equiv 1 \Mod{9} \end{equation*}

since $\phi(9) = 6 = |S|\text{.}$

Checkpoint 4.4.15. Repeat the Argument.

Replicate the idea in Example 4.4.14 to show that $7^{\phi(15)} \equiv 1 \Mod{15}\text{.}$

Finally, we present the proof of Theorem 4.4.9.

Proof of Euler's Theorem

Let $a, n \in N$ such that $gcd (a, n) = 1 .$

First define the set

S = {y : 1 \leq y \leq n, gcd (y, n) = 1}

to be the set of natural numbers smaller than $n$ and relatively prime with $n .$ We know that there are exactly $ϕ (n)$ elements in the set $S,$ so we can label them as $S = {b_{1}, b_{2}, \dots, b_{ϕ (n)}},$ where $gcd (b_{i}, n) = 1$ for $i = 1, 2, \dots, ϕ (n) .$

Since we have $gcd (b_{i}, n) = 1$ and $gcd (a, n) = 1,$ we must also have

gcd (a b_{i}, n) = 1 for any i = 1, 2, \dots, ϕ (n) .

We invoke Theorem 1.3.2 now to write $a b_{i}$ as

a b_{i} = q n + r for some 0 \leq r < n,

which implies that $a b_{i} \equiv r (\mod n) .$

Combining with the fact that $gcd (a b_{i}, n) = 1,$ this implies that $gcd (r, n) = 1,$ so $r$ is a natural number smaller than $n$ and relatively prime with $n .$

In other words, $r$ is in the set $S,$ and we can write $r = b_{j}$ for some $1 \leq j \leq ϕ (n) .$ This means for each $1 \leq i \leq ϕ (n),$ we have $a b_{i} \equiv b_{j} (\mod n)$ for some $1 \leq j \leq ϕ (n) .$

Furthermore, none of the $b_{j}$ 's are repeated, because no two $a b_{i}$ terms are equivalent modulo $n .$ (Otherwise, $a b_{i_{1}} \equiv a b_{i_{2}} (\mod n) \Rightarrow b_{i_{1}} \equiv b_{i_{2}} (\mod n)$ by Proposition 4.2.15, which is a contradiction as the $b_{i}$ 's are all distinct and smaller than $n .$ )

Hence, each integer $a b_{i}$ is congruent modulo $n$ to distinct elements in $S :$

\begin{aligned} a b_{1} & \equiv b_{j_{1}} (\mod n) \\ a b_{2} & \equiv b_{j_{2}} (\mod n) \\ ⋮ \\ a b_{ϕ (n)} & \equiv b_{j_{ϕ (n)}} (\mod n) \end{aligned}

Multiplying all the congruences together gives another congruence, where the right-hand-side is just

\prod_{k = 1}^{ϕ (n)} b_{j_{k}} = \prod_{i = 1}^{ϕ (n)} b_{i}

since each element of $S$ appears exactly once. Hence,

\prod_{i = 1}^{ϕ (n)} a b_{i} \equiv \prod_{i = 1}^{ϕ (n)} b_{i} (\mod n) \Rightarrow a^{ϕ (n)} \equiv 1 (\mod n)

by an application of Proposition 4.2.15.

Video: Primality Testing

Exploration 4.4.1. Primality Testing.

Theorem 4.4.10 asserts that if $p$ is prime and $gcd (a, p) = 1,$ then $a^{p - 1} \equiv 1 (\mod p) .$

(a)

Note that the converse of this statement is not true in general: Even if $gcd (a, n) = 1$ and $a^{n - 1} \equiv 1 (\mod n),$ we would not be able to conclude that $n$ is prime.

Can you give examples of pairs $a, n$ such that $gcd (a, n) = 1$ and $a^{n - 1} \equiv 1 (\mod n)$ are both true, but $n$ is not prime.

(b)

Complete the contrapositive of Theorem 4.4.10:

If $a, n \in N,$ $gcd (a, n) = 1,$ and $a^{n - 1} ≢ 1 (\mod n),$ then .

(c)

Show that 91 is not prime by using part (b) with $a = 2 .$

\(S = \)	\(\{\)1	2	4	5	7	8\(\}\)
	\(\downarrow\)	\(\downarrow\)	\(\downarrow\)	\(\downarrow\)	\(\downarrow\)	\(\downarrow\)	(multiply by \(a = 4\))
	4	8	16	20	28	32
	\(\downarrow\)	\(\downarrow\)	\(\downarrow\)	\(\downarrow\)	\(\downarrow\)	\(\downarrow\)	(reduce modulo 9)
	\(\{\)4	8	7	2	1	5\(\}\)	\(\rightarrow\) same as \(S\text{!}\)