= Solution
Let $d=\gcd(c,n)$, $c=dc'$, and $n=dn'$. The preceding part gives $\gcd(c',n')=1$. The <integer congruence> on the left is equivalent to
$$
n\mid c(a-b)
\quad\Longleftrightarrow\quad
n'\mid c'(a-b).
$$
By <Euclid's lemma>, coprimality of $c'$ and $n'$ makes this equivalent to $n'\mid a-b$. The reverse implication is also immediate by multiplying a <divisibility> relation by $dc'$. Therefore
$$
\boxed{ac\equiv bc\pmod n
\quad\Longleftrightarrow\quad
a\equiv b\pmod{n/\gcd(c,n)}.}
$$
This is <cancellation of a common factor in a congruence>. The printed equality sign in the right-hand expression is interpreted as equality of <residue classes>, hence the displayed <integer congruence>. Ordinary equality of the <integers> $a,b$ would be false: the following example has $a\ne b$.
Back to article page
