 Solution

ID: 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/i/solution

91 = 3 \cdot 26 + 13, 26 = 2 \cdot 13,

g cd (754, 91) = g cd (26, 91) = 13

. Since

13 ∣ 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,

754 \cdot 5 + 91 (- 47) = - 507.

Thus $x = 5$ is a solution, with an explicit Bézout coefficient certificate.

 New to topics? Read the docs here!