Euler's Theorem

From ProofWiki
Jump to navigation Jump to 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:

\(\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.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Euler%27s_Theorem&oldid=593979"