I am studying for a Number Theory exam and this is one of the problems regarding congruence:
Prove that if ca ≡ cb (mod n), then a ≡ b (mod n/d), where d =gcd(c, n).
I am at a complete loss as to how to tackle this proof, and proofs have always been my weaker suit. Any help would be appreciated.
Back to basics. We have $c=c'd$ and $n=n'd$ with integers $c',n'$ such that $\gcd (n', c')=1.$ We have $\frac {ca-cb}{n}\in \Bbb Z$. So we have $$\frac {c'(a-b)}{n'}=\frac {c'da-c'db}{n'd}=\frac {ca-cb}{n}\in \Bbb Z.$$ So $n'|c'(a-b)$ and $\gcd (n',c')=1,$ which implies $n'|(a-b).$
In other words $a\equiv b \pmod {n'}$ and $n'=n/d.$