Least number which leaves remainder 1,2,3,4 when divided succesively by 2,3,5,7

ashwinkumardp · #1 $Old$ November 1st, 2009, 07:53 PM

Hi All,

Please help me with this problem:

What is the least number which leaves remainder 1, 2, 3 and 4 when divided successively by 2, 3, 5 and 7?

Thank you,
Ashwin Kumar D P.
Bangalore, India.

aidan · #2 $Old$ November 2nd, 2009, 02:35 AM

Quote:

Originally Posted by ashwinkumardp $View Post$

Hi All,
Please help me with this problem:
What is the least number which leaves remainder 1, 2, 3 and 4 when divided successively by 2, 3, 5 and 7?
Thank you,
Ashwin Kumar D P.
Bangalore, India.

$x \equiv 1 \mod 2$ Equation1

$x \equiv 2 \mod 3$ Equation2

$x \equiv 3 \mod 5$ Equation3

$x \equiv 4 \mod 7$ Equation4

Use the Chinese Remainder Theorem.

However, for this question try this:
The values that satisfy Eqn4 are
4, 11, 18, 25, 32, 39, ...
They are 4 + multiples of 7.

Use those values in Eqn3

$4 \equiv 4 \mod 5$

$11 \equiv 1 \mod 5$

$18 \equiv 3 \mod 5$

18 satisfies Eqn4 & Eqn3

Use 18 + multiples of 35 ( 7 times 5 ) for Equation2
18, 53, 88, 123, ...

Find the one that satisfies equation2.
Then a similar procedure for Equation1

.