Euler's Theorem
Theorem: If\[a \in \mathbb{Z}_n^*\]
then \[a^{\phi(n)} = 1 \pmod{n}\]
.This reduces to Fermat’s Little Theorem when
\[n\]
is prime.Proof: Let
\[m = \phi(n)\]
, and label the units \[u_1,...,u_m\]
. Consider the sequence \[a u_1,...,a u_m\]
(we multiply each unit by \[a\]
). If \[a u_i = a u_j\]
, then multiplying by \[a^{-1}\]
(which exists since \[a\]
is a unit) shows \[u_i = u_j\]
, hence the members of the sequence are distinct. Furthermore products of units must also be units, hence \[a u_1, ..., a u_m\]
must be \[u_1,...,u_m\]
in some order.Multiplying all the units together gives
\[ a u_1 ... a u_m = u_1 ... u_m.\]
.Rearranging yields
\[ a^{\phi(n)} = a^m = (u_1 ... u_m)(u_1 ... u_m)^{-1} = 1 \]
.Similarly Euler’s Theorem also gives an alternative way to compute inverses. For
\[a \in \mathbb{Z}_n^*\]
, \[a^{-1}\]
can be computed as \[a^{\phi(n)-1}\]
. This is efficient as we may use repeated squaring, but Euclid’s algorithm is still faster (why?) and does not require one to compute \[\phi(n)\]
.These theorems do not tell us the order of a given unit
\[a\in\mathbb{Z}_n^*\]
but they do narrow it down: let \[x\]
be the order of \[a\]
. If we know \[a^y = 1\]
by Euclid’s algorithm we can find \[m, n\]
such that \[ d = m x + n y \]
.where
\[d = \gcd(x, y)\]
. Then \[ a^d = a^{m x + n y} = (a^x)^m (a^y)^n = 1 \]
thus sinc e
\[d \le x\]
we must have \[d = x\]
(since \[x\]
is the smallest positive integer for which \[a^x = 1\]
), and hence \[x\]
must be a divisor of \[y\]
. Thus by Euler’s Theorem, the order of \[a\]
divides \[\phi(n)\]
.These statements are in fact trivial corollaries of Lagrange’s Theorem from group theory. Of course Fermat and Euler died long before group theory was discovered.