Past exam of the mathematics course of the University of Oxford / 2021 / Prelims / Mathematics IV resit / 7 / b

The successive division with remainder steps of the Euclidean algorithm areEach step preserves the greatest common divisor by part (a). The final nonzero remainder is $9$, so

Back-substitute in the Euclidean algorithm to obtain an integer linear combination:Multiplying by $3$ gives the particular solution $(x_0,y_0)=(-45,21)$ of the linear Diophantine equation. Subtracting it from any other solution and dividing by $9$ givesThe integers $34$ and $73$ are coprime, so $73$ divides $x+45$. Writing $x+45=73t$ forces $y-21=-34t$. Conversely these expressions satisfy the original equation for every integer $t$. Thus all solutions of a linear Diophantine equation here are