Integer Congruence Explanation

Question

Edit: I don't think I've expressed myself very well. This is another way of putting my question.

We can say two integers, a and b, are congruent mod m (where m is a natural number) if both numbers divided by m produce the same remainder. In other words, m must evenly divide their difference, a - b

Now, why are the two statements equivalent? (Why can we say "in other words"?)

I.e.

How to prove

$m\mid (a-b) \iff$ $a/m$ and $b/m$ have the same remainder

*** Original question below.

I understand that one definition of integer congruence is:

For a positive integer n, two numbers a and b are said to be congruent modulo n, if their difference a − b is an integer multiple of n

I also understand that the modulus operation (for mod n) can be seen as the remainder on division by n.

What I can't see is how these two concepts relate. Could someone please explain (perhaps using a number line) why the first definition holds?

Answer 1

The quotient remainder theorem (a consequence of Euclidean Division) states that for two integers $a,n$ with $n\neq 0$ there exists a unique pair of integers $q,r$ with $0\leq r<n$ called the "quotient" and the "remainder" respectively such that $a = nq+r$.

You are wishing to prove in your question that $a \equiv b\pmod{n}$ is true if and only if the remainders for $a$ and $b$ with respect to $n$ are the same.

Suppose that $a = nq + r$ and that $b = nq'+r'$. (The apostrophe here merely means that $q$ and $q'$ could potentially be different values.) If we were to suppose that $r\neq r'$ and if we were to assume without loss of generality that $r>r'$ then we have $0\leq r' < r < n$ and as a result $1<r-r'<n$. We have then $a - b = n(q-q') + (r-r')$. It follows then that $(a-b)$ is then not a multiple of $n$ since $(r-r')$ is nonzero and is the unique remainder of $(a-b)$ with respect to $n$ and therefore $a\not\equiv b\pmod{n}$. This proves by contraposition that $a\equiv b\pmod{n}\implies a$ and $b$ have the same remainder with respect to $n$.

Now, suppose instead that $r=r'$. Then $a-b = n(q-q')+(r-r')=n(q-q')+0$ and so $a-b$ is a multiple of $n$ and therefore $a\equiv b\pmod{n}$

$\square$

Answer 2

Okay so $$a-b=mx\implies a=mx+b$$ Now assume for a minute, $b>m$ and let $r<m$ be b's remainder on division by m, k it's integer quotient with m. We now have via substitution :$$a=mx+mk+r$$ regrouping the parts with m, we get $$a=m(x+k)+r$$ or by the first definition r is congruent to a mod m, because they are different by a multiple of m. Therefore, r is the remainder of both b and a, on division by m. They share the same remainder.