中國剩餘定理- 維基百科，自由的百科全書

孫子定理，又稱中國剩餘定理或中國餘數定理，是數論中的一個關於一元線性同餘方程組的定理，說明了一元線性同餘方程組有解的準則以及求解方法。

該定理在中國古代也被稱 ... 中國剩餘定理 維基百科，自由的百科全書 跳至導覽 跳至搜尋 孫子定理，又稱中國剩餘定理或中國餘數定理，是數論中的一個關於一元線性同餘方程組的定理，說明了一元線性同餘方程組有解的準則以及求解方法。

該定理在中國古代也被稱為「韓信點兵」、「求一術」（宋沈括）、「鬼谷算」（宋周密）、「隔牆算」（宋周密）、「剪管術」（宋楊輝）、「秦王暗點兵」、「物不知數」等。

目次 1物不知數 2形式描述 2.1證明 3例子 4交換環上的推廣 4.1主理想整環 4.2一般的交換環 5模不兩兩互質的同餘式組 6參見 7參考資料 物不知數[編輯] 一元線性同餘方程組問題最早可見於中國南北朝時期（公元5世紀）的數學著作《孫子算經》卷下第二十六題，叫做「物不知數」問題，原文如下： 有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。

問物幾何？ 即，一個整數除以三餘二，除以五餘三，除以七餘二，求這個整數。

《孫子算經》中首次提到了同餘方程組問題，以及以上具體問題的解法，因此在中文數學文獻中也會將中國剩餘定理稱為孫子定理。

孫子沒正式證明，但後來印度數學家及天文學家阿耶波多給出具體過程，徹底解決了此定理的任何給定實例。

[1] 最初對「物不知數」問題作出完整系統解答的是宋朝數學家秦九韶，載於1247年《數書九章》卷一、二《大衍類》中，從而使這一問題變為定理。

明朝數學家程大位在《算法統宗》中將解法編成易於上口的《孫子歌訣》[2]： 三人同行七十希，五樹梅花廿一支，七子團圓正半月，除百零五便得知 這個歌訣給出了模數為3、5、7時候的同餘方程式的秦九韶解法。

意思是：將除以3得到的餘數乘以70，將除以5得到的餘數乘以21，將除以7得到的餘數乘以15，全部加起來後再減去105或者105的整數倍，得到的數就是答案（除以105得到的餘數則為最小答案）。

比如說在以上的物不知數問題裡面，使用以上的方法計算就得到 70 × 2 + 21 × 3 + 15 × 2 = 233 = 2 × 105 + 23. {\displaystyle70\times2+21\times3+15\times2=233=2\times105+23.} 因此按歌訣求出的結果就是23。

《數書九章》最初由偉烈亞力在19世紀初譯為英文，而西方世界最早的完整系統解法由高斯在1801年提出。

形式描述[編輯] 用現代數學的語言來說明的話，中國剩餘定理給出了以下的一元線性同餘方程組： ( S ) : { x ≡ a 1 ( mod m 1 ) x ≡ a 2 ( mod m 2 ) ⋮ x ≡ a n ( mod m n ) {\displaystyle(S):\quad\left\{{\begin{matrix}x\equiva_{1}{\pmod{m_{1}}}\\x\equiva_{2}{\pmod{m_{2}}}\\\vdots\qquad\qquad\qquad\\x\equiva_{n}{\pmod{m_{n}}}\end{matrix}}\right.} 有解的判定條件，並用構造法給出了在有解情況下解的具體形式。

中國剩餘定理說明：假設整數m1,m2,...,mn其中任兩數互質，則對任意的整數：a1,a2,...,an，方程組 ( S ) {\displaystyle(S)} 有解，並且通解可以用如下方式構造得到： 設 M = m 1 × m 2 × ⋯ × m n = ∏ i = 1 n m i {\displaystyleM=m_{1}\timesm_{2}\times\cdots\timesm_{n}=\prod_{i=1}^{n}m_{i}} 是整數m1,m2,...,mn的乘積，並設 M i = M / m i , ∀ i ∈ { 1 , 2 , ⋯ , n } {\displaystyleM_{i}=M/m_{i},\;\;\foralli\in\{1,2,\cdots,n\}} ，即 M i {\displaystyleM_{i}} 是除了mi以外的n−1個整數的乘積。

設 t i = M i − 1 {\displaystylet_{i}=M_{i}^{-1}} 為 M i {\displaystyleM_{i}} 模 m i {\displaystylem_{i}} 的數論倒數： t i M i ≡ 1 ( mod m i ) , ∀ i ∈ { 1 , 2 , ⋯ , n } . {\displaystylet_{i}M_{i}\equiv1{\pmod{m_{i}}},\;\;\foralli\in\{1,2,\cdots,n\}.} 方程組 ( S ) {\displaystyle(S)} 的通解形式為： x = a 1 t 1 M 1 + a 2 t 2 M 2 + ⋯ + a n t n M n + k M = k M + ∑ i = 1 n a i t i M i , k ∈ Z . {\displaystylex=a_{1}t_{1}M_{1}+a_{2}t_{2}M_{2}+\cdots+a_{n}t_{n}M_{n}+kM=kM+\sum_{i=1}^{n}a_{i}t_{i}M_{i},\quadk\in\mathbb{Z}.} 在模 M {\displaystyleM} 的意義下，方程組 ( S ) {\displaystyle(S)} 只有一個解： x = ∑ i = 1 n a i t i M i . {\displaystylex=\sum_{i=1}^{n}a_{i}t_{i}M_{i}.} 證明[編輯] 從假設可知，對任何 i ∈ { 1 , 2 , ⋯ , n } {\displaystylei\in\{1,2,\cdots,n\}} ，由於 ∀ j ∈ { 1 , 2 , ⋯ , n } , j ≠ i , gcd ⁡ ( m i , m j ) = 1 {\displaystyle\forallj\in\{1,2,\cdots,n\},\;j\neqi,\;\;\operatorname{gcd}(m_{i},m_{j})=1} ，所以 gcd ⁡ ( m i , M i ) = 1. {\displaystyle\operatorname{gcd}(m_{i},M_{i})=1.} 這說明存在整數 t i {\displaystylet_{i}} 使得 t i M i ≡ 1 ( mod m i ) . {\displaystylet_{i}M_{i}\equiv1{\pmod{m_{i}}}.} 這樣的 t i {\displaystylet_{i}} 叫做 M i {\displaystyleM_{i}} 模 m i {\displaystylem_{i}} 的數論倒數。

觀察乘積 a i t i M i {\displaystylea_{i}t_{i}M_{i}} 可知： a i t i M i ≡ a i ⋅ 1 = a i ( mod m i ) , {\displaystylea_{i}t_{i}M_{i}\equiva_{i}\cdot1=a_{i}{\pmod{m_{i}}},} ∀ j ∈ { 1 , 2 , ⋯ , n } , j ≠ i , a j t j M j ≡ 0 ( mod m i ) . {\displaystyle\forallj\in\{1,2,\cdots,n\},\;j\neqi,\;\;a_{j}t_{j}M_{j}\equiv0{\pmod{m_{i}}}.} 所以 x = a 1 t 1 M 1 + a 2 t 2 M 2 + ⋯ + a n t n M n {\displaystylex=a_{1}t_{1}M_{1}+a_{2}t_{2}M_{2}+\cdots+a_{n}t_{n}M_{n}} 滿足： ∀ i ∈ { 1 , 2 , ⋯ , n } , x = a i t i M i + ∑ j ≠ i a j t j M j ≡ a i + ∑ j ≠ i 0 = a i ( mod m i ) . {\displaystyle\foralli\in\{1,2,\cdots,n\},\;\;x=a_{i}t_{i}M_{i}+\sum_{j\neqi}a_{j}t_{j}M_{j}\equiva_{i}+\sum_{j\neqi}0=a_{i}{\pmod{m_{i}}}.} 這說明 x {\displaystylex} 就是方程組 ( S ) {\displaystyle(S)} 的一個解。

另外，假設 x 1 {\displaystylex_{1}} 和 x 2 {\displaystylex_{2}} 都是方程組 ( S ) {\displaystyle(S)} 的解，那麼： ∀ i ∈ { 1 , 2 , ⋯ , n } , x 1 − x 2 ≡ 0 ( mod m i ) . {\displaystyle\foralli\in\{1,2,\cdots,n\},\;\;x_{1}-x_{2}\equiv0{\pmod{m_{i}}}.} 而 m 1 , m 2 , … , m n {\displaystylem_{1},m_{2},\ldots,m_{n}} 兩兩互質，這說明 M = ∏ i = 1 n m i {\displaystyleM=\prod_{i=1}^{n}m_{i}} 整除 x 1 − x 2 {\displaystylex_{1}-x_{2}} .所以方程組 ( S ) {\displaystyle(S)} 的任何兩個解之間必然相差 M {\displaystyleM} 的整數倍。

而另一方面， x = a 1 t 1 M 1 + a 2 t 2 M 2 + ⋯ + a n t n M n {\displaystylex=a_{1}t_{1}M_{1}+a_{2}t_{2}M_{2}+\cdots+a_{n}t_{n}M_{n}} 是一個解，同時所有形式為： a 1 t 1 M 1 + a 2 t 2 M 2 + ⋯ + a n t n M n + k M = k M + ∑ i = 1 n a i t i M i , k ∈ Z {\displaystylea_{1}t_{1}M_{1}+a_{2}t_{2}M_{2}+\cdots+a_{n}t_{n}M_{n}+kM=kM+\sum_{i=1}^{n}a_{i}t_{i}M_{i},\quadk\in\mathbb{Z}} 的整數也是方程組 ( S ) {\displaystyle(S)} 的解。

所以方程組 ( S ) {\displaystyle(S)} 所有的解的集合就是： { k M + ∑ i = 1 n a i t i M i ; k ∈ Z } . {\displaystyle\{kM+\sum_{i=1}^{n}a_{i}t_{i}M_{i}\;;\quadk\in\mathbb{Z}\}.} 例子[編輯] 使用中國剩餘定理來求解上面的「物不知數」問題，便可以理解《孫子歌訣》中的數字含義。

這裡的線性同餘方程組是： ( S ) : { x ≡ 2 ( mod 3 ) x ≡ 3 ( mod 5 ) x ≡ 2 ( mod 7 ) {\displaystyle(S):\quad\left\{{\begin{matrix}x\equiv2{\pmod{3}}\\x\equiv3{\pmod{5}}\\x\equiv2{\pmod{7}}\end{matrix}}\right.} 三個模數m1 = {\displaystyle=} 3,m2 = {\displaystyle=} 5,m3 = {\displaystyle=} 7的乘積是M = {\displaystyle=} 105，對應的M1 = {\displaystyle=} 35,M2 = {\displaystyle=} 21,M3 = {\displaystyle=} 15.而可以計算出相應的數論倒數：t1 = {\displaystyle=} 2,t2 = {\displaystyle=} 1,t3 = {\displaystyle=} 1.所以《孫子歌訣》中的70、21和15其實是這個「物不知數」問題的基礎解： 70 = 2 × 35 ≡ { 1 ( mod 3 ) 0 ( mod 5 ) 0 ( mod 7 ) , 21 = 1 × 21 ≡ { 0 ( mod 3 ) 1 ( mod 5 ) 0 ( mod 7 ) , 15 = 1 × 15 ≡ { 0 ( mod 3 ) 0 ( mod 5 ) 1 ( mod 7 ) , {\displaystyle70=2\times35\equiv\left\{{\begin{matrix}1{\pmod{3}}\\0{\pmod{5}}\\0{\pmod{7}}\end{matrix}},\right.21=1\times21\equiv\left\{{\begin{matrix}0{\pmod{3}}\\1{\pmod{5}}\\0{\pmod{7}}\end{matrix}},\right.15=1\times15\equiv\left\{{\begin{matrix}0{\pmod{3}}\\0{\pmod{5}}\\1{\pmod{7}}\end{matrix}},\right.} 而將原方程組中的餘數相應地乘到這三個基礎解上，再加起來，其和就是原方程組的解： 2 × 70 + 3 × 21 + 2 × 15 ≡ { 2 × 1 + 3 × 0 + 2 × 0 ≡ 2 ( mod 3 ) 2 × 0 + 3 × 1 + 2 × 0 ≡ 3 ( mod 5 ) 2 × 0 + 3 × 0 + 2 × 1 ≡ 2 ( mod 7 ) , {\displaystyle2\times70+3\times21+2\times15\equiv\left\{{\begin{matrix}2\times1+3\times0+2\times0\equiv2{\pmod{3}}\\2\times0+3\times1+2\times0\equiv3{\pmod{5}}\\2\times0+3\times0+2\times1\equiv2{\pmod{7}}\end{matrix}},\right.} 這個和是233，實際上原方程組的通解公式為： x = 233 + k × 105 , k ∈ Z {\displaystylex=233+k\times105,\;k\in\mathbb{Z}} 《孫子算經》中實際上給出了最小正整數解，也就是 k = − 2 {\displaystylek=-2} 時的解： x = 23 {\displaystylex=23} 。

交換環上的推廣[編輯] 主理想整環[編輯] 設R是一個主理想整環，m1,m2,...,mk是其中的k個元素，並且兩兩互質。

令M = {\displaystyle=} m1m2...mn為這些元素的乘積，那麼可以定義一個從商環R/MR映射到環乘積R/m1R×…× R/mkR的同態： ϕ : R / M R ⟶ R / m 1 R × R / m 2 R × ⋯ × R / m k R {\displaystyle\phi:\;\;\mathrm{R}{\big/}M\mathrm{R}\longrightarrow\mathrm{R}{\big/}m_{1}\mathrm{R}\times\mathrm{R}{\big/}m_{2}\mathrm{R}\times\cdots\times\mathrm{R}{\big/}m_{k}\mathrm{R}} x + M R ↦ ( x + m 1 R , x + m 2 R , ⋯ , x + m k R ) {\displaystyle\left.\;\;x+M\mathrm{R}\;\mapsto\;(x+m_{1}\mathrm{R},x+m_{2}\mathrm{R},\cdots,x+m_{k}\mathrm{R})\right.} 並且 ϕ {\displaystyle\phi} 是一個環同構。

因此 ϕ {\displaystyle\phi} 的逆映射也存在。

而這個逆映射的構造方式就如同中國剩餘定理構造一元線性同餘方程組的解一樣。

由於mi和Mi = {\displaystyle=} M/mi互質，所以存在si和ti使得 s i m i + t i M i = 1 R . {\displaystyles_{i}m_{i}+t_{i}M_{i}=1_{\mathrm{R}}.} 而映射 φ : R / m 1 R × R / m 2 R × ⋯ × R / m k R ⟶ R / M R {\displaystyle\varphi:\;\;\mathrm{R}{\big/}m_{1}\mathrm{R}\times\mathrm{R}{\big/}m_{2}\mathrm{R}\times\cdots\times\mathrm{R}{\big/}m_{k}\mathrm{R}\longrightarrow\mathrm{R}{\big/}M\mathrm{R}} ( a 1 + m 1 R , a 2 + m 2 R , ⋯ , a k + m k R ) ↦ ∑ i = 1 k a i t i M i + M R {\displaystyle\left.\;(a_{1}+m_{1}\mathrm{R},a_{2}+m_{2}\mathrm{R},\cdots,a_{k}+m_{k}\mathrm{R})\;\mapsto\;\sum_{i=1}^{k}a_{i}t_{i}M_{i}+M\mathrm{R}\right.} 就是 ϕ {\displaystyle\phi} 的逆映射。

Z {\displaystyle\mathbb{Z}} 也是一個主理想整環。

將以上的R換成 Z {\displaystyle\mathbb{Z}} ，就能得到中國剩餘定理。

因為 a i + m i R = { x ; x ≡ a i ( mod m i ) } {\displaystylea_{i}+m_{i}\mathrm{R}=\{x;\;x\;\equiv\;a_{i}{\pmod{m_{i}}}\}} 一般的交換環[編輯] 設R是一個有單位元素的交換環，I1,I2,...,Ik是為環 R {\displaystyle\mathbf{R}} 的理想，並且當 i ≠ j {\displaystylei\neqj} 時， I i + I j = R {\displaystyleI_{i}+I_{j}=\mathbf{R}} ，則有典範的環同構： ψ : R / ( I 1 ∩ ⋯ ∩ I k ) ⟶ R / I 1 × ⋯ × R / I k {\displaystyle\psi:\;\;\mathbf{R}/(I_{1}\cap\cdots\capI_{k})\longrightarrow\mathbf{R}/I_{1}\times\cdots\times\mathbf{R}/I_{k}} x + I 1 ∩ ⋯ ∩ I n ⟼ ( x + I 1 , x + I 2 , ⋯ , x + I k ) . {\displaystylex+I_{1}\cap\cdots\capI_{n}\longmapsto(x+I_{1},x+I_{2},\cdots,x+I_{k}).} 模不兩兩互質的同餘式組[編輯] 模不兩兩互質的同餘式組可化為模兩兩互質的同餘式組，再用孫子定理直接求解。

84=22×3×7,160=25×5,63=32×7，由推廣的孫子定理可得 { x ≡ 23 ( mod 84 ) x ≡ 7 ( mod 160 ) x ≡ 2 ( mod 63 ) {\displaystyle{\begin{cases}x\equiv23{\pmod{84}}\\x\equiv7{\pmod{160}}\\x\equiv2{\pmod{63}}\end{cases}}} 與 { x ≡ 7 ( mod 2 5 ) x ≡ 2 ( mod 3 2 ) x ≡ 7 ( mod 5 ) x ≡ 23 ( mod 7 ) {\displaystyle{\begin{cases}x\equiv7{\pmod{2^{5}}}\\x\equiv2{\pmod{3^{2}}}\\x\equiv7{\pmod{5}}\\x\equiv23{\pmod{7}}\end{cases}}} 同解。

[3] 解法 { x ≡ 7 ( mod 2 5 ) x ≡ 2 ( mod 3 2 ) x ≡ 7 ( mod 5 ) x ≡ 23 ( mod 7 ) {\displaystyle{\begin{cases}x\equiv7{\pmod{2^{5}}}\\x\equiv2{\pmod{3^{2}}}\\x\equiv7{\pmod{5}}\\x\equiv23{\pmod{7}}\end{cases}}} → {\displaystyle\rightarrow} { x ≡ 7 ( mod 2 5 ) x ≡ 2 ( mod 3 2 ) x ≡ 2 ( mod 5 ) x ≡ 2 ( mod 7 ) {\displaystyle{\begin{cases}x\equiv7{\pmod{2^{5}}}\\x\equiv2{\pmod{3^{2}}}\\x\equiv2{\pmod{5}}\\x\equiv2{\pmod{7}}\end{cases}}} → {\displaystyle\rightarrow} { x ≡ 7 ( mod 2 5 ) x ≡ 2 ( mod 3 2 × 5 × 7 ) {\displaystyle{\begin{cases}x\equiv7{\pmod{2^{5}}}\\x\equiv2{\pmod{3^{2}\times5\times7}}\\\end{cases}}} 2 5 = 32 {\displaystyle2^{5}=32} 以及 3 2 × 5 × 7 = 315 {\displaystyle3^{2}\times5\times7=315} 315 a ≡ 1 ( mod 32 ) → ( 315 − 32 × 10 ) a ≡ 1 ( mod 32 ) → − 5 a ≡ 1 ( mod 32 ) {\displaystyle315a\equiv1{\pmod{32}}\rightarrow(315-32\times10)a\equiv1{\pmod{32}}\rightarrow-5a\equiv1{\pmod{32}}} ，取數論倒數 a = − 13 {\displaystylea=-13} 32 b ≡ 1 ( mod 315 ) → 32 b ≡ 1 + 315 × 13 ( mod 315 ) → 32 b ≡ 4096 ( mod 315 ) {\displaystyle32b\equiv1{\pmod{315}}\rightarrow32b\equiv1+315\times13{\pmod{315}}\rightarrow32b\equiv4096{\pmod{315}}} ，因 gcd ( 32 , 315 ) = 1 {\displaystyle\gcd(32,315)=1} ，故兩邊可同除以32，取數論倒數 b = 4096 32 = 128 {\displaystyleb={\frac{4096}{32}}=128} 315 × ( − 13 ) × 7 + 32 × 128 × 2 = − 20473 {\displaystyle315\times(-13)\times7+32\times128\times2=-20473} − 20473 ≡ 9767 ( mod 32 × 315 ) {\displaystyle-20473\equiv9767{\pmod{32\times315}}} 所以最小正整數解為 9767 {\displaystyle9767} ，通解為 x = 9767 + 10080 k , k ∈ Z {\displaystylex=9767+10080k,k\in\mathbb{Z}} 。

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

{ x ≡ 3 ( mod 6 ) x ≡ 4 ( mod 10 ) ⇒ { x ≡ 1 ( mod 2 ) x ≡ 0 ( mod 3 ) x ≡ 0 ( mod 2 ) x ≡ 4 ( mod 5 ) {\displaystyle{\begin{cases}x\equiv3{\pmod{6}}\\x\equiv4{\pmod{10}}\\\end{cases}}\Rightarrow{\begin{cases}{\color{Red}x\equiv1{\pmod{2}}}\\x\equiv0{\pmod{3}}\\{\color{Red}x\equiv0{\pmod{2}}}\\x\equiv4{\pmod{5}}\\\end{cases}}} 參見[編輯] 哈瑟原則 參考資料[編輯] ^古代战术计谋中的现代数学.www.solidot.org.[2021-11-03].  ^李儼《大衍求一術的過去和未來》《李儼.錢寶琮科學史全集》卷6121頁《程大位的孫子歌》遼寧教育出版社.1998 ^劉古勝徐東星余暢.推广的孙子定理.高師理科學刊.2010,(3)[2014-01-07].（原始內容存檔於2020-03-27）.  參考書目 數學的100個基本問題，靳平主編，ISBN7-5377-2171-8 取自「https://zh.wikipedia.org/w/index.php?title=中国剩余定理&oldid=70544111」 分類：​同餘數學定理隱藏分類：​使用ISBN魔術連結的頁面 導覽選單 個人工具 沒有登入討論貢獻建立帳號登入 命名空間 條目討論 臺灣正體 不转换简体繁體大陆简体香港繁體澳門繁體大马简体新加坡简体臺灣正體 查看 閱讀編輯檢視歷史 更多 搜尋 導航 首頁分類索引特色內容新聞動態近期變更隨機條目資助維基百科 說明 說明維基社群方針與指引互助客棧知識問答字詞轉換IRC即時聊天聯絡我們關於維基百科 工具 連結至此的頁面相關變更上傳檔案特殊頁面靜態連結頁面資訊引用此頁面維基數據項目 列印/匯出 下載為PDF可列印版 其他專案 維基學院 其他語言 العربيةCatalàČeštinaDeutschΕλληνικάEnglishEsperantoEspañolEuskaraفارسیSuomiFrançaisעבריתहिन्दीHrvatskiMagyarՀայերենBahasaIndonesiaItaliano日本語Қазақша한국어LombardМонголNederlandsPolskiPortuguêsRomânăРусскийSimpleEnglishSlovenčinaSlovenščinaShqipSvenskaУкраїнськаاردوTiếngViệt文言粵語 編輯連結