物不知数

一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：

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

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

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

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

形式描述

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

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

中国剩余定理说明：假设整数m1, m2, ... , mn其中任两数互质，则对任意的整数：a1, a2, ... , an，方程组 ( S ) {\displaystyle (S)} 有解，并且通解可以用如下方式构造得到：

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

设 t i = M i − − --> 1 {\displaystyle t_{i}=M_{i}^{-1}} 为 M i {\displaystyle M_{i}} 模 m i {\displaystyle m_{i}} 的数论倒数： t i M i ≡ ≡ --> 1 ( mod m i ) , ∀ ∀ --> i ∈ ∈ --> { 1 , 2 , ⋯ ⋯ --> , n } . {\displaystyle t_{i}M_{i}\equiv 1{\pmod {m_{i}}},\;\;\forall i\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 . {\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 k\in \mathbb {Z} .} 在模 M {\displaystyle M} 的意义下，方程组 ( S ) {\displaystyle (S)} 只有一个解： x = ∑ ∑ --> i = 1 n a i t i M i . {\displaystyle x=\sum _{i=1}^{n}a_{i}t_{i}M_{i}.}

证明

从假设可知，对任何 i ∈ ∈ --> { 1 , 2 , ⋯ ⋯ --> , n } {\displaystyle i\in \{1,2,\cdots ,n\}} ，由于 ∀ ∀ --> j ∈ ∈ --> { 1 , 2 , ⋯ ⋯ --> , n } , j ≠ ≠ --> i , gcd ⁡ ⁡ --> ( m i , m j ) = 1 {\displaystyle \forall j\in \{1,2,\cdots ,n\},\;j\neq i,\;\;\operatorname {gcd} (m_{i},m_{j})=1} ，所以 gcd ⁡ ⁡ --> ( m i , M i ) = 1. {\displaystyle \operatorname {gcd} (m_{i},M_{i})=1.} 这说明存在整数 t i {\displaystyle t_{i}} 使得 t i M i ≡ ≡ --> 1 ( mod m i ) . {\displaystyle t_{i}M_{i}\equiv 1{\pmod {m_{i}}}.} 这样的 t i {\displaystyle t_{i}} 叫做 M i {\displaystyle M_{i}} 模 m i {\displaystyle m_{i}} 的数论倒数。考察乘积 a i t i M i {\displaystyle a_{i}t_{i}M_{i}} 可知：

所以 x = a 1 t 1 M 1 + a 2 t 2 M 2 + ⋯ ⋯ --> + a n t n M n {\displaystyle x=a_{1}t_{1}M_{1}+a_{2}t_{2}M_{2}+\cdots +a_{n}t_{n}M_{n}} 满足：

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

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

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

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

例子

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

三个模数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其实是这个“物不知数”问题的基础解：

而将原方程组中的余数相应地乘到这三个基础解上，再加起来，其和就是原方程组的解：

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

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

交换环上的推广

主理想整环

设R是一个主理想整环，m1, m2, ... , mk是其中的k个元素，并且两两互质。令M = {\displaystyle =} m1m2...mn为这些元素的乘积，那么可以定义一个从商环R/MR映射到环乘积R/m1R × … × R/mkR的同态：

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

而映射

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

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

一般的交换环

设R是一个有单位元的交换环，I1, I2, ... , Ik是为环 R {\displaystyle \mathbf {R} } 的理想，并且当 i ≠ ≠ --> j {\displaystyle i\neq j} 时， I i + I j = R {\displaystyle I_{i}+I_{j}=\mathbf {R} } ，则有典同构环同构：

模不两两互质的同余式组

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

84=2×3×7,160=2×5,63=3×7，由推广的孙子定理可得 { x ≡ ≡ --> 23 ( mod 84 ) x ≡ ≡ --> 7 ( mod 160 ) x ≡ ≡ --> 2 ( mod 63 ) {\displaystyle {\begin{cases}x\equiv 23{\pmod {84}}\\x\equiv 7{\pmod {160}}\\x\equiv 2{\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\equiv 7{\pmod {2^{5}}}\\x\equiv 2{\pmod {3^{2}}}\\x\equiv 7{\pmod {5}}\\x\equiv 23{\pmod {7}}\end{cases}}} 同解。

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

{ 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\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}}}

参见

哈瑟原则

参考资料

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

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。