5
$\begingroup$

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?

$\endgroup$

3 Answers 3

13
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – Kenny Lau
    Aug 16, 2017 at 3:05
5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ How can we show that if $a-b\leq n$ and $n\mid a-b$ then $a-b=0$? That part struggles me :/ $\endgroup$
    – manooooh
    Dec 14, 2019 at 22:09
  • 1
    $\begingroup$ @man An $n$-multiple $\,kn\neq 0\,$ has greater magnitude $\,|kn| = |k||n|\ge |n|\,$ by $|k|\ge 1\,$ by $\,k\neq 0\ \ $ $\endgroup$ Dec 14, 2019 at 22:26
  • $\begingroup$ Sorry I do not understand what can you conclude from there. If $k\neq0$ and $kn\neq0$ then $n=0$? $\endgroup$
    – manooooh
    Dec 14, 2019 at 22:29
  • 1
    $\begingroup$ @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\ $ $\endgroup$ Dec 14, 2019 at 22:32
  • 1
    $\begingroup$ Unique remainder $\Rightarrow$ unique quotient by $\,qn+r=q′n+r\Rightarrow qn=q′n\overset{n\neq 0}\Rightarrow q=q′\ $ $\endgroup$ Apr 30, 2023 at 23:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .