Using the Chinese Remainder Theorem
Using the Chinese Remainder Theorem Solve the following:
Here is the theorem first:
Chinese Remainder Theorem (CRT): Let r, m1, . . . , mr ∈ Z and for all 1 ≤ i ̸= j ≤ r
suppose gcd(mi, mj ) = 1. Then for any r integers a1, . . . , ar, the system of linear
congruences
x = a1 (mod m1)
x = a2 (mod m2)
.
.
.
x = ar (mod mr)
has a solution x ∈ Z and it is unique modulo m1m2 · · · mr, i.e. if y ∈ Z is any other
solution, then y = x (mod m1m2 · · · mr).
Solve the given system of congruences.
(a)
x = 5 (mod 6)
x = 7 (mod 11)
(b)
x = 3 (mod 11)
x = 4 (mod 17)
(c)
x = 1 (mod 2)
x = 2 (mod 3)
x = 3 (mod 5)
(d)
x = 2 (mod 5)
x = 0 (mod 6)
x = 3 (mod 7)
(e)
x = 1 (mod 5)
x = 3 (mod 6)
x = 5 (mod 11)
x = 10 (mod 13)
(f )
x = 1 (mod 7)
x = 6 (mod 11)
x = 0 (mod 12)
x = 9 (mod 13)
x = 0 (mod 17)
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
