# Why $a\equiv b\pmod n$ implies $a$ and $b$ have equal remainder when divided by $n$?

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

-
+1 Nice question. – amWhy Nov 12 '12 at 1:26
Thank you! But it just showcases my inability to understand this concept haha. :( – Yellow Skies Nov 12 '12 at 1:34

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

-
I edited the answer a little. Of course you can revert it or modify it if you prefer. – Bill Dubuque Jul 11 at 20:26

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

-

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

-
How did you get that $a \mod n=a-pn$? I don't recall that at all.. Pardon me. – Yellow Skies Nov 12 '12 at 1:37
The definition of a mod n is the minimum of the intersection of the sets {a-pn|p is an integer} and the set of natural numbers – Amr Nov 12 '12 at 1:44
Therefore a mod n belongs to the set {a-pn|p is an integer} . Thus there exists an integer p such that a mod n=a−pn – Amr Nov 12 '12 at 1:45
I see! Thankszz – Yellow Skies Nov 12 '12 at 1:52
@Amr I edited the answer a little. Of course you can revert it or modify it if you prefer. – Bill Dubuque Jul 11 at 20:14