Past exam of the mathematics course of the University of Oxford / 2015 / Prelims / Mathematics IV / 6 / a

The divisions in the Euclidean algorithm areThe last nonzero remainder is $17$, soAs a check, $323=19\cdot 17$ and $187=11\cdot 17$; back-substitution also gives $17=-4\cdot 323+7\cdot 187$.

At any division step $u=qv+r$, an integer divides both $u,v$ exactly when it divides both $v,r$: one direction uses $r=u-qv$, and the other uses $u=qv+r$. HenceStarting with $r_0=a$, $r_1=b$, the Euclidean division producesThe nonzero remainders form a strictly decreasing sequence of positive integers. Such a sequence must terminate, since there are only finitely many positive integers below $b$. Suppose $r_N$ is the last nonzero remainder, so $r_{N+1}=0$. The unchanged greatest common divisor at each step givesThe final equality holds because the positive common divisors of $r_N$ and $0$ are precisely the positive divisors of $r_N$. This proves both termination and correctness of the Euclidean algorithm.