# congruence proof

I am looking into congruences for school and I have trouble understanding on how to prove this (i understand modules, congruences but don't know how to prove it).

I need to prove that if this congruence is true:

$$a c \equiv b c \pmod m$$

then also this holds:

$$a \equiv b \pmod{m/\gcd(c,m)}$$

Can some one please explain or give a hint how I can prove this? I have tried googling but all the proofs I have found are without a good explanation to help me understand it.

Thanks!

-

Let $d=\operatorname{gcd}(c,m)$, write $m=d\cdot m'$, $c=d\cdot c'$. You are given that $a\cdot c-b\cdot c=k\cdot m$ for some $k\in\mathbb Z$. It follows that $a\cdot d\cdot c'-b\cdot d\cdot c'=k\cdot d\cdot m'$, hence $a\cdot c'-b\cdot c'=k\cdot m'$, so at least $a\cdot c'\equiv b\cdot c'\pmod{m'}$. But now $c'$ and $m'$ are relatively prime! Does that help in showing $a\equiv b\pmod {m'}$?
Hint  Let $\rm\ d=(m,c).\,$ $\rm\,m\:|\:c(a\!-\!b)\!\!\iff\! \!\frac{m}d|\frac{c}d(a\!-\!b)\!\!\color{#C00}{\iff}\!\! \frac{m}d|\:a\!-b\,\:$ by $\rm\ (\frac{m}d,\frac{c}d)= \frac{(m,c)}d = 1$
Remark $\$ The $\rm\color{#C00}{final}\,$ equivalence employs Euclid's Lemma and the distributive law for GCDs.