本頁使用了標題或全文手工轉換

中國剩餘定理

維基百科,自由的百科全書
跳至導覽 跳至搜尋

中國剩餘定理,又稱中國餘數定理,是數論中的一個關於一元線性同餘方程組的定理,說明了一元線性同餘方程組有解的準則以及求解方法。也稱為孫子定理,古有「韓信點兵」、「孫子定理」、「求一術」(宋沈括)、「鬼谷算」(宋周密)、「隔墻算」(宋 周密)、「剪管術」(宋楊輝)、「秦王暗點兵」、「物不知數」之名。

物不知數[編輯]

一元線性同餘方程組問題最早可見於中國南北朝時期(公元5世紀)的數學著作《孫子算經》卷下第二十六題,叫做「物不知數」問題,原文如下:

有物不知其數,三三數之剩二,五五數之剩三,七七數之剩二。問物幾何?

即,一個整數除以三餘二,除以五餘三,除以七餘二,求這個整數。《孫子算經》中首次提到了同餘方程組問題,以及以上具體問題的解法,因此在中文數學文獻中也會將中國剩餘定理稱為孫子定理。

宋朝數學家秦九韶於1247年《數書九章》卷一、二《大衍類》對「物不知數」問題做出了完整系統的解答。明朝數學家程大位在《算法統宗》中將解法編成易於上口的《孫子歌訣》[1]

三人同行七十希,五樹梅花廿一支,七子團圓正半月,除百零五便得知

這個歌訣給出了模數為3、5、7時候的同餘方程的秦九韶解法。意思是:將除以3得到的餘數乘以70,將除以5得到的餘數乘以21,將除以7得到的餘數乘以15,全部加起來後再減去105或者105的整數倍,得到的數就是答案(除以105得到的餘數則為最小答案)。比如說在以上的物不知數問題裡面,使用以上的方法計算就得到

因此按歌訣求出的結果就是23.

形式描述[編輯]

用現代數學的語言來說明的話,中國剩餘定理給出了以下的一元線性同餘方程組:

有解的判定條件,並用構造法給出了在有解情況下解的具體形式。

中國剩餘定理說明:假設整數m1, m2, ... , mn其中任兩數互質,則對任意的整數:a1, a2, ... , an,方程組有解,並且通解可以用如下方式構造得到:

  1. 是整數m1, m2, ... , mn的乘積,並設,即是除了mi以外的n − 1個整數的乘積。
  2. 數論倒數
  3. 方程組的通解形式為: 在模的意義下,方程組只有一個解:

證明[編輯]

從假設可知,對任何,由於,所以 這說明存在整數使得 這樣的叫做的數論倒數。考察乘積可知:

所以滿足:

這說明就是方程組的一個解。

另外,假設都是方程組的解,那麼:

兩兩互質,這說明整除. 所以方程組的任何兩個解之間必然相差的整數倍。而另一方面,是一個解,同時所有形式為:

的整數也是方程組的解。所以方程組所有的解的集合就是:

例子[編輯]

使用中國剩餘定理來求解上面的「物不知數」問題,便可以理解《孫子歌訣》中的數字含義。這裡的線性同餘方程組是:

三個模數m13, m25, m37的乘積是M105,對應的M135, M221, M315. 而可以計算出相應的數論倒數:t12, t21, t31. 所以《孫子歌訣》中的70,21和15其實是這個「物不知數」問題的基礎解:

而將原方程組中的餘數相應地乘到這三個基礎解上,再加起來,其和就是原方程組的解:

這個和是233,實際上原方程組的通解公式為:

《孫子算經》中實際上給出了最小正整數解,也就是k-2時的解:x23.

交換環上的推廣[編輯]

主理想整環[編輯]

R是一個主理想整環m1, m2, ... , mk是其中的k個元素,並且兩兩互質。令Mm1m2...mn為這些元素的乘積,那麼可以定義一個從商環R/MR映射到環乘積R/m1R × … × R/mkR同態

並且是一個環同構。因此的逆映射也存在。而這個逆映射的構造方式就如同中國剩餘定理構造一元線性同餘方程組的解一樣。由於miMiM/mi互質,所以存在siti使得

而映射

就是的逆映射。

也是一個主理想整環。將以上的R換成,就能得到中國剩餘定理。因為

一般的交換環[編輯]

R是一個有單位元交換環I1, I2, ... , Ik是為環理想,並且當時,,則有典範的環同構

模不兩兩互質的同餘式組[編輯]

模不兩兩互質的同餘式組可化為模兩兩互質的同餘式組,再用孫子定理直接求解。

84=22×3×7,160=25×5,63=32×7,由推廣的孫子定理可得 同解。[2]

注意求解過程中應先檢查同餘式組上是否存在矛盾,存在矛盾的同餘式組無解。

參見[編輯]

參考資料[編輯]

  1. ^ 李儼《大衍求一術的過去和未來》《李儼.錢寶琮科學史全集》卷6 121頁《程大位的孫子歌》遼寧教育出版社. 1998
  2. ^ 劉古勝 徐東星 余暢. 推廣的孫子定理. 高師理科學刊. 2010, (3). 
參考書目