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

The Wilson theorem says that $(p-1)!\equiv -1(\mathrm{mod}p)$ for a prime number $p$. Thus $18\cdot 17!\equiv -1(\mathrm{mod}19)$, and since $18\equiv -1$, we get $17!\equiv 1$. The Fermat little theorem says $b^{p-1}\equiv 1(\mathrm{mod}p)$ when $p$ does not divide $b$. Applying it to $3$ gives $3^{18}\equiv 1$, so $3^{16}$ is the inverse of $9$ modulo $19$. Since $9\cdot 17=153\equiv 1$, the required residue isThis is the unique representative in $\{1,\dots ,19\}$.

For the simultaneous integer congruences, the modulus-$2$ condition is already implied by $x\equiv 3(\mathrm{mod}4)$. Write $x=3+4k$; the modulus-$3$ condition becomes $k\equiv 1(\mathrm{mod}3)$, hence $x=7+12t$. The modulus-$5$ condition then gives $2+2t\equiv 4$, or $t\equiv 1(\mathrm{mod}5)$. ThereforeEvery such integer satisfies all four integer congruences; reversing the substitutions shows that there are no others. The uniqueness modulo $60$ also follows from the Chinese remainder theorem applied to the coprime moduli $3,4,5$.