Question

简述中国剩余定理

Answer 1

不要拘限于书上所讲的中国剩余定理。
AAA　我下面给出一个例题，采用的是中国剩余定理的一种变式，或者说是推广。
我个人认为能够更好地理解中国剩余定理的本质所在。

一个数÷5余1，÷7余3，÷9余2，这个数最小是几？
题目转化为同余式组
x==1 mod 5
x==3 mod 7
x==2 mod 9
解：
令x==7*9*a+5*9*b+5*7*c mod 5*7*9
即x=7*9*a+5*9*b+5*7*c+5*7*9*t
即x==5*7*9*(a/5+b/7+c/9 mod 1)
即x=5*7*9*(a/5+b/7+c/9+t)
代入原同余式组得
7*9*a==1 mod 5 , 于是a==2 mod 5, 取其特值2为代表。
5*9*b ==3 mod 7，于是b==1 mod 7,取其特值1为代表。
5*7*c==2 mod 9,于是c==-2 mod 9,取其特值-2为代表。
再以
x==5*7*9*(a/5+b/7+c/9 mod 1)为求值式，进行计算。
先计算（a/5+b/7+c/9 mod 1)
注意，计算过程中，任一个加项或整体值上可以加减任一个整数，不影响。同时，在计算时，可以充分运用加法的交换律与结合律，随意调整加法项的位置与加法过程的顺序。
其中，mod 1这个提法一定要理解，这样可以为解同余式组带来极大的方便。
mod 1表示两个对象相差一个整数值。如果mod用来表示求余，则表示求一个数的小数部分；如果N==0 mod 1，即说明N为整数。

2/5+1/7-2/9 mod 1 ==2/5-2/9+1/7==8/45+1/7==101/45*7==101/315
于是x==101 mod 315
这个数最小为 101

BBB解的数量之判定法：
对于多个模并非两两互质的情况，可以先确立一组两两互质的分解基数集（质数集是一个常用的特例），将这些模用分解基数表示成为多个因数项，将其中相关于同一个分解基数的项进行归并。如果有矛盾，则无解。
否则有解。
例：同余式组
x=2 mod 16
x=3 mod 5
x=6 mod 12
取4, 3, 5作为分解基。变成
x=2 mod 4^2
x=3 mod 5
x=6 mod 4
x=6 mod 3
其中相关于同一个分解基数的情况，仅有x=2 mod 16与x=6 mod 4是相关于分解基数"4"的,它们没有矛盾。取两相容解集的交集，即其中解集较小的那个：x=2 mod 16.
再与x=3 mod 5及x=6==0 mod 3联立求解。

另例：
x=2 mod 18
x=8 mod 12
以3,2为分解基。
相关于分解基数3的转化式有x=2 mod 3^2, x=2 mod 3, 取前者。
相关于分解基数2的转化式有x=0 mod 2, x=0 mod 4, 取后者。

另例：同余式组
x=3 mod 12
x=2 mod 18
以2,3为分解基集，于是原同余式组变成
x==3 mod 2^2
x==3 mod 3
x==2 mod 3^2
x==2 mod 2
矛盾。故此同余式无解。

如果是形如
ax=b mod m形状的同余式联立的，
则可能出现无解、一解、多解的情况。一个基本的例子如下：
12x=18 mod 27 注：相当于12x=9+18k
自然就等价于同余式
4x=3 mod 9
解得x=3 mod 9, 转化为模27的同余式，为
x=3,12,21 mod 27

Answer 2

x除以m1余b1 ……x除以mn余bn M=m1乘到mn Mi=M/mi yi=(1/M)mod mi 及(1/M)除以mi的余数

x=b1*M1*y1+……+bn*Mn*yn 还要对M求余