Cardinality of Reduced Residue System

Theorem

Let $n \ge 2$.

Let $\Z'_n$ be the reduced residue system modulo $n$.

Then:

$\card {\Z'_n} = \map \phi n$

where $\map \phi n$ is the Euler phi function.

Proof

Recall the definition of $\Z'_n$:

$\Z'_n = \set {\eqclass k n \in \Z_n: k \perp n}$

and the definition of $\map \phi n$:

$\map \phi n = \card {\set {k: 1 \le k \le n, k \perp n} }$

The result follows from Integer is Congruent to Integer less than Modulus.

$\blacksquare$

Sources

• 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {4-2}$ Residue Systems: Theorem $\text {4-5}$