Euler's Theorem

From ProofWiki

Jump to: navigation, search

Theorem

Let $a, m \in \Z: a \perp m$.

Let $\phi \left({m}\right)$ be the Euler Phi Function of $m$.

Then:

$a^{\phi \left({m}\right)} \equiv 1 \pmod m$

Let $ k = \left|{\left[\!\left[{a}\right]\!\right]_m}\right|$ where $\left[\!\left[{a}\right]\!\right]_m \in \Z'_m$.

Now $\left|{\Z'_m}\right| = \phi \left({m}\right)$, from the definition of the Euler Phi Function.

Thus:

$\displaystyle $	$\displaystyle \left[\!\left[{a}\right]\!\right]_m^k$	$=$	$\displaystyle \left[\!\left[{1}\right]\!\right]_m$	$\displaystyle $	by definition of the order of a group element
$\displaystyle \implies$	$\displaystyle \left[\!\left[{a}\right]\!\right]_m^{\phi \left({m}\right)}$	$=$	$\displaystyle \left[\!\left[{a^{\phi \left({m}\right)} }\right]\!\right]_m$	$\displaystyle $	by Congruence of Powers
$\displaystyle $	$\displaystyle $	$=$	$\displaystyle \left[\!\left[{1}\right]\!\right]_m$	$\displaystyle $
$\displaystyle \implies$	$\displaystyle a^{\phi \left({m}\right)}$	$\equiv$	$\displaystyle 1 \pmod m$	$\displaystyle $	by definition of residue class

$\blacksquare$

This entry was named for Leonhard Paul Euler.

\(\displaystyle \)	\(\displaystyle \left[\!\left[{a}\right]\!\right]_m^k\)	\(=\)	\(\displaystyle \left[\!\left[{1}\right]\!\right]_m\)	\(\displaystyle \)	by definition of the order of a group element
\(\displaystyle \implies\)	\(\displaystyle \left[\!\left[{a}\right]\!\right]_m^{\phi \left({m}\right)}\)	\(=\)	\(\displaystyle \left[\!\left[{a^{\phi \left({m}\right)} }\right]\!\right]_m\)	\(\displaystyle \)	by Congruence of Powers
\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left[\!\left[{1}\right]\!\right]_m\)	\(\displaystyle \)
\(\displaystyle \implies\)	\(\displaystyle a^{\phi \left({m}\right)}\)	\(\equiv\)	\(\displaystyle 1 \pmod m\)	\(\displaystyle \)	by definition of residue class