0
$\begingroup$

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.

$\endgroup$

marked as duplicate by Bill Dubuque elementary-number-theory Sep 5 '17 at 19:17

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Temirzhan Sep 5 '17 at 18:54
  • $\begingroup$ Because $r_1-r_2=(a-b)-m(q_1-q_2)$ and $a-b=mk$ for some $k$. $\endgroup$ – punctured dusk Sep 5 '17 at 18:56
  • $\begingroup$ 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. $\endgroup$ – Temirzhan Sep 5 '17 at 18:59
  • $\begingroup$ nonono, we don't want to mention congruences again to finish it $\endgroup$ – punctured dusk Sep 5 '17 at 19:06
  • $\begingroup$ 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? $\endgroup$ – Temirzhan Sep 5 '17 at 19:10
1
$\begingroup$

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

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

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