Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
+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
up vote 3 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer

$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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.