Re: [高中] 中國餘式定理

[gary27 (小龜)]

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
推 goshassault:神@@"