Past exam of the mathematics course of the University of Cambridge / 2012 / ia / Paper 4 / 1D / i / Solution

Use the Euclidean algorithm: $23=18+5$, $18=3\cdot 5+3$, $5=3+2$, and $3=2+1$. Back-substitution gives the Bezout identity $1=9\cdot 18-7\cdot 23$. Multiplying by $101$ gives one solution of the linear Diophantine equation, and shifting the coefficients by multiples of $(23,-18)$ reduces it toIndeed, $18\cdot 12+23(-5)=216-115=101$. More generally all solutions are $x=12+23k$, $y=-5-18k$, $k\in \mathbb{Z}$: subtracting this particular solution gives $18(x-12)=-23(y+5)$, and the coprime integers $18,23$ force $23\mid (x-12)$.