# 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.