Past exam of the mathematics course of the University of Cambridge / 2021 / ia / Paper 4 / 6E / a

The Euclidean algorithm repeatedly replaces a pair $(a,b)$ by $(b,a-qb)$ without changing its greatest common divisor. Reversing the divisions expresses $\gcd (a,b)$ as an integer linear combination $\alpha a+\beta b$, which is Bézout's identity.

Here $3=3(15)-2(21)$, and thereforeOne solution is $(x,y,z)=(36,-24,-1)$. It is not unique: for every $t\in \mathbb{Z}$, $(x,y,z)=(36+7t,-24-5t,-1)$ is another solution.

Because $\gcd (m,n)=1$, choose $u,v\in \mathbb{Z}$ with $um+vn=1$ by Bézout's identity. Thensatisfies $c\equiv a(\mathrm{mod}m)$ and $c\equiv b(\mathrm{mod}n)$. Any two simultaneous solutions differ by a multiple of both coprime integers and hence by a multiple of $mn$. This proves the two-modulus Chinese remainder theorem.

The three congruences reduce toThe first two give $x\equiv 17(\mathrm{mod}35)$; imposing the last gives