Take the 2-minute tour ×

Give all solutions of the system of congruences:

$$x \equiv 3 \pmod 5 $$ $$x \equiv 2 \pmod 4$$ $$x \equiv 5 \pmod 7$$

Then give the least strictly positive solution.

share|improve this question
Since this is HW, can you please tell us what you have tried? –  Amzoti Sep 30 '12 at 3:05
I know that I have to find a corresponding x that solves all three. To do so I have to find one for the first two. –  user42896 Sep 30 '12 at 3:08
add comment

3 Answers

HINT: You’ll want the Chinese remainder theorem (CRT) to get all of them; the same article gives a systematic method. However, there’s one solution that’s very easy to find by inspection; try some small negative numbers. Then the CRT gives you all of them very quickly, without any extensive computation.

share|improve this answer
add comment

Another Hint:

As $x\equiv 3 $ mod 5, $x=5k+3$ for some integral $k$. Using $x\equiv 2$ mod 4, we have $k+1\equiv 0$ mod 4 i.e. $k$ is of the form $4j+3$. Proceed in a similar fashion to finish this off!

share|improve this answer
add comment

Observe that $x+2$ is divisible by $4,5,7,$ so is divisible by $lcm(4,5,7)=140$

$\implies x+2=140a$ where $a$ is any integer.

When the remainders are same, we don't need to apply CRT.

So, the least positive value of $x$ is $140-2=138.$

share|improve this answer
add comment

Your Answer


