# Why are naturals < modulus equal if congruent? [uniqueness of remainder in a consecutive residue system]

Let $$a$$, $$b$$, and $$n$$ be integers with $$0 \le a,b \lt n$$. If $$\,a \equiv b \pmod n,\,$$ i.e. $$\,a-b = pk\,$$ for an integer $$k,\,$$ then $$a=b$$. Why does this congruence imply the equality?

It is not enough that $a,b$ are nonnegative, it is also necessary that $a,b$ are less than $n$. With both of these conditions, then $a\equiv b$ implies that $a=b$. The reason is that $a\equiv b$ means that $a-b$ is an integer multiple of $n$. However, this integer multiple cannot be $n$ or greater (else $a\ge b+n$, impossible), nor $-n$ or smaller (else $a+n\le b$, also impossible). Hence the only integer multiple of $n$ available is $0n$.

• You might want to specify that it is impossible because $a \ge b+n > b$ and also $a \le b-n < 0$, violating the conditions. Aug 16, 2017 at 3:05

The key trick here is the interplay between magnitude and divisibility — every nonzero multiple of $n$ must have a magnitude at least as large as $n$.

Symbolically, if $k \neq 0$, then $|kn| \geq |n|$.

Since integers in the same congruence class are separated by multiples of $n$, this puts a limit on how close they can be. We have

If $a \equiv b \bmod n$ and $a \neq b$, then $|a-b| \geq |n|$

The premise of the problem constrains both $a$ and $b$ to a narrow interval: they are both contained in the set $\{ 0, 1, \ldots, n-1 \}$. The largest possible difference between any two elements of this set has magnitude $n-1$. That is, for any two elements $x,y$ of this set, we have $|x-y| \leq n-1$.

So by the previous observation, the fact that $a \equiv b \bmod n$ implies that one of the following is true:

• $a = b$
• $|a-b| \geq n$

and we can rule out the second possibility because $|a-b| \leq n-1$.

Hint: their $$\rm\color{#c00}{difference}$$ is a natural smaller than $$\,n\,$$ and divisible by $$\,n\,$$ so it must be $$\,0,\,$$ i.e.

w.l.o.g. $$\ 0 \le b\le a < n\,\overset{\rm subtract\ b}\Longrightarrow\, 0\le \color{#c00}{a\!-\!b <} n\!-\!b\le\color{#0a0} n \$$ so $$\ \color{#0a0}n\mid \color{#c00}{a\!-\!b}\iff a\!-\!b = 0$$

Remark  This shows the uniqueness part of the fact that $$\,0,1,2,\ldots,n\!-\!1\,$$ form a complete system of representatives for equivalence classes of $$\,\Bbb Z_n =$$ integers $$\!\bmod n,\,$$ or, equivalently, the uniqueness of the remainder in the (standard) division algorithm. The same proof works for any sequence of $$n$$ consecutive integers since - as above - any two elements differ by less than the extreme elements, so less than $$n,\,$$ so their difference is divisible by $$n$$ only if they are equal. An example of an alternative sequence of remainders is those having least magnitude, e.g. $$\,0,\pm1, \pm2\pmod{\!5}$$. The argument easily generalizes to any arithmetic progression whose step-size is coprime to the modulus.

Corollary $$\ A\equiv B\pmod{\!n}\iff \underbrace{A\bmod n = B\bmod n}_{\textstyle \color{#c00}{a = b}}$$

• How can we show that if $a-b\leq n$ and $n\mid a-b$ then $a-b=0$? That part struggles me :/ Dec 14, 2019 at 22:09
• @man An $n$-multiple $\,kn\neq 0\,$ has greater magnitude $\,|kn| = |k||n|\ge |n|\,$ by $|k|\ge 1\,$ by $\,k\neq 0\ \$ Dec 14, 2019 at 22:26
• Sorry I do not understand what can you conclude from there. If $k\neq0$ and $kn\neq0$ then $n=0$? Dec 14, 2019 at 22:29
• @man That $m=0$ is the only multiple $m$ of $n$ with $\,0\le \color{#c00}m <\color{#0a0} n\,$ since all other multiples $>0\,$ are $\ge n.\$ Explicitly: the natural multiples of $n$ are $\,0,n,2n,3n,\ldots$ and there are $\rm\color{#c00}{none}$ strictly between $0$ and $n.\$ Said more informally, an integer divides a smaller integer only when the smaller $= 0\$ Dec 14, 2019 at 22:32
• Unique remainder $\Rightarrow$ unique quotient by $\,qn+r=q′n+r\Rightarrow qn=q′n\overset{n\neq 0}\Rightarrow q=q′\$ Apr 30, 2023 at 23:56