Cancellation of a common factor in a congruence ($ac\equiv bc(\mathrm{mod}n)⟺a\equiv b(\mathrm{mod}n/\gcd (c,n))$)

For integers $a,b$ and positive integers $c,n$, a common factor may be cancelled from a integer congruence provided the modulus is divided by the corresponding greatest common divisor. Let $d=\gcd (c,n)$, $c=d{c}^{\prime }$, and $n=d{n}^{\prime }$. The integers $c^{\prime },n^{\prime }$ are coprime: any common divisor greater than one would give a common divisor of $c,n$ larger than $d$.

By divisibility and Euclid's lemma,This proves the displayed equivalence. If $c$ is coprime to $n$, the modulus stays unchanged and this is ordinary cancellation by a modular multiplicative inverse. If $n\mid c$, the reduced modulus is $1$, so every pair $a,b$ satisfies the reduced integer congruence.