查看“︁中国剩余定理”︁的源代码

{{noteTA|G1=Math}}

'''中國剩餘定理'''，又稱'''孫子定理'''或'''中國餘數定理'''，是[[数论]]中的一個关于一元线性[[同余]]方程组的定理，说明了一元线性同余方程组有解的准则以及求解方法。该定理在中国古代也被称为「[[韓信]]點兵」、「求一术」（宋 [[沈括]]）、「鬼谷算」（宋 [[周密]]）、「隔-{zh-cn:墻;zh-tw:牆;}-算」（宋 周密）、「剪管術」（宋 [[杨辉]]）、「[[秦始皇|秦王]]暗點兵」、「物不知數」等。

== 物不知数 ==
一元线性同余方程组问题最早可见于中國[[南北朝]]时期（公元5世纪）的数学著作《[[孫子算經]]》卷下第二十六题，叫做“物不知數”问题，原文如下：
{{quote|有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？}}
即，一個整數[[除以三]]-{zh-cn:余;zh-tw:餘;}-二，除以五-{zh-cn:余;zh-tw:餘;}-三，除以七-{zh-cn:余;zh-tw:餘;}-二，求這個整數。《[[孙子算经|孫子算經]]》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。孫子沒正式證明，但後來印度數學家及天文學家[[阿耶波多]]給出具體過程，徹底解決了此定理的任何給定實例。<ref>{{Cite web|title=奇客Solidot {{!}} 古代战术计谋中的现代数学|url=https://www.solidot.org/story?sid=68940|access-date=2021-11-03|work=www.solidot.org|archive-date=2021-11-18|archive-url=https://web.archive.org/web/20211118170558/https://www.solidot.org/story?sid=68940}}</ref>

最初对“物不知数”问题作出完整系统解答的是宋朝数学家[[秦九韶]]，载于1247年《[[数书九章]]》卷一、二《大衍类》中，从而使这一问题变为定理。明朝数学家[[程大位]]在《[[算法统宗]]》中将解法编成易于上口的《孙子歌诀》<ref>李俨《大衍求一术的过去和未来》《李俨.钱宝琮科学史全集》卷6 121页《程大位的孙子歌》辽宁教育出版社. 1998</ref>：
{{quote|三人同行七十稀，五樹梅花廿一支，七子團圓正半月，除百零五便得知}}
这个歌诀给出了模数为3、5、7时候的同余方程的秦九韶解法。意思是：将[[除以3]]得到的余数乘以70，将除以5得到的余数乘以21，将除以7得到的余数乘以15，全部加起来後再减去105或者105的整数倍，得到的数就是答案（除以105得到的余数则为最小答案）。比如说在以上的物不知数问题里面，使用以上的方法计算就得到
:<math>70 \times 2 + 21 \times 3 + 15 \times 2 = 233 = 2\times 105 +23.</math>
因此按歌诀求出的结果就是23。

《数书九章》最初由[[偉烈亞力|伟烈亚力]]在19世纪初译为英文，而[[西方世界]]最早的完整系统解法由[[卡爾·弗里德里希·高斯|高斯]]在1801年提出。

== 形式描述 ==
用现代数学的语言来说明的话，中国剩余定理给出了以下的一元线性同余方程组：
:<math>(S) : \quad \left\{ \begin{matrix} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ \vdots \qquad\qquad\qquad \\ x \equiv a_n \pmod {m_n} \end{matrix} \right.</math>
有解的判定条件，并用[[构造法]]给出了在有解情况下解的具体形式。

中国剩余定理说明：假设[[整数]]{{math|''m''<sub>1</sub>, ''m''<sub>2</sub>, ... , ''m''<sub>n</sub>}}其中任两數[[互质]]，则对任意的整数：{{math|''a''<sub>1</sub>, ''a''<sub>2</sub>, ... , ''a''<sub>n</sub>}}，方程组<math>(S)</math>有解，并且通解可以用如下方式构造得到：
#设<math>M = m_1 \times m_2 \times \cdots \times m_n = \prod_{i=1}^n m_i</math>是整数{{math|''m''<sub>1</sub>, ''m''<sub>2</sub>, ... , ''m''<sub>n</sub>}}的乘积，并设<math>M_i = M/m_i, \; \; \forall i \in \{1, 2, \cdots , n\}</math>，即<math>M_i</math>是除了<math>m_i</math>以外的<math>n-1</math>个整数的乘积。
#设<math>t_i = M_i^{-1}</math>为<math>M_i</math>模<math>m_i</math>的[[数论倒数]]：<math>t_i M_i \equiv 1 \pmod {m_i},  \; \; \forall i \in \{1, 2, \cdots , n\}.</math>
#方程组<math>(S)</math>的通解形式为：<math>x = a_1 t_1 M_1 + a_2 t_2 M_2 + \cdots + a_n t_n M_n + k M= k M + \sum_{i=1}^n a_i t_i M_i, \quad k \in \mathbb{Z}.</math> 在模<math>M</math>的意义下，方程组<math>(S)</math>只有一个解：<math>x = \sum_{i=1}^n a_i t_i M_i.</math>

===证明===
从假设可知，对任何<math>i \in \{1, 2, \cdots , n\}</math>，由于<math>\forall j \in \{1, 2, \cdots , n\}, \; j\neq i, \; \; \operatorname{gcd}(m_i, m_j) = 1 </math>，所以<math>\operatorname{gcd}(m_i, M_i) = 1.</math> 这说明存在整数<math>t_i</math>使得<math>t_i M_i \equiv 1 \pmod {m_i}.</math> 这样的<math>t_i</math>叫做<math>M_i</math>模<math>m_i</math>的数论倒数。觀察乘积<math>a_i t_i M_i</math>可知：
:<math>a_i t_i M_i \equiv a_i \cdot 1 = a_i \pmod {m_i}, </math>
:<math>\forall j \in \{1, 2, \cdots , n\}, \; j\neq i, \; \; a_j t_j M_j \equiv 0 \pmod {m_i}. </math>
所以<math>x = a_1 t_1 M_1 + a_2 t_2 M_2 + \cdots + a_n t_n M_n</math>满足：
:<math>\forall i \in \{1, 2, \cdots , n\}, \; \; x = a_i t_i M_i + \sum_{j \neq i} a_j t_j M_j \equiv a_i + \sum_{j \neq i} 0 = a_i \pmod {m_i}. </math>
这说明<math>x</math>就是方程组<math>(S)</math>的一个解。

另外，假设<math>x_1</math>和<math>x_2</math>都是方程组<math>(S)</math>的解，那么：
:<math>\forall i \in \{1, 2, \cdots , n\}, \; \;  x_1 - x_2 \equiv 0 \pmod {m_i} .</math>
而<math>m_1, m_2, \ldots, m_n</math>两两互质，这说明<math>M =\prod_{i=1}^n m_i</math>整除<math>x_1 - x_2</math>. 所以方程组<math>(S)</math>的任何两个解之间必然相差<math>M</math>的整数倍。而另一方面，<math>x = a_1 t_1 M_1 + a_2 t_2 M_2 + \cdots + a_n t_n M_n</math>是一个解，同时所有形式为：
:<math>a_1 t_1 M_1 + a_2 t_2 M_2 + \cdots + a_n t_n M_n + k M= k M + \sum_{i=1}^n a_i t_i M_i, \quad k \in \mathbb{Z}</math>
的整数也是方程组<math>(S)</math>的解。所以方程组<math>(S)</math>所有的解的集合就是：
:<math>\{k M + \sum_{i=1}^n a_i t_i M_i  \; ; \quad k \in \mathbb{Z} \}. </math>

==例子==
使用中国剩余定理来求解上面的“物不知数”问题，便可以理解《孙子歌诀》中的数字含义。这里的线性同余方程组是：
:<math>(S) : \quad \left\{ \begin{matrix} x \equiv 2 \pmod {3} \\ x \equiv 3 \pmod {5} \\ x \equiv 2 \pmod {7} \end{matrix} \right.</math>
三个模数 {{math|''m''<sub>1</sub>}}<math>=</math>3, {{math|''m''<sub>2</sub>}}<math>=</math>5, {{math|''m''<sub>3</sub>}}<math>=</math>7 的乘积是 {{math|''M''}}<math>=</math>105，对应的 {{math|''M''<sub>1</sub>}}<math>=</math>35, {{math|''M''<sub>2</sub>}}<math>=</math>21, {{math|''M''<sub>3</sub>}}<math>=</math>15. 而可以计算出相应的数论倒数：{{math|''t''<sub>1</sub>}}<math>=</math>2, {{math|''t''<sub>2</sub>}}<math>=</math>1, {{math|''t''<sub>3</sub>}}<math>=</math>1. 所以《孙子歌诀》中的 70、21 和 15 其实是这个“物不知数”问题的基础解：
:<math>70 = 2 \times 35 \equiv  \left\{  \begin{matrix}  1 \pmod {3} \\ 0 \pmod {5} \\  0 \pmod {7} \end{matrix} , \right. 21 = 1 \times 21  \equiv \left\{ \begin{matrix}  0 \pmod {3} \\ 1 \pmod {5} \\  0 \pmod {7} \end{matrix} , \right. 15 = 1 \times 15 \equiv \left\{ \begin{matrix} 0 \pmod {3} \\  0 \pmod {5} \\  1 \pmod {7} \end{matrix} , \right.</math>
而将原方程组中的余数相应地乘到这三个基础解上，再加起来，其和就是原方程组的解：
:<math>2\times 70 + 3 \times 21 + 2 \times 15  \equiv  \left\{  \begin{matrix}  2 \times 1 + 3 \times 0 + 2 \times 0 \equiv 2 \pmod {3} \\  2 \times 0 + 3 \times 1 + 2 \times 0 \equiv 3 \pmod {5} \\  2 \times 0 + 3 \times 0 + 2 \times 1 \equiv 2 \pmod {7} \end{matrix} , \right. </math>
这个和是 233，实际上原方程组的通解公式为：
:<math>x = 233 + k \times 105, \; k\in \mathbb{Z} </math>
《孙子算经》中实际上给出了最小正整数解，也就是 <math>k=-2</math> 时的解：<math>x=23</math>。

== 交换环上的推广 ==
===主理想整环===
设{{math|R}}是一个[[主理想整环]]，{{math|m<sub>1</sub>, m<sub>2</sub>, ... , m<sub>k</sub>}}是其中的{{math|k}}个元素，并且两两互质。令{{math|M}}<math>=</math>{{math|m<sub>1</sub>m<sub>2</sub>...m<sub>n</sub>}}为这些元素的乘积，那么可以定义一个从[[商环]]{{math|R/''M''R}}映射到环乘积{{math|R/''m''<sub>1</sub>R × … × R/''m''<sub>k</sub>R}}的[[同态]]：
:<math>\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}</math>
::<math>\left.  \; \; x + M\mathrm{R}\; \mapsto  \; (x+ m_1 \mathrm{R}, x + m_2 \mathrm{R},\cdots , x+ m_k \mathrm{R} ) \right.</math>
并且<math>\phi</math>是一个[[同构|环同构]]。因此<math>\phi</math>的逆映射也存在。而这个逆映射的构造方式就如同中国剩余定理构造一元线性同余方程组的解一样。由于{{math|m<sub>i</sub>}}和{{math|M<sub>i</sub>}}<math>=</math>{{math|M/m<sub>i</sub>}}互质，所以存在{{math|''s''<sub>i</sub>}}和{{math|''t''<sub>i</sub>}}使得
:<math>s_i m_i + t_i M_i = 1_{\mathrm{R}}.</math>
而映射
:<math>\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} </math>
::<math>\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.</math>
就是<math>\phi</math>的逆映射。

<math>\mathbb{Z}</math>也是一个主理想整环。将以上的{{math|R}}换成<math>\mathbb{Z}</math>，就能得到中国剩余定理。因为
:<math>a_i + m_i \mathrm{R} = \{x ; \; x \; \equiv \; a_i \pmod{m_i} \}</math>
===一般的交换环===
设{{math|R}}是一个有[[单位元]]的[[交换环]]，{{math|''I''<sub>1</sub>, ''I''<sub>2</sub>, ... , ''I''<sub>k</sub>}}是为环<math>\mathbf{R}</math>的[[理想_(环论)|理想]]，并且当<math>i \ne j</math>时，<math>I_i + I_j = \mathbf{R}</math>，则有[[典范]]的环[[同构]]：
:<math>\psi : \; \; \mathbf{R} /( I_1 \cap \cdots \cap I_k) \longrightarrow \mathbf{R} / I_1 \times \cdots \times \mathbf{R}/ I_k</math>
:::<math>x +  I_1 \cap \cdots \cap  I_n \longmapsto (x + I_1 , x + I_2 ,\cdots, x + I_k).</math>

==模不两两互质的同余式组==
模不两两互质的同余式组可化为模两两互质的同余式组，再用孙子定理直接求解。

84=2<sup>2</sup>×3×7,160=2<sup>5</sup>×5,63=3<sup>2</sup>×7，由推广的孙子定理可得
<math>\begin{cases}
x \equiv 23 \pmod{84} \\
x \equiv 7 \pmod{160} \\
x \equiv 2 \pmod{63} 
\end{cases}</math>
与
<math>\begin{cases}
x \equiv 7 \pmod{2^5} \\
x \equiv 2 \pmod{3^2} \\
x \equiv 7 \pmod{5} \\
x \equiv 23 \pmod{7}
\end{cases}</math>
同解。<ref>{{cite journal|author=刘古胜 徐东星 余畅|year=2010|title=推广的孙子定理|journal=高师理科学刊|issue=3|url=http://www.cnki.com.cn/Article/CJFDTotal-GLKX201003013.htm|access-date=2014-01-07|archive-date=2020-03-27|archive-url=https://web.archive.org/web/20200327025712/http://www.cnki.com.cn/Article/CJFDTotal-GLKX201003013.htm|dead-url=no}}</ref>
{{hideH|解法}}
<math>\begin{cases}
x \equiv 7 \pmod{2^5} \\
x \equiv 2 \pmod{3^2} \\
x \equiv 7 \pmod{5} \\
x \equiv 23 \pmod{7}
\end{cases}</math>
<math>\rightarrow</math>
<math>\begin{cases}
x \equiv 7 \pmod{2^5} \\
x \equiv 2 \pmod{3^2} \\
x \equiv 2 \pmod{5} \\
x \equiv 2 \pmod{7}
\end{cases}</math>
<math>\rightarrow</math>
<math>\begin{cases}
x \equiv 7 \pmod{2^5} \\
x \equiv 2 \pmod{3^2 \times 5 \times 7} \\
\end{cases}</math>

<math>2^5=32</math>以及<math>3^2 \times 5 \times 7=315</math>

<math>315a \equiv 1 \pmod{32} \rightarrow  (315-32 \times 10)a \equiv 1 \pmod{32} \rightarrow -5a \equiv 1 \pmod{32}</math>，取數論倒數<math>a=-13</math>

<math>32b \equiv 1 \pmod{315} \rightarrow 32b \equiv 1+315 \times 13 \pmod{315}  \rightarrow 32b \equiv 4096 \pmod{315}</math>，因<math>\gcd(32,315)=1</math> ，故兩邊可同除以32， 取數論倒數<math>b= \frac{4096}{32}=128</math>

<math>315 \times (-13) \times 7 +32 \times 128 \times 2=-20473</math>

<math>-20473 \equiv 9767  \pmod{32 \times 315}</math>

所以最小正整數解為<math>9767</math>，通解為<math>x = 9767 + 10080k, k\in \mathbb{Z} </math>。
{{hideF}}



注意求解过程中应先检查同余式组上是否存在矛盾，存在矛盾的同余式组无解。

<math>\begin{cases}
x \equiv 3 \pmod{6} \\
x \equiv 4 \pmod{10} \\ 
\end{cases}
\Rightarrow
\begin{cases}
{\color{Red}x \equiv 1 \pmod{2}} \\
x \equiv 0 \pmod{3} \\
{\color{Red}x \equiv 0 \pmod{2}} \\
x \equiv 4 \pmod{5} \\  
\end{cases}
</math>

== 参见 ==
*[[哈瑟原则]]

==参考资料==
<references/>

;参考书目 

*''数学的100个基本问题''，靳平 主编，ISBN 7-5377-2171-8

{{authority control}}

[[Category:包含证明的条目]]
[[Category:中国数学发现|Sun, Master]]
[[Category:交換代數]]
[[Category:同余]]
[[Category:数论定理]]