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