# Prove that if $a\equiv b \pmod m$ , then $a \bmod m = b \bmod m$

## Question

Prove that if $a\equiv b \pmod m$ , then
$a \bmod m = b \bmod m$

## Approach

Given,

$a\equiv b \pmod m$

$\implies m\mid (a-b)$

$\implies (a-b)=m\cdot k$

$\implies a=b+m\cdot k$

Now,

$a \bmod m$ can be written as

$\implies b+m\cdot k \pmod m$

No idea how to move forward to get

$$b \pmod m \impliedby b +m\cdot k \pmod m$$

Thanks!

#### Solutions Collecting From Web of "Prove that if $a\equiv b \pmod m$ , then $a \bmod m = b \bmod m$"

$$a\equiv b \pmod m$$
$$\implies (a-b) = m k$$
$$\implies a = m k + b$$
$$\implies a \bmod m = (mk\bmod m + b\bmod m)\bmod m = b\bmod m \bmod m = b \bmod m$$
$$\implies a \bmod m = b \bmod m$$

Here is an important point raised by @(Bill Dubuque) in this proof. In line $4$, I used $(mk+b)\bmod m = (mk\bmod m + b\bmod m)\bmod m$ which must be proved for the completion of the proof of the original result. There are multiple ways to prove this equality, however if one uses the approach used in this answer, then this leads to a circular dependency i.e. usage of this equality to prove the original result and the usage of the original result in proving this equality. So, to complete the proof of original result one must prove this equality with some other approach. Based on the suggestion by Bill, here is a revised proof,

Let $b = mq + r \implies b \bmod m = r$, then,

$$a\equiv b \pmod m$$
$$\implies (a-b) = m k$$
$$\implies a = m k + b = mk + mq + r = m(k+q) + r$$
$$\implies a \bmod m = r = b \bmod m$$
$$\implies a \bmod m = b \bmod m$$

Note:
Here is an issues found by @(Bill Dubuque) in my first proof.

$$a\equiv b \pmod m$$
$$\implies (a-b) = m k$$
$$\implies (a-b)\bmod m = m k \bmod m$$
$$\implies a \bmod m – b \bmod m = 0$$
$$\implies a \bmod m = b \bmod m$$

But the $4$th equation above cannot follow from the $3$rd equation in general (counterexample $a=m$ and $b=1$).

Hint $\,$ Show $\ c\equiv d\pmod{\!m}\,$ and $\,|c-d|<m\,\Rightarrow\, c= d$

Apply that to $\,\ \underbrace{a\bmod m}_{\Large c}\!\equiv a\equiv b\equiv \underbrace{b\bmod m}_{\Large d}\,\ \pmod{\!m}$

Remark  Any sequence of $m$ consecutive integers forms a complete system $S$ of representatives (normal forms) of all equivalence classes mod $m,\,$ so the above implies that congruence reduces to equality on these normal forms, i.e. $\ a\equiv b\iff \bar a = \bar b,\,$ where $\bar n =$ unique normal-form rep in $S$ congruent to $n\,$ (which is analogous to:  fractions are equivalent iff their least form rep’s are equal, i.e. least terms fractions are normal forms for equivalence of fractions).

An alternative convenient choice of normal forms for modular arithmetic arises by choosing the least magnitude reps (signed or balanced residue system), e.g. $\,\{-2,\color{#c00}{-1},0,1,2\}\pmod{\! 5}.\,$ In these signed systems the normal form of $\,m\!-\!1\,$ is $\,-1,\,$ e.g. above $\,4\equiv\color{#c00}{-1}\pmod{\!5},\,$ simplifying common calculations such as $\,(m\!-\!1)^k\equiv (-1)^k,\,$ e.g. when casting out elevens.

The phrase $a \mod m$ as some specific numerical value is not a universally understood or accepted concept and so the phrase $a \mod m = b\mod m$ may not have any sensible meaning depending on which mathematician you ask.

It can be taken to mean: For any $m \in \mathbb N$ (not including 0) and any integer $a$ there will exist unique integers $q, r$ so that $a = qm + r$ and $0 \le r < m$. We define $r$ as the remainder where $a$ is divided by $m$.

I have seen this called $r = a \mod m$ or more commonly $r = a \% m$. In my opinion, I can accept the latter if it is properly defined but I detest the former as it is an abuse of notation and concept.

The notation $a \equiv b \mod m$ means $m$ divides $a- b$ or equivalently $a$ and $b$ have the same remainder when divided by $m$. But the important thing is that this is not a statement about specific integers– it is a statement about equivalence classes of sets of integers. $a \equiv b \mod m$ mean that both $a$ and $b$ are elements of the the same set $M = \{ x\in \mathbb Z| m|(x-a)\}$.

Anyway. Assuming that you mean $a \mod m$ to mean the unique integer remainder as I desribed in the second paragraph then the proof is trivial:

Suppose $a \equiv b \mod m$ Let $r_1 = a \mod m$ so $a = jm + r_1$ or $r_1 = a = jm$ for some integer $j$ and let $r_2 = b \mod m$ so $b = lm + r_2$ o $r_2 = b- lm$ and $0 \le r_1 < m; 0 \le r_2 < m$. So $r_1 – r_2= (a-b) + (j- l)m$ So as $m|(a-b)$ and $m|(j-l)n$ then $m|r_1 – r_2$.

Let $r_1 – r_2 = dm$ for some integer $d$.

then $m > r_1 > r_1 – r_2 = dm$ and $dm = r_1 – r_2 > -r_2 > m$ so $m > dm > -m$ and $1 > d > -1$ but $d$ is an integer.

So $d= 0$ and $r_1 – r_2 = 0*m = 0$ and $a \mod m = r_1 = r_2 = b \mod m$.

Write $a=qm+r$ and $b=pm+s$, where $0\leq s,r<m$.
Then $a\;\underline{mod}\;m = r$ and $b\;\underline{mod}\;m = s$. On the other hand, $a\equiv b\; mod \;m$ iff $m|a-b$ iff (above) $m|r-s$ iff ($r,s$ remainders) $r=s$.

I think it’s obvious:

You have that $a \equiv b+mk \pmod m$.

But, $mk \equiv 0 \pmod m$ , so $a \equiv b+mk \equiv b\pmod m$.

Done.