Cancellation in congruences

Statement

Let $n$ be a positive integer, and let $a$, $b$ and $c$ be integers. Let $d = \gcd(c, n)$. If $c a \equiv c b \pmod n$, then $a \equiv b \pmod{n / d}$.

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

Explanations

L1 human

You can divide both sides of a congruence by a number that has no common factor with the modulus. If the number shares a factor with the modulus, you must also divide the modulus by that common factor.