Euler's Theorem

From ProofWiki
Jump to: navigation, search

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.

By Order of Element Divides Order of Finite Group:

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

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

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


Thus:

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

$\blacksquare$


Source of Name

This entry was named for Leonhard Paul Euler.


Sources