What's the smallest three digit number that satisfies the following system of congruences?

Question

So my question is how to find the smallest three digit number $n$, which satisfies the following: $$ x \equiv 0\mod2\\ x \equiv 2\mod3\\ x \equiv 2\mod4\\ x \equiv 2\mod5\\ x \equiv 2\mod6\\ $$ My problem is that I know it can be solved but I can't use the Chinese Remainder Theorem because for example $(3,6)\neq1$... can anyone help?

Answer 1

Since $x \equiv 0 \mod 2$, $x \in \{2, 4, 6, 8, ...\}$

Since $x \equiv 2 \mod 3$, $x \in \{2, 8, 14, ...\}$

Since $x \equiv 2 \mod 4$, $x \in \{2, 14, 26, ...\}$

Since $x \equiv 2 \mod 5$, $x \in \{2, 62, 122, ...\}$

The last condition is already covered by the first two equivalences. The answer to the question is 122.

Answer 2

$x$ satisfies the original set of equations if and only if it satisfies the equations $x\equiv 2\pmod 3$, $x\equiv 2\pmod 4$ and $x\equiv 2\pmod 5$. Now you can apply the Chinese remainder theorem because these moduli are pairwise coprime.

Answer 3

The equivalence $x\equiv2\pmod4$ implies $x\equiv0\pmod2$.
The equivalence $x\equiv0\pmod2$ and $x\equiv2\pmod3$ imply that $x\equiv2\pmod6$.

Thus, of the $4$ equivalences, we only need to use $x\equiv2\pmod4$ and $x\equiv2\pmod3$.

Therefore, we need to solve the equivalences $$ x\equiv2\pmod3\\ x\equiv2\pmod4\\ x\equiv2\pmod5 $$ Hint: What do these say about $x-2$?

Answer 4

Note that $\mbox{lcm}(2,3,4,5,6) = 60.$ Change your system slightly to

$$ x \equiv 0\mod2\\ x \equiv 0\mod3\\ x \equiv 0\mod4\\ x \equiv 0\mod5\\ x \equiv 0\mod6\\ $$

so that the solution is obviously $x = 60k,$ where $k$ is any integer. Then observe that adding $2$ to any of these solutions, must be a solution to the original system. So the set of all solutions is $60k+2.$