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

The greatest common divisor of positive integers $a,b$ is the largest positive integer dividing both, denoted $\gcd (a,b)$. The set of positive common divisors contains $1$ and is finite, so this definition supplies a value.

The Euclidean algorithm repeatedly replaces $(r_{i-1},r_i)$ by $(r_i,r_{i-1}-q_i{r}_i)$, where the new remainder lies between $0$ and $r_i-1$. Common divisors are unchanged by this subtraction, and decreasing positive remainders ensure termination. The last nonzero remainder is the greatest common divisor.

The extended Euclidean algorithm also tracks coefficients $r_i=u_{i}a+v_{i}b$, beginning with coefficient pairs $(1,0)$ and $(0,1)$ and applying the same subtraction to the pairs. This invariant produces Bézout coefficients for the last nonzero remainder. Here the divisions areBack substitution givesThus $\gcd (580,252)=4$, with $m=10$ and $n=-23$ in Bézout's identity.