Question

What is the smallest integer which when divided by 3, 5, 7 & 11 leaves remainders of 2, 4, 6 & 1 respectively?

Options are:
A) 104 B) 1154 C) 419 D)None of the options given

Is there any systematic way to approach this question instead of just plain trial and error method?

Answer 1

See below.

Explanation:

This problem is solved as an application of the so called Chinese Remainder Theorem (CRM)

Given

`{(x equiv r_1 mod m_1),(x equiv r_2 mod m_2),( cdots " " cdots " " cdots),(x equiv r_n mod m_n):}`

and calling `m = m_1m_2 cdots m_n` with

`M_k = m/m_k EE t_k | t_k M_k equiv 1 mod m_k`

now calling `s_k = t_k M_k` we have

`x = sum_(k=1)^n s_k r_k`

In our example

`r_1 = 2, r_2=4, r_3 = 6, r_4 = 1`
`m_1 = 3, m_2=5,m_3=7,m_4=11`

then

`t_1 = 1, t_2 = 1, t_3 = 2, t_4 = 2` and

`x = 3884` is a solution.

NOTE

With this method we can find a solution and eventually the smallest. In this case `419` is the smallest solution.