Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Discrete mathematics, continuous mathematics, and probability / 1 / c

Let $d=\gcd (c,n)$, and write $c=d{c}^{\prime }$, $n=d{n}^{\prime }$ with positive integers $c^{\prime },n^{\prime }$. If an integer $e>1$ divided both $c^{\prime }$ and $n^{\prime }$, then $de$ would divide both $c$ and $n$, contradicting the maximality of their greatest common divisor $d$. Thus $\gcd (c^{\prime },n^{\prime })=1$. Equivalently, Bézout's identity for $c,n$ can be divided by $d$ to express $1$ as an integer combination of $c^{\prime },n^{\prime }$.

Let $d=\gcd (c,n)$, $c=d{c}^{\prime }$, and $n=d{n}^{\prime }$. The preceding part gives $\gcd (c^{\prime },n^{\prime })=1$. The integer congruence on the left is equivalent toBy Euclid's lemma, coprimality of $c^{\prime }$ and $n^{\prime }$ makes this equivalent to $n^{\prime }\mid a-b$. The reverse implication is also immediate by multiplying a divisibility relation by $d{c}^{\prime }$. ThereforeThis 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$.

Take $(a,b,c,n)=(1,4,2,6)$. These are four distinct positive integers and $n\ge 3$. Their products are $ac=2$ and $bc=8$, whose difference is $6$, so $ac\equiv bc(\mathrm{mod}6)$. Here the correct reduced modulus is $6/\gcd (2,6)=3$, and indeed $1\equiv 4(\mathrm{mod}3)$. The example illustrates why cancelling a noninvertible factor may change the modulus in modular arithmetic.