中國剩餘定理證明過程

中國剩餘定理可以描述為：

若某數x分别被d1、、…、dn除得的餘數為r1、r2、…、rn，則可表示為下式：

x=R1r1+R2r2+…+Rnrn+RD

其中R1是d2、d3、…、dn的公倍數，而且被d1除，餘數為1；（稱為R1相對于d1的數論倒數）

R1 、

R2 、

…  、

Rn是d1、d2、…、dn-1的公倍數，而且被dn除，餘數為1；

D是d1、d2、…、的最小公倍數；

R是任意整數（代表倍數），可根據實際需要決定；

且d1、、…、必須互質，以保證每個Ri(i=1,2，…，n)都能求得.

（注：因為R1對d1求餘為1，是以R1r1對d1求餘為r1，這就是為什麼是R1對d1求餘為1的目的，其次，R2r2,R3r3…Rnrn對d1求餘都是0）

如要讨論中國利餘定理，同餘（congruence）的概念可算是必須。

給定一個正整數n，我們說兩個數a、b是對模n同餘，如果a-b是n的倍數。用符号a≡b(mod n)來代表。一般來說，a≡b(mod n)等同于a＝b+kn，而a，b，k，n都是整數，是以，13≡1(mod 6)、19≡1(mod 6)。 

但同餘并不隻是一個代号，而是有很友善和有趣的特性。（一）整數加法跟普通加法相似，a+c≡(b+c)(mod n)；（二）整數乘法跟普通乘法相似，ac≡bc(mod n)，而a，b，c，n都是整數。但如果ac≡bc(mod n)，則不一定a≡b(mod n)。 

以「鬼谷算」為例，假設x是那個未知數，而除3，5，7後的餘數分别為r1，r2，r3。是以有 

x≡r1(mod 3) 

x≡r2(mod 5) 

x≡r3(mod 7) 

而另一方面

70＝(5x7)x2≡1(mod 3)、70≡0(mod 5)及70≡0(mod 7) 

21＝(3x7)x1≡1(mod 5)、21≡0(mod 3)及21≡0(mod 7) 

15＝(3x5)x1≡1(mod 7)、15≡0(mod 3)及15≡0(mod 5) 

是以

x≡70r1+21r2+15r3+3m

x≡70r1+21r2+15r3+5n

x≡70r1+21r2+15r3+7p

 最後得到這個精彩的結果，x≡(70r1+21r2+15r3)(mod 105)，而105正便是3，5，7的最小公偣數。是以其實在很多數字可以滿足這幾個餘數條件的，要找到最小值才要減105。

對于中國剩餘定理有個簡單了解并記憶的方法：

中國剩餘定理的思想在于先找到一個滿足條件的數，不管是不是最小的，如果不是最小的就不斷減公倍數，中國剩餘定理的巧妙在于把滿足條件的數分成三個部分相加，例如：

假設滿足條件的數為：M=3*5*a+5*7*b+3*7*c

先讓它滿足條件1：除以3餘1，我們看M的第一部分和第三部分能被3整除，隻要第二部分除以3餘1就行了，選擇b=2就滿足

再滿足條件2：除以5餘2，考慮第三部分就行了，選擇c=2就滿足

最後滿足條件3：除以7餘3，考慮第一部分就行了，選擇a=3

這樣M=3*5*3+5*7*2+3*7*2=157，比公倍數大，減去公倍數，157-105=52是滿足條件最小數

以我個人了解寫成下面這個形式（以3個數為例）

X被a,b,c處分别餘r1,r2,r3。表示為：

X%a = r1                     x%b = r2                     x%c = r3

bc*k1 % a = 1     ac*k3 % b = 1     ab*k3 % c = 1

x = bc * k1 * r1 + ac * k2 * r2 + ab * k3 * r3

本文轉自 小眼兒 部落格園部落格，原文連結：http://www.cnblogs.com/hujunzheng/articles/3885695.html，如需轉載請自行聯系原作者