◀ ▲ ▶Branches / Number-theory / Proof

Proof

(related to Proposition: Congruences and Division with Quotient and Remainder)

"$\Rightarrow$"

• Let $a=q_am+r_a$ and $b=q_bm+r_b$ in the division with quotient and remainder, with $0\le r_a < m$ and $0\le r_b < m.$
• We can subtract both equations and get $a-b=(q_a-q_b)m.$
• It follows $m\mid (a-b).$
• This means, by definition, $a\equiv b(m)$ (i.e. $a$ is congruent to $b$ modulo $m$).

"$\Leftarrow$"

• Let $a\equiv b(m)$ and $a=q_am+r_a$ with $0\le r_a < m.$
• Since $m\mid(a-b)$, there is an integer $q$ with $b=a+qm.$
• This means that $b= q_am+r_a+qm=(q_a+q)m+r_a=q_bm+r_a$
• It follows, that any division with quotient and remainder of $b$ results in the same remainder $r_a.$

Altogether, it follows $a\equiv b(m)\Longleftrightarrow r_a=r_b.$

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Landau, Edmund: "Vorlesungen über Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927
2. Jones G., Jones M.: "Elementary Number Theory (Undergraduate Series)", Springer, 1998