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

Reduction of both coefficients in modular arithmetic givesMore explicitly,The first expression is divisible by $91$ exactly when the last parenthesis is. By the definition of a integer congruence, the two congruences are equivalent.

The Euclidean algorithm givesso $\gcd (754,91)=\gcd (26,91)=13$. Since $13\mid 39$, the criterion for a linear congruence guarantees a solution. One can also exhibit it directly: $26\cdot 5+91(-1)=39$, or in the original coefficients,Thus $x=5$ is a solution, with an explicit Bézout coefficient certificate.

Divide the divisibility relation $91\mid 26x-39$ by $13$ to obtain $7\mid 2x-3$. Since $2\cdot 4\equiv 1(\mathrm{mod}7)$, multiplication by the modular multiplicative inverse gives $x\equiv 12\equiv 5(\mathrm{mod}7)$. Therefore all integer solutions are $x=5+7q$, $q\in \mathbb{Z}$.

Modulo $91=13\cdot 7$, the choices $q=0,\dots ,12$ giveThey are distinct residue classes: equality of two such classes would imply $91\mid 7(q-q^{\prime })$, hence $13\mid q-q^{\prime }$. Every integer $q$ is congruent to one of those thirteen choices, so the list is exhaustive.

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.