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.

Question

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.

Suresh Chand · Accepted Answer

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.

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.

Leave your Answer:

Hits Counter

Question

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.

Leave your Answer: