Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

share|cite|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
up vote 4 down vote accepted

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

share|cite|improve this answer
    
I edited the answer a little. Of course you can revert it or modify it if you prefer. – Bill Dubuque Jul 11 at 20:26

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

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

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
    
@Amr I edited the answer a little. Of course you can revert it or modify it if you prefer. – Bill Dubuque Jul 11 at 20:14

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.