Order of Multiplicative Group of Reduced Residues

From ProofWiki
Jump to navigation Jump to search


Let $\struct {\Z'_m, \times_m}$ denote the multiplicative group of reduced residues modulo $m$.

The order of $\struct {\Z'_m, \times_m}$ is $\map \phi m$, where $\phi$ denotes the Euler $\phi$ function.


By definition, the order of a group is the cardinality of its underlying set.

By definition, the underlying set of $\struct {\Z'_m, \times_m}$ is the reduced residue system $\Z'_m$:

$\Z'_m = \set {\eqclass {a_1} m, \eqclass {a_2} m, \ldots, \eqclass {a_{\map \phi m} } m}$


$\forall k: a_k \perp m$

From Cardinality of Reduced Residue System, $\Z'_m$ has $\map \phi m$ elements.

Hence the result.