5
$\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
    How did you get that $a \mod n=a-pn$? I don't recall that at all.. Pardon me.2012-11-12
  • 0
    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 numbers2012-11-12
  • 0
    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−pn2012-11-12
  • 0
    I see! Thankszz2012-11-12
  • 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$.