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

🔗

p

is prime, then by definition all integers from

1

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) .

🔗

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}

🔗

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}

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,

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{!}\)

MAT202: Introduction to Discrete Mathematics

Section 4.4 Euler's Theorem

Objectives

Definition 4.4.1. Euler's Totient Function.

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

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

Proposition 4.4.5. $ϕ (p)$ .

Checkpoint 4.4.6. Converse of Proposition 4.4.5.

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

Checkpoint 4.4.8. $ϕ (p q)$ .

Theorem 4.4.9. Euler's Theorem.

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

Proof.

Example 4.4.11. Example of Theorem 4.4.9.

Example 4.4.12. Compute the Remainder.

Checkpoint 4.4.13. Compute the Remainder.

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

Checkpoint 4.4.15. Repeat the Argument.

Exploration 4.4.1. Primality Testing.

(a)

(b)

(c)

\(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

Section 4.4 Euler's Theorem

Objectives

Definition 4.4.1. Euler's Totient Function.

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

Checkpoint 4.4.3. ϕ(n) for small n.

Proposition 4.4.5. ϕ(p).

Checkpoint 4.4.6. Converse of Proposition 4.4.5.

Checkpoint 4.4.7. ϕ(pk).

Checkpoint 4.4.8. ϕ(pq).

Theorem 4.4.9. Euler's Theorem.

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

Proof.

Example 4.4.11. Example of Theorem 4.4.9.

Example 4.4.12. Compute the Remainder.

Checkpoint 4.4.13. Compute the Remainder.

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

Checkpoint 4.4.15. Repeat the Argument.

Exploration 4.4.1. Primality Testing.

(a)

(b)

(c)

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

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

Proposition 4.4.5. $ϕ (p)$ .

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

Checkpoint 4.4.8. $ϕ (p q)$ .

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