Question

Find the smallest positive $n$ such that \begin{align*} n &\equiv 3 \pmod{4}, \\ n &\equiv 2 \pmod{5}, \\ n &\equiv 6 \pmod{7}. \end{align*}

Answer 1

4, 5, and 7 are mutually coprime, so you can use the Chinese remainder theorem right away.

We construct a number
`x` such that taking it mod 4, 5, and 7 leaves the desired remainders:

`x=3\cdot5\cdot7+4\cdot2\cdot7+4\cdot5\cdot6`

• Taken mod 4, the last two terms vanish and we have

`x\equiv3\cdot5\cdot7\equiv105\equiv1\pmod4`

so we multiply the first term by 3.

• Taken mod 5, the first and last terms vanish and we have

`x\equiv4\cdot2\cdot7\equiv51\equiv1\pmod5`

so we multiply the second term by 2.

• Taken mod 7, the first two terms vanish and we have

`x\equiv4\cdot5\cdot6\equiv120\equiv1\pmod7`

so we multiply the last term by 7.

Now,

`x=3^2\cdot5\cdot7+4\cdot2^2\cdot7+4\cdot5\cdot6^2=1147`

By the CRT, the system of congruences has a general solution

`n\equiv1147\pmod{4\cdot5\cdot7}\implies\boxed{n\equiv27\pmod{140}}`

or all integers
`27+140k`,
`k\in\mathbb Z`, the least (and positive) of which is 27.