1. 定理。n=n1n2…nk,且ni间两两互质,a<---->(a1,a2,…,ak),a属于,ai属于,且i=1,2…k
ai=amodni。
若 a<----->(a1,a2,…,ak)
b<----->(b1,b2,…bk)
那么
a+b<----->((a1+b1)modn1,(a2+b2)modn2,…,(ak+bk)modnk)
a-b<----->((a1-b1)modn1,(a2-b2)modn2,…,(ak-bk)modnk)
ab<----->((a1b1)modn1,(a2b2)modn2,…,(akbk)modnk)
证明:
(1)将a转换为a1,a2…ak,只需对n进行质因数分解
(2)将a1,a2,…ak转换为a
mi=n/ni,ci=mi(modni)
需证明:a=(a1c1+a2c2+…+akck)(modn)能保证a=ai(modni)
j!=i,则,mj=0(modni) 即 cj=mj=0(modni)
即:ci<- --- >(0,0,…,0,1,0,…0)(第i个为1)
所以对每个i
有:a=aici(modni)=ai mi(modni)=ai(modni)
同理可证明出加减乘、
2. n=n1n2…nk,且ni间两两互质,对a1,a2,…,ak , x=ai(modni)对模n有唯一解
3. n1,n2不互素的解法
http://www.cnblogs.com/inpeace7/archive/2012/03/17/2403063.html
中国剩余定理,非互素
x=a1(mod n1)
x=a2(mod n2)
n1与n2不互素。
x=n1k1+a1
x=n2k2+a2
n1k1=n2k2+a2-a1
n1k1=a2-a1(mod n2)
若k1有解,则gcd(n1,n2)|(a2-a1)
设d=gcd(n2,n1)
即 n1k1/d=(a2-a1)/d(mod n2/d)
k1=(a2-a1)/d*(mod n2/d)
设k1=(a2-a1)/d*+k(n2/d)
所以x=n1k1+a1=n1((a2-a1)/d*)+k(n2/d))+a1
x=n1*(a2-a1)*/d+a1(mod n1n2/d)
令t=(a2-a1)*,n=n1n2/d
x=tn1+a2(mod n)