# Proof of $a \equiv b$ mod m => $a \equiv b$ mod $m'$ with $d \cdot m' = m$

Let $$a,b \in \mathbb{Z}$$ and $$m, m', d \in \mathbb{N}$$ with $$d \cdot m' = m$$.

How can I prove/disprove that

$$a \equiv b$$ mod m => $$a \equiv b$$ mod $$m'$$?

and

$$a \equiv b$$ mod $$m'$$ => $$a \equiv b$$ mod m

For the first statement, can I for example say

$$27 \equiv 7$$ mod $$10$$ => $$27 \equiv 7$$ mod $$5$$ and $$27 \equiv 7$$ mod $$2$$?

I don't really understand, because for the first statement, it's the same like $$a \equiv b$$ mod m => $$a \equiv b$$ mod $$\frac{m}{d}$$. But what actually is d?

• Hint: divisibility is transitive – JavaMan Oct 29 '18 at 19:36

The first statement is true:

$$a \equiv b \bmod m \implies \\ a=mx+k, \space b=my+k\implies \\ a=m'dx+k, \space b=m'dy+k\implies \\ a=m'(dx)+k, \space b=m'(dy)+k\implies \\ a\equiv b \bmod m'$$

The second statement can be disproved with a single example:

Say $$m'=5$$, $$d=2$$, $$m=m'd=10$$, $$a=12$$, $$b=7$$:

Obviously: $$a\equiv b \bmod m'$$ because $$12\equiv7\bmod 5$$. But it is not true that $$a\equiv b \bmod m$$ because $$12\not\equiv 7\bmod 10$$.

By definition $$a\equiv b \mod m \iff \exists k\in\mathbb{Z}: a = mk+b$$ Using $$m = dm'$$ we get $$a = dm'k+b = (dk)m'+b$$ where $$kd\in\mathbb{Z}$$ and thus $$a\equiv b \mod m'$$

For the second statement, try to find a counterexample (actually, there are a lot).