2
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Are you asking why $\ a\equiv b\pmod{\!n} \iff (a\bmod n) = (b\bmod n),\,$ or something else? $\endgroup$
    – Bill Dubuque
    Commented Apr 17, 2019 at 16:46
  • $\begingroup$ Hiow can I understand why the first definition is true in terms of remainders? $\endgroup$
    – Robin Andrews
    Commented Apr 17, 2019 at 16:55
  • 1
    $\begingroup$ $a\equiv b\pmod n\!\!\overset{\rm\ def}\iff n\mid a-b\iff (a-b)\bmod n = 0\ \ $ $\endgroup$
    – Bill Dubuque
    Commented Apr 17, 2019 at 17:02
  • 1
    $\begingroup$ Recall that $\ c\bmod n\ $ is the remainder left when dividing $\,c\,$ by $\,n.\ \ $ $\endgroup$
    – Bill Dubuque
    Commented Apr 17, 2019 at 17:07

2 Answers 2

Reset to default
2
$\begingroup$

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$

$\endgroup$
7
  • $\begingroup$ Is that the answer to my question though? "You are wishing to prove in your question that a≡b(modn) is true if and only if the remainders for a and b with respect to n are the same." Rather than "m|(a-b) is true if and only if the remainders for a and b with respect to n are the same". It may seem obvious that they are the same thing, but not to me, yet... $\endgroup$
    – Robin Andrews
    Commented Apr 17, 2019 at 19:33
  • $\begingroup$ @Robin $a\equiv b\pmod{n}$ is true if and only if $(a-b)$ is a multiple of $n$ by definition. Also by definition $(a-b)$ is a multiple of $n$ if and only if $n\mid (a-b)$. $\endgroup$
    – JMoravitz
    Commented Apr 17, 2019 at 19:52
  • $\begingroup$ (a−b) is a multiple of n if and only if n∣(a−b) is obvious. a≡b(modn) is true if and only if (a−b) is a multiple of n not so much, to me. As per my question, how does a statement about the individual divisibility of two numbers automatically imply something about the divisibility of their difference? There seems to be a missing step which is taken for granted but could be made explicit. $\endgroup$
    – Robin Andrews
    Commented Apr 17, 2019 at 20:00
  • 2
    $\begingroup$ The definition of what it means to say $a\equiv b\pmod{n}$ is that $(a-b)$ is a multiple of $n$. There is nothing to prove here. That is how it is defined. $\endgroup$
    – JMoravitz
    Commented Apr 17, 2019 at 20:02
  • 1
    $\begingroup$ "But it can also be defined in another way... How are these two definitions equivalent?" The proof in my post shows why $(a-b)$ is a multiple of $n$ is equivalent to $a$ and $b$ having the same remainders when divided by $n$. It follows then that whether you define $a\equiv b\pmod{n}$ to be the meaning on the left or whether you define it to be the meaning on the right, by transitivity the definitions are equivalent because the options of what you had to define them as are equivalent. $\endgroup$
    – JMoravitz
    Commented Apr 17, 2019 at 20:06
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .