$ac\equiv bc \pmod{\!m}\!\!\iff\!\! a\equiv b \pmod{\!\!\frac{m}{(c,m)}}$ [Euclid's Lemma, congruence form]

Solution 1:

It is special case $\, x = a\!-\!b\,$ below $\, $ [general Euclid's Lemma]

Theorem $\, \ m\mid cx \iff\, \dfrac{m}{(m,c)}\ {\Large \mid}\ x.\ \ \,$ Proof $\,\ $ Let $\ d = (m,c).\ $ Then

we deduce $\, \ m\mid cx \overset{{\rm cancel}\ d\!\!}\iff\ \color{#c00}{\dfrac{m}d}\ {\Large \mid}\ \color{#c00}{\dfrac{c}d}\:x\!\!\overset{\rm(EL)\!}\iff\! \dfrac{m}d\ {\Large \mid}\ x\,\ $ by Euclid's Lemma (EL),

because: $\,\ (m,c) = d\ \Rightarrow\, \color{#c00}{\left(\dfrac{m}d,\,\dfrac{c}d\right)} = (m,c)/d = 1\ $ via GCD Distributive Law.

Or $\,\ m\mid cx\iff m\mid mx,cx\!\!\overset{\rm\color{#0a0}{U}\!}\iff m\mid (mx,cx)\overset{\rm\color{#90f}{D}}=(m,c)x\iff m/(m,c)\mid x$

where we employed $\,\rm\color{#0a0}{U} =\,$ gcd Universal Property and $\,\rm\color{#90f}{D} = \,$gcd Distributive Law