Is there a non-brute-force way to find $x$ such that $45\leq x < 200$, $x\equiv 0 \pmod{5}$ , $x\equiv1 \pmod{8}$, $x\equiv1 \pmod{12}$?

Question

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 1

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.

Answer 2

From the last two congruences, $x\equiv 1 \pmod{24}$

Then $x\equiv 1 \equiv 25 \equiv 49 \equiv...$

Just keep going until you find something congruent to $0 \pmod{5}$ that is within your range of interest.

Or you could note that $25$ works, and then so will $25 + 120k$ for any integer $k$.

Answer 3

Just use the Chinese remainder theorem: $$x\equiv1\bmod12\implies x\equiv1\bmod3$$ $$x\equiv1\bmod8\land x\equiv1\bmod3\implies x\equiv1\bmod24$$ $$x\equiv1\bmod24\land x\equiv0\bmod5\implies x\equiv 25\bmod120$$ Then add 120 repeatedly to 25 until getting a number within the desired range, yielding $x=145$.

Answer 4

Hint: Use the Chinese Remainder Theorem. In the case for modular arithmetic, this theorem is as follows:

Theorem Suppose you have a system of congruences: $$\begin{cases} x \equiv a_1 \ \mbox{mod} \ b_1 \\ \vdots \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \vdots \\ x\equiv a_n \ \mbox{mod} \ b_n \end{cases}$$ where $b_i$ are pairwise coprime. Then there is a unique $c$ such that $$x\equiv c \ \mbox{mod} \ \prod_{j=1}^nb_j$$

Does this hint help?