中国剩余定理

x ≡a1(mod m1)
x ≡a2(mod m2)
x ≡a3(mod m3)
中国剩余定理 x在模m1*...*mn下有唯一解；
其中m1,m2,m3两两互质
M=Πmi;
Mi=M/mi;
其中 Miyi ≡1(mod m1) ,即yi是Mi模mi的逆；
答案 x=∑aiMiyi
正确性:对于任意 同余方程只剩下aj*Mj*yj ,又 Mj*yj在模mj下互逆=1;显然正确性又保障；
唯一性：若不然
xi ≡xj(mod m1)
...
xi ≡xj(mod mn)
所以 m1|xi-xj ...mn|xi-xj又mi两两互质；
所以 m1*...*mn|xi-xj 即 M|xi-xj
所以 xi ≡xj (mod M)即在模M意义下 xi=xj;