Congruent Integers less than Half Modulus are Equal
Jump to navigation
Jump to search
Theorem
Let $k \in \Z_{>0}$ be a strictly positive integer.
Let $a, b \in \Z$ such that $\size a < \dfrac k 2$ and $\size b < \dfrac k 2$.
Then:
- $a \equiv b \pmod k \implies a = b$
where $\equiv$ denotes congruence modulo $k$.
Proof
We have that:
- $-\dfrac k 2 < a < \dfrac k 2$
and:
- $-\dfrac k 2 < -b < \dfrac k 2$
Thus:
- $-k < a - b < k$
Let $a \equiv b \pmod k$
Then:
- $a - b = n k$
for some $n \in \Z$.
But as $-k < n k < k$ it must be the case that $n = 0$.
Thus $a - b = 0$ and the result follows.
$\blacksquare$
Sources
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {4-1}$ Basic Properties of Congruences: Exercise $5$