Proof that if ax ≡ bx (mod m) and gcd(x, m) = 1, then a ≡ b (mod m)

If $ax ≡ bx \bmod m$:

$$\begin{gathered} m \mid (ax-bx) \\ m \mid x(a-b) \end{gathered}$$

If $gcd(x, m) = 1$:

$$\begin{gathered}1 = j(x) + k(m) \quad (where \ j, k \in ℤ)\\ (a-b) = j(a-b)(x) + k(a-b)(m) \end{gathered}$$

Since $m \mid (a-b)(x)$ and $m \mid (a-b)(m)$, then:

$$\begin{gathered} m \mid j(a-b)(x) + k(a-b)(m) \\ m \mid (a-b) \end{gathered}$$

Therefore $a ≡ b \bmod m$.