Order of Group of Units of Integers Modulo n

Theorem

Let $n \in \Z_{\ge 0}$ be an integer.

Let $\struct {\Z / n \Z, +, \cdot}$ be the ring of integers modulo $n$.

Let $U = \struct {\paren {\Z / n \Z}^\times, \cdot}$ denote the group of units of this ring.

Then:

$\order U = \map \phi n$

where $\phi$ denotes the Euler $\phi$-function.

Proof

By Reduced Residue System under Multiplication forms Abelian Group, $U$ is equal to the set of integers modulo $n$ which are coprime to $n$.

It follows by Cardinality of Reduced Residue System:

$\order U = \map \phi n$

$\blacksquare$

Sources

• 1982: P.M. Cohn: Algebra Volume 1 (2nd ed.) ... (previous) ... (next): $\S 2.3$: Congruences