Need clarification on differences/products of Modular Arithmetic

Question

I am completing a discrete math assignment and noticed in my textbook a solution regarding modular arithmetic and the Pigeonhole Principle:

Using the Pigeonhole Principle, show that in every set of 100 integers, there exist two whose difference is a multiple of 37.

Since there are 100 pigeons and only 37 pigeonholes, two pigeons must go in the same pigeonhole. This means k1 rem 37 = k2 rem 37, which implies that k1 − k2 is a multiple of 37.

Now for my questions. How does the mod and rem function differ?

Can someone clarify how two integers with the same remainder of another integer implies that the difference will be a multiple?

In other words, suppose we have $a,b,c \in Z$. How does $a \mod c = b\mod c$ imply $a-b$ is a multiple of $c$?

I feel like this is some elementary principle/theorem that is not coming to me at the moment. Any help would be appreciated.

Answer 1

$a\equiv b\pmod c$ means that there is some integer $n$ such that $a=nc+b$. If also $d\equiv b \pmod c$, then there is some integer $m$ such that $d=mc+b$. Now, $$a-d = nc+b -(mc+b) = nc-mc =(n-m)c$$ and we see that $a-d$ is a multiple of $c$.

Answer 2

$\mod{}$ is not actually a function.

The easiest way to learn and understand what $42 \equiv 79\pmod {37}$ means is that $42$ and $79$ have the same remainder when divided by $37$. And $42 = 1\cdot 37 + 5$ and $79 = 2\cdot 37 + 5$ that is certainly true.

However the technical definition of $a\equiv b \pmod n$ is that $n$ divides into $a-b$ and so $42\equiv 79 \pmod {37}$ means $37$ divides into $42-79$. And as $42-79 = -37$ that is also certainly true.

These two definitions are exactly this same.

.....

Every number can be written $a = m\cdot q + r$ where $r$ is the remainder and is between $0$ and $q$ (i.e. $0 \le r < q$).

So if $a = m\cdot q + r$ and $b = w\cdot q + r$ have the same remainder, then $a-b = (m\cdot q + r)-(w\cdot q +r) = q(m-w)$ so $q$ divides into $a-b$.

And if $q$ divides evenly into $a-b$, then if we let $a = m \cdot q + r$ and $b = w \cdot q+ s$, then $q$ divides evenly into $a-b = (m\cdot q + r) - (w\cdot q+s) = q(m-w) + (r-s)$. So $q$ divides evenly into $r-s$. But $0 \le r < q$ and $0 \le s < q$ so $-q < r-s < q$ and the only number between $-q$ and $q$ (NOT including $-q$ or $q$) that is divisible by $q$ is... $0$ [because $0 = 0\cdot q$]. So if $q|r-s$ and $r-s < q$ and $-q < r-s$ the only way that is possible is if $r-s=0$ or in other words if $r =s$. So in other words.... $a$ and $b$ have the same remainder.