6. The goal of this question is to prove the Chinese remainder theorem. Let n1,.
ID: 3209673 • Letter: 6
Question
6. The goal of this question is to prove the Chinese remainder theorem. Let n1,..., nk be pairwise coprime positive integers (thus every two of them are coprime). Let c1,..., ck be arbitrary. Consider the system of congruence equations X Cl (mod n) ck (mod nk) The Chinese remainder theorem, which you will prove below, asserts that the system is soluble and has a unique solution mod N Tli 1=1 (a) Show that if two integers satisfy the system, they are congruent mod N. (This should be short. If xo, x1 both are solutions, then x0x1 (mod ni) for all i. Does Theorem 53 of Hardy-Wright now help? Note that the hypothesis that the ni are pairwise coprime is crucial.) (b) You will now show that the system does indeed have a solution (which by Part (a), will be unique mod N). You will do this by constructing a solution, as follows: For each 1Explanation / Answer
We start by forming the product N = n1n2 · · · nk . For each i = 1, 2, . . . , k , let Ni = N/ni = n1 · · · ni1ni+1 · · · nk
In words, Ni is the product of all the integers nr with the factor ni omitted.
By hypothesis, the ni are relatively prime in pairs, so that gcd(Ni , ni ) = 1.
According to the theory of a single linear congruence, it is therefore possible to solve the congruence
Ni x 1 (mod ni ); call the unique solution xi .
Our aim is to prove that the integer x = c1N1x1 + c2N2x2 + ·· ·+ckNkxk is a simultaneous solution of the given system.
First, observe that Ni 0 (mod nj ) for i j , because nj | Ni in this case.
The result is x = c1N1x1 + c2N2x2 + ·· ·+ckNkxk ciNixi (mod ni ) for each i = 1, 2, . . . , k
But the integer xi was chosen to satisfy the congruence Ni x 1 (mod ni ), which forces x ci · 1 ci (mod ni )
This shows that a solution to the given system of congruences exists.
As for the uniqueness assertion, suppose that x0 is any other integer that satisfies these congruences.
Then x ai x0 (mod ni ) for each i = 1, 2, . . . , k
and so ni | x x0 for each value of i. Because gcd(ni , n j ) = 1, we have that n1n2 · · · nk | x x0 ;
hence x x0 (mod N).
With this, the Chinese Remainder Theorem is proven.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.