Euler's Theorem

The fundamental theorem of arithmetic states that any positive integer $N$ can be uniquely factorized into the form $N = p_1 ^{q_1} p_2 ^{q_2} \ldots p_n^ {q_n}$, where $p_i$ are distinct primes, and $q_i$ are positive integers. How many integers $1 \leq k \leq N$ are there such that $gcd(k, N) =1$? This seems difficult to count directly, so instead, consider the integers $1 \leq k \leq N$ such that $gcd(k, N)\neq 1$ ($k$ are the integers divisible by $p_i$ for some $i$). Of the integers less than $N$, $\frac {N}{p_1}$ of them are multiples of $p_1$. Similarly, $\frac {N}{p_2}$ of the integers less than $N$ are multiples of $p_2$. However, we have included multiples of $p_1 p_2$ in both of these sets, thereby double counting.

The Principle of Inclusion and Exclusion (PIE) is a method to count the number of elements in overlapping sets. For $i=1$ to $n$, let $P_i$ be the set of integers smaller than or equal to $N$ that are multiples of $p_i$. Then the number of integers that are multiples of $p_i$ is $|P_i| = \frac {N}{p_i}$. The number of integers that are multiples of $p_ip_j$ is $|P_i \cap P_j| = \frac {N}{p_ip_j}$. This holds true in general: for any subset $S$ of $\{ 1, 2, \ldots, n\}$, the number of integers that are multiples of $\displaystyle \prod_{s\in S} p_s$ is $\lvert \bigcap_{s\in S} P_s \rvert = \frac {N}{\prod_{s\in S} p_s}$.

Then, the set of numbers that satisfy $\gcd(k, N)=1$ is exactly the set of numbers that are not a multiple of any $p_i$, hence are not in any of the sets $P_i$. By the Principle of Inclusion and Exclusion,

$\begin{aligned} N - \big\vert \bigcup_i P_i \big\vert = & N - \sum_{i} \big\vert P_i \big\vert + \sum_{i\neq j} \big\vert P_i \cap P_j \big\vert - \sum_{ i \neq j, j \neq k, k\neq i} \big\vert P_i \cap P_j \cap P_k \big\vert + \ldots + (-1)^n \big\vert \bigcap_i P_i \big\vert \\ = & N - \sum_{i} \frac {N}{p_i} + \sum_{i\neq j} \frac {N}{p_ip_j} - \sum_{ i \neq j, j \neq k, k\neq i} \frac {N}{p_i p_j p_k} + \ldots + (-1)^n \frac {N}{\prod_i p_i} \\ = & N \left( 1-\frac {1}{p_1} \right) \left(1-\frac {1}{p_2} \right) \left( 1-\frac {1}{p_3} \right) \ldots \left( 1-\frac {1}{p_n} \right) \\ \end{aligned}$

The number of integers smaller than $N$ that are coprime to $N$ is Euler's phi function $\phi(N)$.

Euler's Theorem: If $\gcd (a, N) = 1$, then $a^{\phi(N)} \equiv 1 \pmod{N}$.

Proof: Let $\mathcal{S}$ be the set of integers that are coprime to $N$. Let $a\mathcal{S}$ be the set of (possibly repeated) integers of the form $\{ as : s \in \mathcal{S} \}$ taken modulo $N$. First, we show that there are no repeats. If there are repeats, i.e., $as_i \equiv as_j \pmod{N}$, then Modulo Arithmetic Property H implies $s_i \equiv s_j \pmod{N}$. But since every element $s$ in $\mathcal{S}$ is smaller than $N$, this is not possible. Second, we show that $a\mathcal{S}$ is contained within $\mathcal{S}$. This is true because given $s$ an element of $\mathcal{S}$, $1\leq \gcd(as, N) \leq \gcd(a,N) \times \gcd (s, N) = 1\times 1 = 1$, so $\gcd(as, N)=1$ which shows that $as$ is an element of $S$. Since $a\mathcal{S}$ is a set of $\phi(N)$ distinct elements contained in $\mathcal{S}$, which is also a set of $\phi(N)$ distinct elements, it follows that these sets are the same modulo $N$.

Since the sets contain the exact same elements modulo $N$, the product of all the elements of $a\mathcal{S}$ is equal to the product of all the elements of $\mathcal{S}$ modulo $N$. Therefore,

$as_1 \cdot as_2 \cdot \ldots \cdot as_{\phi(N)} \equiv s_1 \cdot s_2 \cdot \ldots \cdot s_{\phi(N)} \pmod{N}.$

Since $s_1 \cdot s_2 \cdot \ldots \cdot s_{\phi(N)}$ is coprime to $N$, it follows from Modulo Arithmetic Property H that $a^{\phi(N)} \equiv 1 \pmod{N}$.

Note: The set $\mathcal{S}$ is also called a reduced residue system modulo N.

Worked Examples

1. What is the units digit of ${{9^7} ^ 5} ^3$?

Solution: Finding the units digit of a number is equivalent to working modulo 10. By Euler's theorem, we need only determine the value of the exponent ${7^5}^3$ modulo $\phi(10)=10\times(1-\frac {1}{2})\times(1-\frac {1}{5}) = 4$. Again by Euler's theorem, we need only determine the value of the exponent ${5^3}$ modulo $\phi(4)=4\times (1-\frac {1}{2})=2$. Then

$\begin{aligned} 5^3 &\equiv & 1^3 & \equiv & 1 & \pmod{2} \\ {7^5}^3 &\equiv & 7^1 & \equiv & 3^1 \equiv 3 &\pmod{4}\\ {{9^7}^5}^3 &\equiv & 9^3 & \equiv & 729 \equiv 9 &\pmod{10}\\ \end{aligned}$

Note: Another approach is to realize that $9^n \pmod{10}$ is the sequence $9, 1, 9, 1, 9, 1, \ldots$ which has period 2. Since the parity of the exponent is odd, this implies the last digit is 9.

2. Calculate (by hand) the value of $\frac {5}{21}$.

Solution: By Euler's theorem, $\phi(21)=21\times(1-\frac {1}{3})(1-\frac {1}{7})=12$, implying $10^{12}\equiv 1 \pmod{21}$. In fact, we can do better than this by applying Euler's theorem to $\phi(3)=3\times(1-\frac {1}{3})=2$ and $\phi(7)=7\times(1-\frac {1}{7}) = 6$. We know that $10^6 \equiv (10^2)^3 \equiv 1^3 \equiv 1 \pmod{3}$ and $10^6 \equiv 1 \pmod{7}$, thus $10^6 \equiv 1 \pmod{21}$. In particular, $10^6-1 = 21 \times 47619$. Hence, $\frac {5}{21} = \frac {5 \times 47619}{21 \times 47619} = \frac{238095}{999999}=0.238095238095......$

3. [Fermat's Little Theorem] If $p$ is a prime and $a$ is an integer, show that $a^p \equiv a \pmod{p}$.

Solution: Observe that if $p$ is a prime, then $\phi(p)=p\times (1-\frac {1}{p}) = p-1$. Hence, by Euler's Theorem, if $\gcd(a,p)=1$, then

$a^{p-1} \equiv 1 \pmod{p} \Rightarrow a^p \equiv a \pmod{p}.$

What about the values of $a$ such that $\gcd(a,p)\neq 1$? In this case, $a$ will be a multiple of $p$, so $a^p \equiv 0^p \equiv 0 \equiv a \pmod{p}$.

Note: This can also be shown by induction on $a$.

4. Show that if $n$ is an odd integer, then $n$ divides $2^{n!} -1$.

Solution: By Euler's Theorem, $n$ divides $2^{\phi(n)}-1$. Since $\phi(n) < n$, we have $n! = \phi(n) \cdot k$ for some integer $k$. Since

$2^{n!}-1 = (2^{\phi(n)}-1)(2^{\phi(n)\cdot(k-1)}+ 2^{\phi(n)\cdot(k-2)}+\ldots + 1),$

it follows that $n$ also divides $2^{n!}-1$.