# Euler's Theorem

## Theorem

Let $a, m \in \Z$ be coprime integers: $a \perp m$.

Let $\map \phi m$ be the Euler $\phi$ function of $m$.

Then:

$a^{\map \phi m} \equiv 1 \pmod m$

### Corollary

Let $p^n$ be a prime power for some prime number $p > 1$.

Let $a$ be an integer not divisible by $p: p \nmid a$.

Then:

$a^{\paren {p - 1} p^{n - 1} } \equiv 1 \pmod {p^n}$

## Proof

Let $\eqclass a m$ denote the residue class modulo $m$ of $a$.

Since $a \perp m$, it follows by Reduced Residue System under Multiplication forms Abelian Group that $\eqclass a m$ belongs to the abelian group $\struct {\Z'_m, \times}$.

Let $k = \order {\eqclass a m}$ where $\order {\, \cdot \,}$ denotes the order of a group element.

$k \divides \order {\Z'_m}$

By the definition of the Euler $\phi$ function:

$\order {\Z'_m} = \map \phi m$

Thus:

 $\ds \eqclass a m^k$ $=$ $\ds \eqclass a m$ Definition of Order of Group Element $\ds \leadsto \ \$ $\ds \eqclass a m^{\map \phi m}$ $=$ $\ds \eqclass {a^{\map \phi m} } m$ Congruence of Powers $\ds$ $=$ $\ds \eqclass 1 m$ $\ds \leadsto \ \$ $\ds a^{\map \phi m}$ $\equiv$ $\ds 1 \pmod m$ Definition of Residue Class

$\blacksquare$

## Source of Name

This entry was named for Leonhard Paul Euler.