MHB Why do we conclude that r1-r2=0?

  • Thread starter Thread starter evinda
  • Start date Start date
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! :)

I am looking at the proof of the following sentence:
$a \equiv b \pmod m \Rightarrow a,b$ give the same remainder when they are divided by $m$.

That's the proof that my teacher gave:

Let $a \equiv b \pmod m$.So, $ m \mid a-b$

Let $a=q_1 \cdot m+r_1, 0 \leq r_1 < m$
and $b=q_2 \cdot m+r_2,0 \leq r_2<m$

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

As $m \mid a-b \Rightarrow m \mid r_1-r_2$

As $-m<r_1-r_2<m \Rightarrow r_1-r_2=0$ $\Rightarrow r_1=r_2$.

Could you explain me the red part? :confused:
 
Mathematics news on Phys.org
evinda said:
Hello! :)

I am looking at the proof of the following sentence:
$a \equiv b \pmod m \Rightarrow a,b$ give the same remainder when they are divided by $m$.

That's the proof that my teacher gave:

Let $a \equiv b \pmod m$.So, $ m \mid a-b$

Let $a=q_1 \cdot m+r_1, 0 \leq r_1 < m$
and $b=q_2 \cdot m+r_2,0 \leq r_2<m$

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

As $m \mid a-b \Rightarrow m \mid r_1-r_2$

As $-m<r_1-r_2<m \Rightarrow r_1-r_2=0$ $\Rightarrow r_1=r_2$.

Could you explain me the red part? :confused:

$m|r_{1}-r_{2}$ so $ma=r_{1}-r_{2}$ for some integer $a$. If $a$ is non-zero, then $|r_{1}-r_{2}|$ would be at least as large as $|m|$, contrary to the inequality $-m<r_{1}-r_{2}<m$. Hence $a=0$, so that $r_{1}-r_{2}=0$
 
Fermat said:
$m|r_{1}-r_{2}$ so $ma=r_{1}-r_{2}$ for some integer $a$. If $a$ is non-zero, then $|r_{1}-r_{2}|$ would be at least as large as $|m|$, contrary to the inequality $-m<r_{1}-r_{2}<m$. Hence $a=0$, so that $r_{1}-r_{2}=0$

How do we conclude to the inequality $-m<r_{1}-r_{2}<m$? :confused:
 
evinda said:
How do we conclude to the inequality $-m<r_{1}-r_{2}<m$? :confused:

It follows from the inequalities $0 \leq r_1 < m$ and $0 \leq r_2<m$.
 
Fermat said:
It follows from the inequalities $0 \leq r_1 < m$ and $0 \leq r_2<m$.

I understand...Thank you! (Nod)
 
evinda said:
Hello! :)

I am looking at the proof of the following sentence:
$a \equiv b\pmod m \Rightarrow a,b$ give the same remainder when they are divided by $m$.
I would rewrite this, replacing words by symbols, to get:
$a \equiv b\pmod m \Rightarrow a\pmod m = r, b\pmod m = r$

then as your teacher stated, by definition
$a \equiv b\pmod m \Rightarrow m \mid a-b$

so, by substitution, we have as an equivalent to the instructor's problem statement:
$m \mid a-b \Rightarrow a\pmod m = r, b\pmod m = r$

also by definition we have:
$a\pmod m = r \Rightarrow a=mq_1+r$
and
$b\pmod m = r \Rightarrow b=mq_2+r$

so again by substituting into the problem definition we have:
$m \mid a-b \Rightarrow a=mq_1+r$ and $b=mq_2+r$
then
$m \mid a-b \Rightarrow (a-b) = m(q_1 - q_2)$
and finally:
$m \mid a-b \Rightarrow m \mid a-b$

Really, the actual statement to be proven was so close to being a fundamental definition that the professor had to work hard to obscure that fact.
 
Last edited:
I would personally put the "mod m" part into parentheses only when explicitly working with a congruence relation, and just writing "a mod m" when using it to denote a remainder operation. I find it's more consistent and less confusing to people, but it's no big deal.

And, yes, the argument here is near tautological. $a \equiv b \pmod{m}$ is pretty much the definition of "$a$ and $b$ leave the same remainder when divided by $m$", though I suppose it depends on what fundamental definition of modular arithmetic you're working your way up from.
 
Back
Top