$\ 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!
 A: 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}$.
A: 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}$$
A: 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.
A: Likely clearer in two steps: $ $ first cancel $\,d = (c,m)\,$ $\rm\color{#c00}{everywhere}$ to reduce to the case of $\rm\color{#0a0}{coprime}$ $\,\bar c,\bar m = c/d, m/d,\,$ then cancel $\,\bar c\,$ by scaling by $\,\bar c^{-1}$ (exists $\!\bmod \bar m$ by $\,\bar c\,$ $\rm\color{#0a0}{coprime}$ to $\,\bar m)$
$$\begin{align}  
ac &\equiv bc\!\!\pmod{m}\\
\overset{\bf L1\!}\iff\ \ a\bar c&\equiv b\bar c\!\!\!\pmod{\bar m}\ \ \ {\rm via\ cancel\ } d = (c,m)\ \,\&\,\ \rm L1\ below\\
\iff\ \ \ \ a &\equiv b\pmod{\bar m}\  {\rm\ \ by\ scaling\ by\ }\, \bar c^{-1}
\end{align}$$
$\rm\bf L1$ $ $ If $\, d\mid c,m\!:\ ac\equiv bc\pmod{\!m}\!\!\iff\! {ac/\color{#c00}d \equiv bc/\color{#c00}d\pmod{\!m/\color{#c00}d}}\ $ [cancel $\,d\ \rm\color{#c00}{everywhere}$]
$\!\begin{align}{\bf Proof}\qquad\qquad\! \exists\:\! k\!:\quad\  ac &= bc + km\\[.2em]
\iff \exists\:\! k\!:\  ac/d &= bc/d \,+\, k\:m/d,\ \ \text{via cancel $\,d$}\\[.2em] 
\iff\qquad ac/d &\equiv bc/d\!\!\!\pmod{\!m/d} \\[.2em]
{\rm i.e.}\ \ \ \ \ \ a\bar c\, &\equiv\, b\bar c\,\pmod{\!\bar m}\end{align}$
Remark $\ $ The (two-step) cancellation has a natural view as modular fraction reduction as explained in the remark in my other answer here.
A: By definition, $ac\equiv bc \pmod{m}$ means that there exists a $k\in\mathbb{Z}$ such that $ac=bc+km$. If $d=\gcd(c,m)$, let $c=sd$ and $m=td$ (note now that $\gcd(s,t)=1$). This means that
$$
\begin{aligned}
ac &\equiv bc \pmod{m} \Longleftrightarrow \\
ac &= bc+km \Longleftrightarrow \\
asd &= bsd+ktd \Longleftrightarrow \\
as &= bs+kt,
\end{aligned}
$$
so $as\equiv bs \pmod{t}$, or in other words $as\equiv bs \pmod{m/d}$. But since $\gcd(s,t)=1$ we can conclude that $a\equiv b \pmod{m/d}$, and we are done.
A: Theorem.
$$\forall a, b, c \in \mathbf{Z}, n \in \mathbf{Z}^*, \quad ac \equiv bc \pmod n \iff a \equiv b \pmod{\tfrac{n}{\gcd(c, n)}}.$$
Proof. Let $a, b, c \in \mathbf{Z}, n \in \mathbf{Z}^*$.
$$
\begin{align}
  ac \equiv bc \pmod n & \iff \exists k \in \mathbf{Z}, ac - bc = kn \\
                       & \iff \exists k \in \mathbf{Z}, (a - b)c = kn \\
                       & \iff \exists k \in \mathbf{Z}, (a - b) \frac{c}{\gcd(c, n)} = k\frac{n}{\gcd(c, n)}.
\end{align}
$$
Therefore, $\frac{c}{\gcd(c, n)}$ divides $k\frac{n}{\gcd(c, n)}$, and since $\frac{c}{\gcd(c, n)}$ is coprime to $\frac{n}{\gcd(c, n)}$, it follows from Euclid’s lemma that $\frac{c}{\gcd(c, n)}$ divides $k$, hence
$$
\begin{align}
  ac \equiv bc \pmod n & \iff \exists k \in \mathbf{Z}, a - b = \frac{k}{\frac{c}{\gcd(c, n)}} \frac{n}{\gcd(c, n)} \\
                       & \iff \exists l \in \mathbf{Z}, a - b = l \frac{n}{\gcd(c, n)} \\
                       & \iff a \equiv b \pmod{\tfrac{n}{\gcd(c, n)}}. & \blacksquare
\end{align}
$$
