Past exam of the mathematics course of the University of Cambridge / 2010 / ia / Paper 4 / 1E / b / Solution

The modular inverse of $2$ modulo $3$ is $2$, so the second modular congruence is $x\equiv 2(\mathrm{mod}3)$. The third means $10\mid 2(x-2)$, equivalently $5\mid x-2$. Cancelling this common factor changes the modulus; it gives $x\equiv 2(\mathrm{mod}5)$.

The first three conditions consequently combine to $x\equiv 2(\mathrm{mod}15)$ and $x$ odd, hence $x=17+30k$ for an integer $k$. The last condition becomesAs $30\cdot 38=17\cdot 67+1$, multiplying by the modular inverse $38$ gives $k\equiv 2(\mathrm{mod}67)$. ThusThe Chinese remainder theorem states that modular congruences with pairwise coprime moduli have a unique solution modulo their product. Here those moduli are $2,3,5,67$, with product $2010$. The derivation proves necessity, and substitution gives $77\equiv 1(\mathrm{mod}2)$, $2\cdot 77\equiv 1(\mathrm{mod}3)$, $2\cdot 77\equiv 4(\mathrm{mod}10)$ and $77\equiv 10(\mathrm{mod}67)$, proving sufficiency for the whole displayed class.