Example

Prove that if $ac \equiv bc \pmod{m}$ and $\gcd(c,m)=1$, then $a \equiv b \pmod{m}$.


Turning the given congruence into a statement about divisibility, we have: $$\begin{align} ac \equiv bc \pmod{m} &\Rightarrow m \mid bc - ac\\ &\Rightarrow m \mid c \cdot (b-a)\\ &\Rightarrow m \mid b-a \quad \textrm{ ...as $m$ and $c$ are relatively prime}\\ &\Rightarrow b \equiv a \pmod{m} \end{align}$$ QED.