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

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.