Answer to Question #139419 in Combinatorics | Number Theory for Kishore

Question

find the smallest positive solution of the system of linear congruences ? X=2 (mod3) , X=3(mod 5), X=2(mod 7)

Answer 1

Since the numbers 3 5 7 are coprime, we use the Chinese remainder theorem

${M_0} = {m_1}{m_2}{m_3}=3*5*7 =105$

$M_i =\frac{M_0}{m_i}$

$M_1 =\frac{M_0}{m_1}=\frac{105}{3}=35$

$M_2 =\frac{M_0}{m_2}=\frac{105}{5}=21$

$M_3 =\frac{M_0}{m_3}=\frac{105}{7}=15$

$M_iy_i =a_i(mod\ m_i)$

$35y_1 =2(mod\ 3)$

$33y_1+2y_1 =2(mod\ 3)$

$2y_1 =2(mod\ 3)$

$y_1=1$

$21y_2 =3(mod\ 5)$

$20y_2+y_2 =3(mod\ 5)$

$y_2 =3(mod\ 5)$

$y_2 =8$

$15y_3=2(mod\ 7)$

$14y_3+y_3=2(mod\ 7)$

$y_3=2(mod\ 7)$

$y_3=9$

$x =( M_1y_1+M_2y_2+M_3y_3)(mod\ M_0)$

$x =(35*1+21*8+15*9)(mod\ 105)$

$x= 338(mod\ 105)$

$x=23$

Answer: x=23