Euler's Theorem

Euler's Theorem states that, in the modular arithmetic ring $\mathbb Z_m$ for any $m\in\mathbb N$, $a^{\varphi(m)}=1$ for all $a\in\mathbb U_m$, the group of units of $\mathbb Z_m$. That is, for all $a\in\mathbb Z$ with $\mathrm{gcd}(a,m)=1$, we have $$a^{\varphi(m)}\equiv 1\bmod m$$ The proof of this theorem is short and only requires a few key observations:

• The unit group $\mathbb U_m$ has $\varphi(m)$ elements.

• By Lagrange's Theorem , the order of every element of a group divides the order of the group.

• If $d|n$ and $a^d\equiv 1\bmod m$, then $a^n\equiv 1\bmod m$.

abstract-algebra

number-theory

back to home page