Theorem :Chinese Remainder Theorem Let m1,m2,...,mn be pairwise relatively prime positive integer and let b1,b2,...bn be any integers. Then the system of linear congruences in one variable given by _ x = b1 mod m1 _ x = b2 mod m2 . . . _ x = bn mod mn has unique solution modulo m1m2....mn proof: We first construct a solution to the given system of linear congruences in one variable. Let M=m1m2...mn and , i=1,2,...,n. let Mi=M/mi, now (Mi,mi)=1 for each i. _ ixi = 1 mod mi has a solution for each i by corollary _ {The linear congruence in one variable ax = 1 mod m has a solution _ if and only if (a,m) = 1 then ax = 1 mod m has exactly one incongruent solution modulo m. Form x=b1M1x1+b2M2x2+...+bnMnxn Note that x is a solution of the desired system since , for i=1,2,...,n x=b1M1x1+b2M2x2+....+biMixi+...+bnMnxn _ = 0+0+...+bi+...+0 mod mi _ = bi mod mi It remains to show the uniqueness of the solution modulo M. Let x' be another solution to given system of linear congruences _ in one variable.Then,for all i, we have x' = bi mod mi ; _ _ since x = bi mod mi for all i , we have that x = x' mod mi for all i, or ,equivalently , mi | x-x' for all i. Then M | x-x' ,from which _ x = x' mod M . The proof i s complete. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.134.242.144