Take the 2-minute tour ×
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.

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|improve this question
1  
+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
add comment

3 Answers

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|improve this answer
add comment

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|improve this answer
add comment

$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|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
add comment

Your Answer

 
discard

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.