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

Here, x = a (mod 5)

x = 2 (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 = 5

a2 = 2       m2 = 7

Now,

m = m1 × m2

or, m = 5 × 7

or, m = 35

Also,

M1 = $$\frac{m}{m_1}$$ = 35/5 = 7

M2 = $$\frac{m}{m_2}$$ = 35/7 = 5

Now, we need to find the inverse of M1 mod m1 and M2 mod m2

Here, to find inverse of 7 mod 5

7 × 0 = 0 (mod 5)

7 × 1 = 2 (mod 5)

7 × 2 = 4 (mod 5)

7 × 3 = 1 (mod 5)

Therefore, 3 is the inverse of 7 mod 5.

Let y1 = 3

Also, to find inverse of 5 mod 7

5 × 0 = 0 (mod 7)

5 × 1 = 5 (mod 7)

5 × 2 = 3 (mod 7)

5 × 3 = 1 (mod 7)

So, inverse is 3

Let y2 = 3

We get,

a1 = 1      M1 = 7    y1 = 3

a2 = 2     M2 = 5    y2 = 3

The solutions to these systems are those x such that

x = a1M1y1 + a2M2y2 (mod m)

x = 1 × 7 × 3 + 2 × 5 × 3 (mod 35)

x = 51 (mod 35)

x = 16 (mod 35)

Hence, we concolude that 16 is the smallest +ve integer that leaves remainder 1 when divided by 5 and 2 when divided by 7.