中国剩余定理

中國剩余定理，又稱中國餘數定理，是数论中的一個关于一元线性同余方程组的定理，说明了一元线性同余方程组有解的准则以及求解方法。也称为孫子定理，古有「韓信點兵」、「孫子定理」、「求一术」（宋沈括）、「鬼谷算」（宋周密）、「隔墻算」（宋 周密）、「剪管術」（宋杨辉）、「秦王暗點兵」、「物不知數」之名。

目录

• 
  1 物不知数
  


• 
  2 形式描述
  
  
  
  • 
    2.1 证明
    
  
  
  
  


• 
  3 例子
  


• 
  4 交换环上的推广
  
  
  
  • 
    4.1 主理想整环
    
  
  
  • 
    4.2 一般的交换环
    
  
  
  
  


• 
  5 模不两两互质的同余式组
  


• 
  6 参见
  


• 
  7 参考资料
  

物不知数

一元线性同余方程组问题最早可见于中國南北朝时期（公元5世纪）的數學著作《孫子算經》卷下第二十六题，叫做“物不知數”问题，原文如下：
.mw-parser-output .templatequote{margin-top:0;overflow:hidden}.mw-parser-output .templatequote .templatequotecite{line-height:1em;text-align:left;padding-left:2em;margin-top:0}.mw-parser-output .templatequote .templatequotecite cite{font-size:small}

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

即，一個整數除以三余二，除以五余三，除以七余二，求這個整數。《孫子算經》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

宋朝数学家秦九韶于1247年《数书九章》卷一、二《大衍类》对“物不知数”问题做出了完整系统的解答。明朝数学家程大位在《算法统宗》中将解法编成易于上口的《孙子歌诀》^[1]：

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

这个歌诀给出了模数为3、5、7时候的同余方程的秦九韶解法。意思是：将除以3得到的余数乘以70，将除以5得到的余数乘以21，将除以7得到的余数乘以15，全部加起来後再减去105或者105的整数倍，得到的数就是答案（除以105得到的余数则为最小答案）。比如说在以上的物不知数问题里面，使用以上的方法计算就得到

70×2+21×3+15×2=233=2×105+23.{displaystyle 70times 2+21times 3+15times 2=233=2times 105+23.}

因此按歌诀求出的结果就是23.

形式描述

用现代数学的语言来说明的话，中国剩余定理给出了以下的一元线性同余方程组：

(S):{x≡a1(modm1)x≡a2(modm2)⋮x≡an(modmn){displaystyle (S):quad left{{begin{matrix}xequiv a_{1}{pmod {m_{1}}}\xequiv a_{2}{pmod {m_{2}}}\vdots qquad qquad qquad \xequiv a_{n}{pmod {m_{n}}}end{matrix}}right.}

有解的判定条件，并用构造法给出了在有解情况下解的具体形式。

中国剩余定理说明：假设整数m₁, m₂, ... , m_n其中任两數互质，则对任意的整数：a₁, a₂, ... , a_n，方程组(S){displaystyle (S)}有解，并且通解可以用如下方式构造得到：

1. 设M=m1×m2×⋯×mn=∏i=1nmi{displaystyle M=m_{1}times m_{2}times cdots times m_{n}=prod _{i=1}^{n}m_{i}}是整数m₁, m₂, ... , m_n的乘积，并设Mi=M/mi,∀i∈{1,2,⋯,n}{displaystyle M_{i}=M/m_{i},;;forall iin {1,2,cdots ,n}}，即Mi{displaystyle M_{i}}是除了m_i以外的n − 1个整数的乘积。


2. 设ti=Mi−1{displaystyle t_{i}=M_{i}^{-1}}为Mi{displaystyle M_{i}}模mi{displaystyle m_{i}}的数论倒数：tiMi≡1(modmi),∀i∈{1,2,⋯,n}.{displaystyle t_{i}M_{i}equiv 1{pmod {m_{i}}},;;forall iin {1,2,cdots ,n}.}
   


3. 方程组(S){displaystyle (S)}的通解形式为：x=a1t1M1+a2t2M2+⋯+antnMn+kM=kM+∑i=1naitiMi,k∈Z.{displaystyle x=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},quad kin mathbb {Z} .} 在模M{displaystyle M}的意义下，方程组(S){displaystyle (S)}只有一个解：x=∑i=1naitiMi.{displaystyle x=sum _{i=1}^{n}a_{i}t_{i}M_{i}.}
   

证明

从假设可知，对任何i∈{1,2,⋯,n}{displaystyle iin {1,2,cdots ,n}}，由于∀j∈{1,2,⋯,n},j≠i,gcd⁡(mi,mj)=1{displaystyle forall jin {1,2,cdots ,n},;jneq i,;;operatorname {gcd} (m_{i},m_{j})=1}，所以gcd⁡(mi,Mi)=1.{displaystyle operatorname {gcd} (m_{i},M_{i})=1.} 这说明存在整数ti{displaystyle t_{i}}使得tiMi≡1(modmi).{displaystyle t_{i}M_{i}equiv 1{pmod {m_{i}}}.} 这样的ti{displaystyle t_{i}}叫做Mi{displaystyle M_{i}}模mi{displaystyle m_{i}}的数论倒数。考察乘积aitiMi{displaystyle a_{i}t_{i}M_{i}}可知：

aitiMi≡ai⋅1≡ai(modmi),{displaystyle a_{i}t_{i}M_{i}equiv a_{i}cdot 1equiv a_{i}{pmod {m_{i}}},}

∀j∈{1,2,⋯,n},j≠i,aitiMi≡0(modmj).{displaystyle forall jin {1,2,cdots ,n},;jneq i,;;a_{i}t_{i}M_{i}equiv 0{pmod {m_{j}}}.}

所以x=a1t1M1+a2t2M2+⋯+antnMn{displaystyle x=a_{1}t_{1}M_{1}+a_{2}t_{2}M_{2}+cdots +a_{n}t_{n}M_{n}}满足：

∀i∈{1,2,⋯,n},x=aitiMi+∑j≠iajtjMj≡ai+∑j≠i0≡ai(modmi).{displaystyle forall iin {1,2,cdots ,n},;;x=a_{i}t_{i}M_{i}+sum _{jneq i}a_{j}t_{j}M_{j}equiv a_{i}+sum _{jneq i}0equiv a_{i}{pmod {m_{i}}}.}

这说明x{displaystyle x}就是方程组(S){displaystyle (S)}的一个解。

另外，假设x1{displaystyle x_{1}}和x2{displaystyle x_{2}}都是方程组(S){displaystyle (S)}的解，那么：

∀i∈{1,2,⋯,n},x1−x2≡0(modmi).{displaystyle forall iin {1,2,cdots ,n},;;x_{1}-x_{2}equiv 0{pmod {m_{i}}}.}

而m1,m2,…,mn{displaystyle m_{1},m_{2},ldots ,m_{n}}两两互质，这说明M=∏i=1nmi{displaystyle M=prod _{i=1}^{n}m_{i}}整除x1−x2{displaystyle x_{1}-x_{2}}. 所以方程组(S){displaystyle (S)}的任何两个解之间必然相差M{displaystyle M}的整数倍。而另一方面，x=a1t1M1+a2t2M2+⋯+antnMn{displaystyle x=a_{1}t_{1}M_{1}+a_{2}t_{2}M_{2}+cdots +a_{n}t_{n}M_{n}}是一个解，同时所有形式为：

a1t1M1+a2t2M2+⋯+antnMn+kM=kM+∑i=1naitiMi,k∈Z{displaystyle 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},quad kin mathbb {Z} }

的整数也是方程组(S){displaystyle (S)}的解。所以方程组(S){displaystyle (S)}所有的解的集合就是：

{kM+∑i=1naitiMi;k∈Z}.{displaystyle {kM+sum _{i=1}^{n}a_{i}t_{i}M_{i};;quad kin mathbb {Z} }.}

例子

使用中国剩余定理来求解上面的“物不知数”问题，便可以理解《孙子歌诀》中的数字含义。这里的线性同余方程组是：

(S):{x≡2(mod3)x≡3(mod5)x≡2(mod7){displaystyle (S):quad left{{begin{matrix}xequiv 2{pmod {3}}\xequiv 3{pmod {5}}\xequiv 2{pmod {7}}end{matrix}}right.}

三个模数m₁={displaystyle =}3, m₂={displaystyle =}5, m₃={displaystyle =}7的乘积是M={displaystyle =}105，对应的M₁={displaystyle =}35, M₂={displaystyle =}21, M₃={displaystyle =}15. 而可以计算出相应的数论倒数：t₁={displaystyle =}2, t₂={displaystyle =}1, t₃={displaystyle =}1. 所以《孙子歌诀》中的70，21和15其实是这个“物不知数”问题的基础解：

70=2×35≡{1(mod3)0(mod5)0(mod7),21=1×21≡{0(mod3)1(mod5)0(mod7),15=1×15≡{0(mod3)0(mod5)1(mod7),{displaystyle 70=2times 35equiv left{{begin{matrix}1{pmod {3}}\0{pmod {5}}\0{pmod {7}}end{matrix}},right.21=1times 21equiv left{{begin{matrix}0{pmod {3}}\1{pmod {5}}\0{pmod {7}}end{matrix}},right.15=1times 15equiv 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(mod3)2×0+3×1+2×0≡3(mod5)2×0+3×0+2×1≡2(mod7),{displaystyle 2times 70+3times 21+2times 15equiv left{{begin{matrix}2times 1+3times 0+2times 0equiv 2{pmod {3}}\2times 0+3times 1+2times 0equiv 3{pmod {5}}\2times 0+3times 0+2times 1equiv 2{pmod {7}}end{matrix}},right.}

这个和是233，实际上原方程组的通解公式为：

x=233+k×105,k∈Z.{displaystyle x=233+ktimes 105,;kin mathbb {Z} .}

《孙子算经》中实际上给出了最小正整数解，也就是k={displaystyle =}-2时的解：x={displaystyle =}23.

交换环上的推广

主理想整环

设R是一个主理想整环，m₁, m₂, ... , m_k是其中的k个元素，并且两两互质。令M={displaystyle =}m₁m₂...m_n为这些元素的乘积，那么可以定义一个从商环R/MR映射到环乘积R/m₁R × … × R/m_kR的同态：

ϕ:R/MR⟶R/m1R×R/m2R×⋯×R/mkR{displaystyle phi :;;mathrm {R} {big /}Mmathrm {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+MR↦(x+m1R,x+m2R,⋯,x+mkR){displaystyle left.;;x+Mmathrm {R} ;mapsto ;(x+m_{1}mathrm {R} ,x+m_{2}mathrm {R} ,cdots ,x+m_{k}mathrm {R} )right.}

并且ϕ{displaystyle phi }是一个环同构。因此ϕ{displaystyle phi }的逆映射也存在。而这个逆映射的构造方式就如同中国剩余定理构造一元线性同余方程组的解一样。由于m_i和M_i={displaystyle =}M/m_i互质，所以存在s_i和t_i使得

simi+tiMi=1R.{displaystyle s_{i}m_{i}+t_{i}M_{i}=1_{mathrm {R} }.}

而映射

φ:R/m1R×R/m2R×⋯×R/mkR⟶R/MR{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 /}Mmathrm {R} }

(a1+m1R,a2+m2R,⋯,ak+mkR)↦∑i=1kaitiMi+MR{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}+Mmathrm {R} right.}

就是ϕ{displaystyle phi }的逆映射。

Z{displaystyle mathbb {Z} }也是一个主理想整环。将以上的R换成Z{displaystyle mathbb {Z} }，就能得到中国剩余定理。因为

ai+miR={x;x≡ai(modmi)}{displaystyle a_{i}+m_{i}mathrm {R} ={x;;x;equiv ;a_{i}{pmod {m_{i}}}}}

一般的交换环

设R是一个有单位元的交换环，I₁, I₂, ... , I_k是为环R{displaystyle mathbf {R} }的理想，并且当i≠j{displaystyle ineq j}时，Ii+Ij=R{displaystyle I_{i}+I_{j}=mathbf {R} }，则有典范的环同构：

ψ:R/(I1∩⋯∩Ik)⟶R/I1×⋯×R/Ik{displaystyle psi :;;mathbf {R} /(I_{1}cap cdots cap I_{k})longrightarrow mathbf {R} /I_{1}times cdots times mathbf {R} /I_{k}}

x+I1∩⋯∩In⟼(x+I1,x+I2,⋯,x+Ik).{displaystyle x+I_{1}cap cdots cap I_{n}longmapsto (x+I_{1},x+I_{2},cdots ,x+I_{k}).}

模不两两互质的同余式组

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

84=2²×3×7,160=2⁵×5,63=3²×7，由推广的孙子定理可得
{x≡23(mod84)x≡7(mod160)x≡2(mod63){displaystyle {begin{cases}xequiv 23{pmod {84}}\xequiv 7{pmod {160}}\xequiv 2{pmod {63}}end{cases}}}
与
{x≡7(mod25)x≡2(mod32)x≡7(mod5)x≡23(mod7){displaystyle {begin{cases}xequiv 7{pmod {2^{5}}}\xequiv 2{pmod {3^{2}}}\xequiv 7{pmod {5}}\xequiv 23{pmod {7}}end{cases}}}
同解。^[2]

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

{x≡3(mod6)x≡4(mod10)⇒{x≡1(mod2)x≡0(mod3)x≡0(mod2)x≡4(mod5){displaystyle {begin{cases}xequiv 3{pmod {6}}\xequiv 4{pmod {10}}\end{cases}}Rightarrow {begin{cases}{color {Red}xequiv 1{pmod {2}}}\xequiv 0{pmod {3}}\{color {Red}xequiv 0{pmod {2}}}\xequiv 4{pmod {5}}\end{cases}}}

参见

• 哈瑟原则

参考资料

1. 
   ^ 李俨《大衍求一术的过去和未来》《李俨.钱宝琮科学史全集》卷6 121页《程大位的孙子歌》辽宁教育出版社. 1998
   


2. 
   ^ 刘古胜 徐东星 余畅. 推广的孙子定理. 高师理科学刊. 2010, (3). 
   

参考书目

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

This page is only for reference, If you need detailed information, please check here