# $a\equiv b\pmod n$ iff $a \bmod m = b \bmod m$ [duplicate]

I'm sort of stuck on this proof

I know that $a\equiv b\pmod n$ means $a - b = mk$ for some integer $k$
and by the Division algorithm
$a = mq_1 + r_1$
$b = mq_2 + r_2$

$a - b = m(q_1 - q_2) + (r_1 - r_2)$

Once I get to the line above I get stuck how do I show that $r_1 - r_2$ are actually equal and the same remainder? I've looked at other proofs that just say the remainder for $a$ and $b$ equal to $r$.

I feel like i'm missing something extremely obvious.

## marked as duplicate by Bill Dubuque elementary-number-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Sep 5 '17 at 19:17

You have $a-b=m(q_1-q_2)+(r_1-r_2)$ so $m$ divides $r_1-r_2$.

Yet $0\leq |r_1-r_2|\leq\max(r_1,r_2) <m$.

Recall that $m$ divides $x$ implies $x=0$ or $|x|\geq m$. (Proof: if $x\neq0$, then $|x|=|m|\cdot|\frac xm|\geq |m|\cdot1$)

So $|r_1-r_2|=0$.

• I'm a bit confused sorry.. How do we know m divides r1 - r2? and the last line i don't understand at all how does that show r1=r2 – Temirzhan Sep 5 '17 at 18:54
• Because $r_1-r_2=(a-b)-m(q_1-q_2)$ and $a-b=mk$ for some $k$. – punctured dusk Sep 5 '17 at 18:56
• Ah okay so then i can say that since r1 - r2 are a mulitple of m they are congruent mod m and therefore equal? Im a bit rusty, feel free to correct me. – Temirzhan Sep 5 '17 at 18:59
• nonono, we don't want to mention congruences again to finish it – punctured dusk Sep 5 '17 at 19:06
• Im not sure how to "explain" in english that they are equal then. Is it because r1 - r2 is equal to 0 due to mk - m(q1 - q2) is equal to 0? but how do I know that those two quantities are equal? – Temirzhan Sep 5 '17 at 19:10

You seem to be asking about the proof for direction $a\equiv b\pmod{m}\implies a \mod m = b\mod m$

As you correctly note, $a\equiv b \pmod{m}$ means $a-b=mk$ for some $k\in\mathbb{Z}$.

Now by the division algorithm, write $a=mq+r$ where $0\le r < m$.

Then $b=a-mk=(mq+r)-mk=m(q-k)+r$.

By uniqueness in the division algorithm, this means $r$ is the remainder of dividing $b$ by $m$.

So $a$ and $b$ have the same remainder on division by $m$, and so $a \mod m = b\mod m$.

• is their anyway to continue the way i did it where i set r1 and r2 as unequal and show that they are equal? – Temirzhan Sep 5 '17 at 18:38