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.