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

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

**Proof:**Suppose that $\gcd(a, n) = 1$. Then $a \in U(n)$. But $U(n)$ is a group of order $\phi(n)$ and the identity in $U(n)$ is $1$ and so $a^{\phi(n)} = 1$, i.e.:

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

*The condition "$\gcd(a, p) = 1$ where $p$ is prime" is equivalent to "$p$ does not divide $a$."*

**Proof;**Suppose that $\gcd(a, p) = 1$. Then $a \in U(p)$. But $\phi(p) = U(p) = p-1$, so by Euler's Theorem we have that: