## 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.