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

This answer is restricted. Please login to view the answer of this question.

Login Now

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.

If you found any type of error on the answer then please mention on the comment or report an answer or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .