7
$\begingroup$

How does $a\equiv b\pmod n$ implies $a$ and $b$ have the same remainder when divided by $n$?

I don't understand the huge jump from modular equivalence to having equal remainders.

I see by definition $a\equiv b\pmod n\,$ implies $n\mid (a-b)\,$ so $\,a-b=nk\,$ so $\,a=b+nk$.

But I do not see how this implies that $a$ and $b$ have the same remainder when divided by $n$.

  • 0
    Thank you! But it just showcases my inability to understand this concept haha. :(2012-11-12

3 Answers 3

6

We prove $\ n\mid a-b \iff a\,$ and $\,b\,$ leave the same remainder when divided by $\,n$.

If $a$ and $b$ have the same remainder $r$ when divided by $n$, then $a = q_1n + r$ and $b = q_2n + r$. Subtracting yields $\,a - b = q_1n + r - (q_2n + r) = (q_1 - q_2)n$, which means $n \mid (a-b)$.

Conversely suppose $n\mid (a-b).$ Then $\,a = b+nk\,$ for some integer $\,k.\,$ By the division algorithm, $b = qn + r\,$ for some integers $q$ and $0 \leq r < n$. Putting this value of $b$ into above $a = b + nk = (qn + r) + nk = (q + k)n + r$, so $r$ is also the remainder of $a$ divided by $n$.

  • 0
    I edited the answer a little. Of course you can revert it or modify it if you prefer.2016-07-11
2

$\,\bar a\, =\, a\bmod n\, =\, a-pn\ $ and

$\,\bar b\, =\, b \bmod n\, =\, b-qn\ $ for some integers $\,p,q$.

Therefore if $\ n\mid a-b\ $ then $\,n\,$ divides $\,\bar a-\bar b\, =\, a-b + (q-p)n$

By definition $\ 0 \le \bar a,\bar b < n\,$

therefore $\ 0 \le |\bar a -\bar b| < n$

so we conclude $\ \bar a - \bar b = 0,\,$ being divisible by $\,n.$

  • 0
    @Amr I edited the answer a little. Of course you can revert it or modify it if you prefer.2016-07-11
2

It may be helpful for you instead to think about the following.

Proposition: Let $a, b, m$ be integers with $m \geq 2$. Then, $a \equiv b \pmod{m} \qquad \text{if and only if} \qquad a = mk + b$ for some $k \in \mathbb{Z}$.

With the proposition in tow, consider the remainder of $a - b$ when divided by $m$.