$\ ac≡bc\pmod{\! m}\!\iff\! a≡b\pmod {\!m/d},\ d = \gcd(c,m)\ $ [Congruence Cancellation & Division Rule]

How would you show that if $ac≡bc$ $\mod m$ and $\gcd(c,m)=d$, then $a≡b$ $\mod \frac{m}{d}$?

Any help would be much appreciated!

Solution 1:

You have marked this under proof writing. So I will attempt a model proof.

So $ac \equiv bc \mod m$, which means that $m | ac-bc$, and hence $m | c(a-b)$. Hence, $c(a-b)=km$ for some integer $k$. Now, Given that $\gcd(c,m) =d $, it follows that $c=xd$ and $m=yd$ for some co-prime integers $x$ and $y$. Hence, $$ c(a-b) = km \implies xd(a-b) = kyd \implies x(a-b) = ky $$ Note that $x | ky$ from the above. Now, because $x$ is co-prime to $y$, it follows that $x |k$ and hence $\frac{k}{x}$ is an integer. Now, $$ (a-b) = \frac{k}{x}y $$ and hence $a-b$ is a multiple of $y$. Hence $a \equiv b \mod y$. But $y = \frac{m}{d}$, hence $a \equiv b \mod \dfrac{m}{d}$.

Solution 2:

Assuming integers for all variables, and $c' = c/d$, $m' = m/d$ :

$$\begin{align} ac \equiv bc \pmod m &\iff \exists k ~~ ac - bc = km \\ % &\iff \exists k ~~ ac'd - bc'd \equiv km \\ % &\iff \exists k ~~ a - b \equiv (k/c')(m/d) \end{align}$$

So we have to establish that $k / c'$ is an integer. From $\gcd(c, m) = d$ we can infer $\gcd(c', m') = 1$, so

$$ac - bc = km$$ $$ac'd - bc'd \equiv k(m'd)$$ $$c'(a - b) = km'$$

So $c'$ divides $k$, so $k/c'$ is an integer.

$$\exists j ~ a - b = j(m/d)$$ $$a \equiv b \pmod {m/d}$$

Solution 3:

By definition $\ ac\equiv bc\pmod{\! m}\!\iff\! m\mid ac\!-\!bc = \color{#0a0}c\:\!(\overbrace{a\!-\!b}^{\textstyle \color{#0a0}n})\!\iff m/(m,c)\mid a\!-\!b,\,$ by

Theorem $ $ (general Euclid's Lemma) $\ \ \ m\mid \color{#0a0}{cn}\iff m/(m,c)\mid n \ \ $

Remark $ $ As is explained carefully here, in fraction language this can be written as

$$ ac\equiv bc\!\!\!\!\pmod{\!m}\iff a\equiv \dfrac{bc}c\!\!\!\!\pmod{\!m}\equiv\!\!\!\!\!\!\!\!\underbrace{\dfrac{bc/\color{#c00}d}{c/\color{#c00}d}\equiv b\!\!\!\pmod{\!m/\color{#c00}d}}_{\textstyle {\rm cancel}\ \color{#c00}d\!=\!(c,m)\,\ \color{#c00}{\rm everywhere}}\qquad\qquad$$

The common divisor $\,\color{#c00}d = (c,m)\,$ must be cancelled $\:\!\rm\color{#c00}{everywhere}\:\!$ (top, bottom and modulus), leaving the new denominator $\,c/d\,$ coprime to the new modulus $\,m/d,\,$ so invertible, so cancellable. Generally, the modular fraction $\,bc/c\bmod m$ exists $\!\iff d\,$ divides the top (numerator) - true here: $\,d\!=\!(c,m)\mid c\mid bc,\,$ but when $d>1$ the fraction is multi-valued $\!\bmod m,\,$ but single-valued $\!\bmod m/d,\,$ see the prior linked post for details.