# Modulo Congruence: How does $a=b\bmod n$ implies $a$ and $b$ have the same remainder when divided by $n$?

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

I don't understand the huge jump from modulo to implying the same remainder.

I see that $a=b\mod n$ implies $n|(a-b)$ by definition. Then $a-b=nk$ implying $a=b+nk$.

But I do not see how does this show 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

If $a$ and $b$ have the same remainder $r$ when divided by $n$, then $a = q_1n + r$ and $b = q_2n + r$. Then substracting the two equations would give you $a - b = q_1n + r - (q_2n + r) = (q_1 - q_2)n$, which means $n | (a-b)$.
Now if $n | (a-b)$. We know that $b = qn + r$ for some $q$ and $0 \leq r < n$ as you showed $a = b + nk = (qn + r) + nk = n(q + k) + r$, and as you see $r$ is also the remainder of $a$ after dividing by $n$.

-

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

-

$a$ mod n$=a-pn$ and $b$ mod n$=b-qn$ for some integers p,q

Therefore we deduce that n divides ($a$ mod n-$b$ mod n)

Since 0 < = ($a$ mod n,$a$ mod n) < n

therefore -n < ($a$ mod n-$b$ mod n) < n

therefore ($a$ mod n-$b$ mod n) must equal zero

-
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