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?

1 Answer
Mar 14, 2018

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.