I was reading through a proof of the following proposition:

$$a\equiv b\!\!\pmod{m}\iff (a\bmod m) = (b\bmod m)$$

i.e. $\ a \equiv b \pmod{\!m} $ if and only if a and b leave the same remainder when divided by m

I came across a statement that I didn't quite understand. I boxed my area of confusion below:

enter image description here I am confused because I expected the inequality to be $ 0 \leq r_1 - r_2 < m$. How did they come to the conclusion that $ -m < r_1 - r_2 < m$

Any input is appreciated.

  • $\begingroup$ What if $r_1 = 0$ and $r_2 > 0$? $\endgroup$ – Brad Mar 22 '14 at 20:40

Since $$0\le r_2<m$$ then \begin{align}&-m<-r_2\le0\quad \text{and since}\\ &\;\;\;0\le r_1<m\end{align} then by adding term by term we find $$-m<r_1-r_2<m$$

  • $\begingroup$ Oh! I see what they did now. So to add them, they must also add the inequality. But in this case we are adding the negative (subtracting) so we flip the inequality and then add. Thanks so much! $\endgroup$ – user132586 Mar 22 '14 at 20:47
  • $\begingroup$ You're welcome. $\endgroup$ – user63181 Mar 22 '14 at 20:48
  • $\begingroup$ Could you explain why that implies that $r_1 - r_2 = 0$? $\endgroup$ – user132586 Mar 22 '14 at 20:50
  • 1
    $\begingroup$ Since $m|(r_1-r_2)$ then $r_1-r_2=km,\; k\in \Bbb Z$ but since $$-m<r_1-r_2<m$$ then $r_1-r_2=0$ the only possible multiple of $m$ between $-m$ and $m$. $\endgroup$ – user63181 Mar 22 '14 at 20:53
  • $\begingroup$ Oh right, its bounded by divisibility. $\endgroup$ – user132586 Mar 22 '14 at 20:54

Sami explained the inequality. I explain another way, avoiding it.

$\qquad m\mid a\!-\!b \iff a\!-\!b \in m\Bbb Z \iff a+m\Bbb Z\, =\, b+m\Bbb Z$

$\qquad a\ {\rm mod}\ m\, $ is the least nonnegative element of $\ a+m\Bbb Z$

$\qquad b\ {\rm mod}\ m\, $ is the least nonnegative element of $\ b+m\Bbb Z.$

Being equal sets, they have equal least nonnegative elements.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.