Why are naturals < modulus equal if congruent? [uniqueness of remainder]

Solution 1:

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$.

Solution 2:

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$.

Solution 3:

Hint: their $\rm\color{#c00}{difference}$ is a 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.