Initial Segment of Natural Numbers forms Complete Residue System
Jump to navigation
Jump to search
Theorem
Let $m \in \Z_{\ne 0}$ be a non-zero integer.
Let $\N_m = \set {0, 1, 2, \ldots, m - 1}$ denote the initial segment of $\N$
Then $\N_m$ is a complete residue system modulo $m$.
Proof
Let $n \in \Z$.
From the Division Theorem there exist unique integers $q$ and $u$ such that:
- $n = m q + u$
such that $0 \le u < m$.
That is:
- $n \equiv u \pmod m$
and $u$ is one of $0, 1, \ldots, m - 1$.
Also, since $\forall i, j \in \N_m: \size {i - j} < m$, no two elements of $\N_m$ are congruent.
Thus $\N_m = \set {0, 1, 2, \ldots, m - 1}$ is a complete residue system modulo $m$.
$\blacksquare$
Sources
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {4-2}$ Residue Systems: Corollary $\text {4-1}$