Prove ca ≡ cb (mod m) if and only if a ≡ b mod (m/gcd(c, m) ) I can't seem to answer this question without assuming that gcd(c,m) = 1. Is the question missing any information?
Let $g=\gcd(c,m)$ and write $c=gd$, $m=gn$.  Then $\gcd(d,n)=1$, because otherwise $g$ would not be the greatest common divisor of $c$ and $n$.  Therefore
$$\eqalign{
  ca\equiv cb\pmod m
  &amp;\iff m\mid ca-cb\cr
  &amp;\iff gn\mid gd(a-b)\cr
  &amp;\iff n\mid d(a-b)\cr
  &amp;\iff n\mid a-b\cr
  &amp;\iff a\equiv b\ \Bigl({\rm mod}\frac{m}{\gcd(c,m)}\Bigr)\ .\cr}$$
Note that the second last step is true because $\gcd(d,n)=1$.
Let $\,d=a\!-\!b.\,\ m\mid cd\iff m\mid cd,md\!\!\overset{\large\ \ (1)}\iff m\mid (cd,md) = (c,m)d\iff m/(c,m)\mid d$

where in $(1)$ we used the GCD Universal Property and the GCD Distributive Law