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

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.

Apply the Euclidean algorithm to $19$ and $11$:Back-substitution gives the Bézout's identityThus $(x,y)=(-4,7)$ is one solution of the Diophantine equation. Subtracting this solution from any other givesSince $19$ and $11$ are coprime, $11$ divides $x+4$. To justify that step directly, multiply $1=-4\cdot 19+7\cdot 11$ by $x+4$: both terms on the right are divisible by $11$, because $19(x+4)=-11(y-7)$. Write $x+4=11t$; substitution then gives $y-7=-19t$. Therefore the complete solution set isEvery such pair satisfies the original Diophantine equation, since the $t$ terms cancel.

First recall why the two-variable Bézout's identity follows from the Euclidean algorithm. The initial values $a,b$ are integer linear combinations of $a,b$. At every subsequent step, $r_{j+1}=r_{j-1}-q_j{r}_j$ is again an integer linear combination of $a,b$. Therefore the last nonzero remainder, which is their greatest common divisor, has that form.

Put $e=\gcd (a,b)$. The preceding argument supplies integers $u,v$ with $e=au+bv$. Applying the same argument to $e,c$ gives integers $p,q$ such thatAn integer divides $a,b,c$ exactly when it divides $e,c$: if it divides $a,b$, it divides $e=au+bv$, while $e$ itself divides both $a,b$. Hence $\gcd (e,c)=\gcd (a,b,c)=d$. Substituting the expression for $e$ provesThusare integers satisfying $ax+by+cz=d$. This also explains how to construct the coefficients using two applications of the Euclidean algorithm.