Why are naturals < modulus equal if congruent? [uniqueness of remainder] Let $a$, $b$, and $n$ be integers with $0 \le a \lt n$ and $0 \le b \lt n$. Suppose $a \equiv b \pmod n$. Then $a-b=0$ and $a=b$. Why does the congruence of two non negative integers imply that they must be equal?
 A: 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.
A: 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$.
A: 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$.
