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

Question

I came across this theorem:

For all integers a,b,c and m>0, if d = GCD(c,m) then a*c ≡ b*c (mod m) iff a ≡ b (mod m/d).

The =>proof states this:

a*c ≡ b*c (mod m) => m|(a-b)*c 
                  => m/d | (a-b)*c/d
                  => m/d | (a-b)
                  => a ≡ b (mod m/d)

I don't understand how to go from step 2 to step 3. The proof states that this is possible because m/d and c/d are coprime. To me this means GCD(m/d, c/d) = 1 but how does this cancel out the whole term?

Answer 1

If $\frac{m}{d} | (a-b)\frac{c}{d}$ and $GCD(\frac{m}{d}, \frac{c}{d}) = 1$, then $\frac{m}{d}$ must divide $a-b$, because $\frac{m}{d}$ and $\frac{c}{d}$ have no primes in common.

If you still don't have it clear, express $\frac{m}{d}$ and $\frac{c}{d}$ as a product of primes, and see that they can't have primes in common in their factorization, and therefore $\frac{m}{d}$ must divide $a-b$.

Answer 2

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