proof writing - If $ac≡bc$ $mod m$ and $gcd(c,m)=d$, show that $a≡b$ $mod frac{m}{d}$

How would you show that if $ac≡bc$ $\mod m$ and $\gcd(c,m)=d$, then $a≡b$ $\mod \frac{m}{d}$?

Any help would be much appreciated!

Answer

You have marked this under proof writing. So I will attempt a model proof.

So $ac \equiv bc \mod m$, which means that $m | ac-bc$, and hence $m | c(a-b)$. Hence, $c(a-b)=km$ for some integer $k$. Now, Given that $\gcd(c,m) =d$, it follows that $c=xd$ and $m=yd$ for some co-prime integers $x$ and $y$. Hence,
$$c(a-b) = km \implies xd(a-b) = kyd \implies x(a-b) = ky$$
Note that $x | ky$ from the above. Now, because $x$ is co-prime to $y$, it follows that $x |k$ and hence $\frac{k}{x}$ is an integer. Now, $$(a-b) = \frac{k}{x}y$$
and hence $a-b$ is a multiple of $y$. Hence $a \equiv b \mod y$. But $y = \frac{m}{d}$, hence $a \equiv b \mod \dfrac{m}{d}$.