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

  • $\begingroup$ Thank you! But it just showcases my inability to understand this concept haha. :( $\endgroup$ – 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$.


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


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

  • $\begingroup$ How did you get that $a \mod n=a-pn$? I don't recall that at all.. Pardon me. $\endgroup$ – Yellow Skies Nov 12 '12 at 1:37
  • $\begingroup$ 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 $\endgroup$ – Amr Nov 12 '12 at 1:44
  • $\begingroup$ 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 $\endgroup$ – Amr Nov 12 '12 at 1:45
  • $\begingroup$ I see! Thankszz $\endgroup$ – Yellow Skies Nov 12 '12 at 1:52
  • $\begingroup$ @Amr I edited the answer a little. Of course you can revert it or modify it if you prefer. $\endgroup$ – Bill Dubuque Jul 11 '16 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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