Euler's Theorem and Fermat's Little Theorem

Recall from the Lagrange's Theorem page that if $(G, *)$ is a finite group and $(H, *)$ is a subgroup then the number of elements in $H$ must divide the number of elements in $G$ and moreover:

(1)

\begin{align} \quad \mid G \mid = [G : H] \mid H \mid \end{align}

With Lagrange's theorem we can prove two other important theorems rather simply. Before we do so, we will need to get a quick definition out of the way. If $n \in \mathbb{N}$, define a function $\phi : \mathbb{N} \to \mathbb{N}$ to be such that $\phi(n)$ be the number of positive integers $m$ with $1 \leq m \leq n$ such that $\gcd (m, n) = 1$.

Equivalently, for each $n \in \mathbb{N}$ we can let $U(n)$ denote the set of all positive integers $m$ with $1 \leq m \leq n$ such that $\gcd (m, n) = 1$, and then $(U(n), \cdot) = (\mathbb{Z}_n^{\times}, \cdot)$ is a group with the operation of multiplication $\cdot$ defined for all $a, b \in U(n)$ by $a \cdot b = ab \mod n$. It's relatively easy to show that $(U(n), \cdot)$ is itself a group. Thus $\phi(n) = \mid U(n) \mid$.

Lemma 1: Let $G$ be a finite group of order $n$. Then: a) For each $a \in G$, the order of $a$ divides $n$. b) For any $a \in G$ we have that $a^n = e$, where $e$ denotes the identity element.

• Proof of a) Note that $\mathrm{ord}(a) = |\langle a \rangle|$. Since $\langle a \rangle$ is a subgroup of the finite group $G$, we have by Lagrange's theorem that $\mathrm{ord}(a) = |\langle a \rangle| \mid |G|$. $\blacksquare$

• Proof of b) Let $a \in G$. By (a) we have that $\mathrm{ord}(a) \mid |G| = n$. So there exists a positive integer $k$ such that $\mathrm{ord}(a) k = n$. Therefore:

(2)

\begin{align} \quad a^n = a^{\mathrm{ord}(a)k} = (a^{\mathrm{ord}(a)})^k = e^k = e \quad \blacksquare \end{align}

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

• Proof: Let $\gcd(a, n) = 1$. First suppose that $1 \leq a < n$. Then $a \in U(n)$. By Lemma 1 (b) we have that $a^{|U(n)|} = 1$ for all $(a, n) = 1$. But $|U(n)| = \phi(n)$. So $a^{\phi(n)} = 1$.

• So in general, we see that if $\gcd (a, n) = 1$ then:

(3)

\begin{align} \quad a^{\phi(n)} \equiv 1 \pmod n \quad \blacksquare \end{align}

Theorem 3 (Fermat's Little Theorem): If $\gcd(a, p) = 1$ where $p$ is prime then $a^{p-1} \equiv 1 \pmod p$.

• Proof: If $p$ is prime then $\varphi(p) = p - 1$. So Fermat's Little Theorem follows immediately as a special case of Theorem 2. $\blacksquare$