Past exam of the mathematics course of the University of Cambridge / 2012 / ia / Paper 4 / 1D (Numbers and Sets)

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)$.

Write $x=3+18k$. The second modular congruence becomes $18k\equiv -1(\mathrm{mod}23)$. The Bezout identity above says that $9$ is the inverse of $18$ modulo $23$, so $k\equiv -9\equiv 14(\mathrm{mod}23)$. ThereforeThe checks are $255=18\cdot 14+3=23\cdot 11+2$. The Chinese remainder theorem explains uniqueness modulo $18\cdot 23=414$, since the moduli are coprime integers.