Multiple modulis, trying to find 1 number

Question

I won't quote here the full question, because it's irrelevant.

${x \in \mathbb{N}}$

${x \le 250}$

${x \mod 8 = 1}$

${x \mod 7 = 2}$

${x \mod 5 = 3}$

So my idea was to write down ever number that gives modulo 8 = 1, starting at 9, 17, 25, ...

Then I'd have to check which of these numbers is modulo 7 = 2 ...

And then which of them are modulo 5 = 3 ...

But there has to be a more efficient way (I hope).

How do I connect those modulis so I can calculate $x$ straight?

Answer 1

For some integers $i,j,k$, we have: $$x = 1 + 8i$$ $$x = 2 + 7j$$ $$x = 3 + 5k$$

The first two equations mean that $1 + 8i = 2 + 7j$, or equivalently, $1 + 8i \equiv 1 + i \equiv 2 \mod 7$ which becomes $i \equiv 1 \mod 7$. So take $i = 1 + 7l$ and get $x = 1 + 8(1 + 7l) = 9 + 56l$.

Then, that means that $9 + 56l = 3 + 5k$, or equivalently, $9 + 56l \equiv 4 + l \equiv 3 \mod 5$, which becomes $l \equiv 4 \mod 5$. So take $l = 4 + 5m$ and get $x = 9 + 56(4 + 5m) = 9 + 224 + 280m = 233 + 280m$.

$x = 233 + 280m$ satisfies all three equations for any integer $m$. With the restriction $1 \leq x \leq 250$, $x = 233$ is the only solution.

Answer 2

Just use the Chinese Remainder Theorem:

$x = 1\times7\times5\times3 + 2\times8\times5\times3 + 3\times8\times7\times1 + k\times8\times7\times5 = 513 + 280k$, for every $k\in\mathbb{Z}$

So the only valid $x$ is 233.

Answer 3

Hint $\ \ 5,8\mid x\!+\!7\iff 40\mid x\!+\!7\iff x=-7\!+\!40k.\,$

${\rm mod}\,\ 7\!:\,\ 2\equiv x = -7\!+\!40\color{#c00}k\equiv -2k\iff \color{#c00}{k\equiv -1},\ $ so $\,x = -7\!+\!40(\color{#c00}{-1}\!+\!7j) = -47\!+\!280j$