Cardinality of Set of Residue Classes

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $m \in \Z_{>0}$ be a (strictly) positive integer.

Let $\Z_m$ be the set of residue classes modulo $m$.


Then:

$\card {Z_m} = m$

where $\card { \, \cdot \,}$ denotes cardinality.


Proof

By definition of the set of residue classes modulo $m$, $Z_m$ is the quotient set of congruence modulo $m$:

$\Z_m = \dfrac \Z {\mathcal R_m}$

where $\mathcal R_m$ is the congruence relation modulo $m$ on the set of all $a, b \in \Z$:

$\mathcal R_m = \set {\tuple {a, b} \in \Z \times \Z: \exists k \in \Z: a = b + k m}$


Thus by definition $\Z_m$ is the set of residue classes modulo $m$:

$\Z_m = \set {\eqclass 0 m, \eqclass 1 m, \ldots, \eqclass {m - 1} m}$

Hence:

\(\displaystyle \card {\Z_m}\) \(=\) \(\displaystyle \card {\set {0, 1, \ldots, m - 1} }\)
\(\displaystyle \) \(=\) \(\displaystyle m\)

$\blacksquare$


Sources