elementary number theory - Is there a non-brute-force way to find $x$ such that $45leq x < 200$, $xequiv 0 pmod{5}$ , $xequiv1 pmod{8}$, $xequiv1 pmod{12}$?

Like the title says, I'm wondering if there's a non-brute-force way to determine $x$ such that

$$45\le x<200,$$
$$x\bmod5\equiv0,$$
$$x\bmod8\equiv1,$$
$$x\bmod12\equiv1$$
I know I can simply enumerate all integers in $[45, 200)$ to get the answer (145), but I'm wondering if there's a more elegant solution.

Answer

Well:

• Since the number is $0$ mod $5$, we don't have to check all integers in $[45,200)$, but only the multiples of $5$: $45, 50, 55, \ldots$





• But we also know $x \mod{8} = 1$, which happens one in every 8 multiples of $5$. So $x \mod 40 = 25$. Now we only have to check $65, 105, 145, 185$.




• The third statement, $x \mod 12 = 1$, is the same as $x \mod 3 = 1$ and $x \mod 4 = 1$. The latter thing we already know from $x \mod 8 = 1$. So we combine the facts $x \mod 40 = 25$ and $x \mod 3 = 1$ to get $x \mod 120 = 25$. Now the only possibility is $145$.

If you would like to know the mathematical justification for these steps, it is known as the Chinese remainder theorem.