Prove the Chinese Remainder Theorem below: 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) . .
Prove the Chinese Remainder Theorem below:
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).
Prove
There are several known proofs of the CRT, but this will require you to write a specific one.
For each i = 1, 2, . . . r, let Ni be the product of all of the moduli mj for j ̸= i, Ni = m1 · · · mi-1mi+1 · · · mr.
1. For each i, show that gcd(Ni, mi) = 1, and that there are integers ui and vi such that Niui + mivi = 1.
2. For each i and j with i ̸= j, show that Niui = 0 (mod mj).
3. For each i, show that Niui = 1 (mod mi).
4. Find a Z-linear combination x of the Niui which solves the entire system of linear congruences,
x = a1 (mod m1)
x = a2 (mod m2)
.
.
.
x = ar (mod mr)
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images
