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

  • Thread starter Thread starter evinda
  • Start date Start date
AI Thread Summary
The discussion centers on the proof that if \( a \equiv b \pmod{m} \), then \( a \) and \( b \) yield the same remainder when divided by \( m \). It begins by establishing that \( m \mid a-b \) leads to the expression \( a-b = (q_1-q_2) \cdot m + (r_1 - r_2) \). The key point is that since \( m \) divides \( r_1 - r_2 \) and the remainders \( r_1 \) and \( r_2 \) are constrained between 0 and \( m \), the only solution is \( r_1 - r_2 = 0 \). This confirms that \( r_1 = r_2 \), reinforcing the definition of congruence in modular arithmetic. The conversation highlights the tautological nature of the proof, emphasizing the close relationship between congruence and remainders.
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