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.

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

Login Now

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.

 

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 . . .