中國剩餘定理

　　如要討論中國利餘定理，同餘（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後的餘數分別為r₁，r₂，r₃。因此有

x≡r₁(mod 3)

x≡r₂(mod 5)

x≡r₃(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)

由同餘的特性，我們有

70r₁≡r₁(mod 3)、70r₁≡0(mod 5)及70r₁≡0(mod 7)

21r₂≡r₂(mod 5)、21r₂≡0(mod 3)及21r₂≡0(mod 7)

15r₃≡r₃(mod 7)、15r₃≡0(mod 3)及15r₃≡0(mod 5)

因此亦有

70r₁+21r₂+15r₃≡r₁(mod 3)

70r₁+21r₂+15r₃≡r₂(mod 5)

70r₁+21r₂+15r₃≡r₃(mod 7)

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

　　由以上的推導方法，我們可以知道，無論餘數是多少，也可運用這個方法；而且無論除數有多少個，也可用同一個推導的方法找到一公式來計出符合條件的未知數。而這種一般的解法便是「中國剩餘定理」。

　　網主在中學時代經已接觸「鬼谷算」，那時候對同餘不大認識，對「鬼谷算」的意義、內藏的玄機和方法的原理，都認識不深，只覺這道題目跟餘數有關，隨即想到「素數公式」的問題，究竟用這種方法，可否構造到素數呢？而餘數及素數間又有何關係呢？

　　經過了很複雜的嘗試（並非證明），發現了構造或尋找素數的「簡單」方法，即可以用電腦編一個十分簡單的程序，搜出所有任意指定範圍內的素數。

　　其實，用利用中國剩餘定理，再用已知的素數為除數，設已知首n個的素數，而且第n個素數是p，只要代入不同的餘數，如果所計算出來的結果是介乎p及p²之間，則這個必定是素數，而且因為p及p²之間必有素數存在（網主曾在某書本看過這個定理，但出處卻已忘記），所以利用這個方法，可以找出所要求的素數。

　　當然，這個結果只是很膚淺和簡單，網主只希望透過這網頁跟讀者分享。


上一章	第一章