1
$\begingroup$

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?

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This method is preferable to the Chinese remainder theorem for simple systems of congruences. +1 $\endgroup$ – mysatellite Nov 7 '15 at 14:52
1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Upvoting it since it is your first answer. However, you could present it better $\endgroup$ – Shailesh Nov 7 '15 at 14:33
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.