Euler' Theorem And Euler's Totient Function

# Euler's Theorem and Euler's Totient Function

Recall that Fermat's theorem states that for a prime integer p, $a^{p-1} \equiv 1 \pmod p$ if $(a, p) = 1$. We are now going to find an equivalence for any positive integer as opposed to just primes. For any positive integer m, we want to know if $a^{f(m)} \equiv 1 \pmod m$ given $(a, m) = 1$.

Suppose that m = 9. We will construct a table of least residues mod 9 for all integers between 1 and 9 that are relatively prime to 9, specifically the integers 1, 2, 4, 5, 7, and 8. Notice that we have 6 integers between 1 and 9 that are relatively prime to 9. We will let a = 1, a = 2, … and calculate a (mod 9), a2 (mod 9), and so forth until we notice something interesting. We thus get the following table:

a (mod 9) a2 (mod 9) a3 (mod 9) a4 (mod 9) a5 (mod 9) a6 (mod 9)
1 1 1 1 1 1
2 4 8 7 5 1
4 7 1 4 7 1
5 7 8 4 2 1
7 4 1 7 4 1
8 1 8 1 8 1

Notice that how $1^6 \equiv 2^6 \equiv 4^6 \equiv 5^6 \equiv 7^6 \equiv 8^6 \pmod 9$. It appears that if (a, 9) = 1, then $a^6 \equiv 1 \pmod 9$.

## Example 1

Construct a table similar to the one above for when m = 12. What do you notice about this table?

To construct this table, we will look at the integers between 1 and 12 that are relatively prime to 12. There are four of these integers, specifically 1, 5, 7, and 11. We will let a = 1, a = 5, a = 7, and a = 11, and calculate a (mod 12), a2 (mod 12), and so forth as follows:

a (mod 12) a2 (mod 12) a3 (mod 12) a4 (mod 12)
1 1 1 1
5 1 5 1
7 1 7 1
11 1 11 1

It appears that $1^4 \equiv 5^4 \equiv 7^4 \equiv 11^4 \pmod {12}$, and that if (a, 12) = 1, then $(a^4 \equiv 1 \pmod {12}$.

# Euler's Totient Function (Euler's Φ-Function)

In general, it seems that if $(a, m) = 1$, then $a^{f(m)} \equiv 1 \pmod m$ if $f(m)$ represents the number of integers relatively prime to m that are less than or equal to m. We will define this function as $\phi (m)$, which is known as Euler's Totient Function or Euler's Φ-Function.

 Definition: Euler's Totient Function or Euler's Φ-Function, $\phi (m)$ for a positive integer m is equal to the number of positive integers less than or equal to m that are relatively prime to m.

## Example 2

Calculate A) $\phi (6)$, B) $\phi (20)$ and C) $\phi (31)$.

• A) Let's first list the positive integers less than or equal to 6. They are 1, 2, 3, 4, 5, and 6. To calculate $\phi (6)$, we will axe off any of these integers a where $(a, 6) ≠ 1$. Specifically the integers 2, 3, 4, and 6 are not relatively prime to 6. 1 and 5 are the only two positive integers less than or equal to 6 that are also relatively prime to 6. There are two of these, so $\phi (6) = 2$.
• B) Calculating $\phi (2)$ will be a bit more cumbersome. Listing the positive integers less than or equal to 20 is as follows: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20. We know that 2, 4, 6, 8, 10, 12, 14, 16, 18, and 20 are not relatively prime to 20, since they all share a common divisor of 2. Our new list is now 1, 3, 5, 7, 9, 11, 13, 15, 17, 19. 5 and 15 can be axed off the list since $(5, 20) = 5$ and $(15, 20) = 5$. Our new list is 1, 3, 7, 9, 11, 13, 17, and 19. All of these integers are relatively prime to 20, and there are 8 of them, so $\phi (20) = 8$.
• C) To calculate $\phi (31)$, instead of listing all positive integers less than or equal to 31 and then axing off ones that aren't relatively prime to 31, take notice that 31 is a prime number, and its only divisors are 1 and 31. No positive integer less than 31 is divisible by 31. So there will be 30 positive integers less than or equal to 31 that are relatively prime to 31, so $\phi (31) = 30$.

# Euler's Theorem

 Theorem (Euler): For all integers m ≥ 1 and $\phi (m)$ be the number of positive integers less than or equal to m and relatively prime to m, then $a^{\phi (m)} \equiv 1 \pmod m$ whenever $(a, m) = 1$

We observed this theorem in our original observations upon constructing tables for when m = 9 and m = 12 above. We will now verify that this is essentially an extension to Fermat's Theorem with the following lemma.

## Lemma 1: If (a, m) = 1, and r1, r2, …, rΦ(m) are the positive integers less than m, the least residues mod m of ar1, ar2, …, arΦ(m) are a permutation of r1, r2, …, rΦ(m).

• Proof: There are Φ(m) numbers in the set of integers $ar_1, ar_2, ..., ar_{\phi (m)}$. Suppose that $ar_i \equiv ar_j \pmod m$ for some i and j such that $1 ≤ i ≤ \phi (m)$ and $1 ≤ j ≤ \phi m$. Since $(a, m) = 1$, then $r_i \equiv r_j \pmod m$. But ri and rj are least residues, so $r_i = r_j$. But ri and rj were assumed to be different so by contradiction, ri and rj are different.

We will omit the proof that all $(ar_i, m) = 1$, but attempt to verify it.

## Proof of Euler's Theorem

We will now prove Euler's theorem, $a^{\phi (m)} \equiv 1 \pmod m$ when $(a, m) = 1$.

• Proof: From lemma 1, we obtain that:
(1)
\begin{align} r_1r_2...r_{\phi (m)} \equiv (ar_1)(ar_2)...(ar_{\phi (m)}) \pmod m \\ r_1r_2...r_{\phi (m)} \equiv a^{\phi (m)}r_1r_2...r_{\phi (m)} \pmod m \\ 1 \equiv a^{\phi (m)} \pmod m \\ a^{\phi (m)} \equiv 1 \pmod m \\ \end{align}

### Example 3

Prove that if (72, n) = 1, then $n^{12} \equiv 1 \pmod {72}$.

Suppose that n is relatively prime to 72, that is (72, n) = 1. We note that 72 = 8 x 9, and hence (8, n) = 1, and (9, n) = 1. Since $\phi (8) = 4$, it follows by Euler's theorem that $n^4 \equiv 1 \pmod {8}$. Additionally, $n^{12} = (n^{4})^3 \equiv 1 \pmod {8}$.

Now, we also know that $\phi (9) = 6$, and by Euler's theorem that $n^6 \equiv 1 \pmod {9}$. Additionally $n^{12} = (n^6)^2 \equiv 1 \pmod {8}$.

Hence, if (72, n) = 1, then 8 | n12 - 1 and 9 | n12 - 1. Since (8, 9) = 1, it follows that 72 | n12 - 1, or more appropriately, $n^{12} \equiv 1 \pmod {72}$, and the proof is complete.