# Find the value of x such that x = 1 (mod 3), x = 1 (mod 4),  x = 1 (mod 5) and x = 0 (mod 7) using Chinese remainder theorem.

Here, from question

x = 1(mod 3)

x = 1(mod 4)

x = 1(mod 5)

x = 0(mod 7)

We know, linear congurency is of form x = an (mod mn) where n is an integer. So, Let us suppose

 a1  = 1 m1 = 3 a2 = 1 m2 = 4 a3 = 1 m3 = 5 a4 = 0 m4 = 7

Now, m = m1 × m2 × m3 × m4

= 3 × 4 × 5 × 7

= 420

Also,

M1 = $$\frac{m}{m_1} = \frac{420}{3}$$ = 140

M2 = $$\frac{m}{m_2} = \frac{420}{4}$$ = 105

M3 = $$\frac{m}{m_3} = \frac{420}{5}$$ = 84

M4 = $$\frac{m}{m_4} = \frac{420}{7}$$ = 60

Now, we need to find the inverse of M1 mod m1,  M2 mod m2, M3 mod m3 and M4 mod m4.

Now, inverse of M1 mod m1 i.e 140 mod 3 is

140 × 0 = 0 (mod 3)

140 × 1 = 2 (mod 3)

140 × 2 = 1 (mod 3)

∴ 2 is the invers of 140 mod 3

Let y1 = 2

Also, inverse of 105 mod 4 is

105 × 0 = 0 (mod 4)

105 × 1 = 1 (mod 4)

∴ 1 is the inverse of 105 mod 4.

Let y2 = 1

Also, inverse of 84 mod 5

84 × 0 = 0 (mod 5)

84 × 1 = 4 (mod 5)

84 × 2 = 3 (mod 5)

84 × 3 = 2 (mod 5)

84 × 4 = 1 (mod 5)

∴ 4 is the inverse of 84 mod 5

Let y3 = 4

Similarly, inverse of 60 mod 7

60 × 0 = 0 (mod 7)

60 × 1 = 4 (mod 7)

60 × 2 = 1 (mod 7)

∴ 2 is the inverse of 60 mod 7

Let y4 = 2

Now, we know,

a1 = 1,    a2 = 1,   a3 = 1,   a4 = 0

M1 = 140,    M2 = 105,   M3 = 84,   M4 = 60

y1 = 2,   y2 = 1,   y3 = 4,   y4 = 2

The solutions to these systems are those

x such that

x = a1M1y1 + a2M2y2 + a3M3y3 + a4M4y4  mod m

= 1 × 140 × 2 + 1× 105 × 1 + 1 × 84 × 4 + 0 × 60 × 2 mo 420

= 280 + 105 + 446 (mod 420)

= 301

Hence, we conclde that 301 is the smallest +ve integer that leaves remainder 1 when divided by 3,4,5 and 7.