Congruent Integers less than Half Modulus are Equal

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$