Past exam of the mathematics course of the University of Oxford / 2017 / Prelims / Mathematics IV / 7 / a / i / Solution

The euclidean algorithm computes the greatest common divisor of two integers by repeated division with remainder. Start with $r_0=|A|$, $r_1=|B|$, interchanging them if necessary, and repeatedly writeuntil a zero remainder occurs. The positive remainders strictly decrease, so the process terminates. At each step the common divisors of $r_{j-1},r_j$ are exactly the common divisors of $r_j,r_{j+1}$, because $r_{j+1}=r_{j-1}-q_j{r}_j$. HenceIf one input is zero, the answer is the absolute value of the other; the usual convention sets $\gcd (0,0)=0$. Back-substitution also expresses the greatest common divisor as an integer linear combination of the inputs, as in Bézout's identity.