If $a = b \pmod m$ then $ka = kb\pmod m$, but if $ka = kb\pmod m$ and $\gcd(k, m) = 1$ then $a = b \pmod m$

Question

If $a = b \pmod m$ then $ka = kb\pmod m$, but if $ka = kb\pmod m$ and $\gcd(k, m) = 1$ then $a = b \pmod m$.

Why do we need the extra gcd part in the second claim?

Answer 1

Specifically, let's look at a counterexample. Consider $k=5$, $m=10$, $a=4$, and $b=2$. It should be obvious that:

$ka = kb \pmod{m}$ since $5\cdot 4 = 5 \cdot 2 = 0 \pmod{10}$.

We wouldn't think that $4 = 2 \pmod{10}$ however.

More generally, the problem is that $a = b \pmod{m}$ is one reason that $ka = kb \pmod{m}$ could happen, but $\text{gcd(}k,m)>1$ is another reason $ka = kb \pmod{m}$ could happen. When going backwards, it is necessary to rule out $\text{gcd(}k,m)>1$ to proceed.