Cancellation in congruences

Remarks

In particular, if $c$ and $n$ are coprime, then $c a \equiv c b \pmod n$ implies $a \equiv b \pmod n$. The modulus can become smaller. For example, $2 \cdot 1 \equiv 2 \cdot 4 \pmod 6$, but $1 \not\equiv 4 \pmod 6$. Here $d = 2$, and indeed $1 \equiv 4 \pmod 3$. The proof: $n \mid c (a - b)$ gives $\frac{n}{d} \mid \frac{c}{d} (a - b)$. Since $n / d$ and $c / d$ are coprime, the generalized Euclid's lemma gives $\frac{n}{d} \mid a - b$.