孙子定理的一个证明 A Proof of Chinese Remainder Theorem

doi:10.12677/PM.2019.93034

Pure Mathematics
Vol. 09 No. 03 ( 2019 ), Article ID: 30084 , 5 pages
10.12677/PM.2019.93034

A Proof of Chinese Remainder Theorem

Jiming Yang

●How to Cite this Article

Department of Mathematics, Yuxi Normal University, Yuxi Yunnan

Received: Apr. 14^th, 2019; accepted: Apr. 25^th, 2019; published: May 6^th, 2019

ABSTRACT

A proof of Chinese Remainder Theorem is given.

Keywords:Chinese Remainder Theorem, Proof, Congruence

孙子定理的一个证明

杨继明

玉溪师范学院数学系，云南玉溪

收稿日期：2019年4月14日；录用日期：2019年4月25日；发布日期：2019年5月6日

摘要

本文给出了孙子定理的一个证明。

关键词 :孙子定理，证明，同余式

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

在公元四、五世纪的《孙子算经》中的“物不知数”问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何?”答案为：“23”。这个问题也就是求解同余式组

$x \equiv 2 (\mod 3), x \equiv 3 (\mod 5), x \equiv 2 (\mod 7)$ .

明朝程大位根据孙子算经里所用的方法用歌谣给出了该题的解法：“三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。”即解为

$x \equiv 2 \times 70 + 3 \times 21 + 2 \times 15 \equiv 233 \equiv 23 (\mod 105)$ .

在西方，与《孙子算经》同类的算法，最早见于1202年意大利数学家斐波那契的《算经》。1801年，德国数学家高斯的《算术探究》中，才明确写出了这一问题的求法。

把孙子算经给出的结果加以推广，就得到了著名的孙子定理。孙子定理及其证明参阅 [1] [2] 。文 [3] 给出了一个求解孙子问题的简便方法。文 [4] 研究了一般的线性同余式组的有解判别条件及其求解方法。文 [5] 把线性同余式组、线性不定方程组、线性代数方程组、常系数线性微分方程组和常系数线性差分方程组统一成为了R-模上的方程组，并分别给出了各种方程组的解法。

2. 主要结果及应用

下面的定理1就是著名的孙子定理。

定理1 (孙子定理) 设 $m_{1}, m_{2}, \dots, m_{k}$ 是k个两两互质的正整数，

$m = m_{1} m_{2} \dots m_{k}, m = m_{i} M_{i}, i = 1, 2, \dots, k$ ,

则同余式组

$x \equiv b_{1} (\mod m_{1}), x \equiv b_{2} (\mod m_{2}), \dots, x \equiv b_{k} (\mod m_{k})$ . (1)

的解是

$x \equiv {M^{'}}_{1} M_{1} b_{1} + {M^{'}}_{2} M_{2} b_{2} + \dots + {M^{'}}_{k} M_{k} b_{k} (\mod m)$ , (2)

其中

${M^{'}}_{i} M_{i} \equiv 1 (\mod m_{i}), i = 1, 2, \dots, k$ . (3)

文 [1] 给出了该定理的三种证明方法。下面我们再给出一种证法。

证因 $m_{1}, m_{2}, \dots, m_{k}$ 是k个两两互质的正整数，故 $(M_{i}, m_{i}) = 1, i = 1, 2, \dots, k$ 。于是，满足(3)式的整数是存在的。

要证明同余式组(1)的解是(2)，只需证明(1)式和(2)式等价即可。

设整数x满足(1)式，则 $x \equiv b_{i} (\mod m_{i}), i = 1, 2, \dots, k$ ，从而

${M^{'}}_{i} M_{i} x \equiv {M^{'}}_{i} M_{i} b_{i} (\mod m_{i}), i = 1, 2, \dots, k$ .

因为当 $i \neq j$ 时， $m_{i} | M_{j}$ ，故

$({M^{'}}_{1} M_{1} + \dots + {M^{'}}_{k} M_{k}) x \equiv {M^{'}}_{1} M_{1} b_{1} + \dots + {M^{'}}_{k} M_{k} b_{k} (\mod m_{i}), i = 1, 2, \dots, k$ .

从而

$({M^{'}}_{1} M_{1} + \dots + {M^{'}}_{k} M_{k}) x \equiv {M^{'}}_{1} M_{1} b_{1} + \dots + {M^{'}}_{k} M_{k} b_{k} (\mod m)$ . (4)

因 ${M^{'}}_{i} (i = 1, 2, \dots, k)$ 满足(3)式，故

${M^{'}}_{1} M_{1} + {M^{'}}_{2} M_{2} + \dots + {M^{'}}_{k} M_{k} \equiv 1 (\mod m_{i}), i = 1, 2, \dots, k$ . (5)

因 $m_{1}, m_{2}, \dots, m_{k}$ 两两互质，故由(5)式得

${M^{'}}_{1} M_{1} + {M^{'}}_{2} M_{2} + \dots + {M^{'}}_{k} M_{k} \equiv 1 (\mod m)$ (6)

由(4)和(6)两式即知，(2)式成立。

反之，设整数x满足(2)式，则由 $m_{i} | M_{j} (i \neq j)$ 和(3)式得

$\begin{matrix} x \equiv {M^{'}}_{1} M_{1} b_{1} + {M^{'}}_{2} M_{2} b_{2} + \dots + {M^{'}}_{k} M_{k} b_{k} \\ \equiv {M^{'}}_{i} M_{i} b_{i} \equiv b_{i} (\mod m_{i}), i = 1, \dots, k \end{matrix}$ .

即整数x满足(1)式。

应用定理1求解孙子问题的例子参见文 [1] [2] 。下面给出一个更便于求解孙子问题的方法。

定理2 设 $m_{1}, m_{2}, \dots, m_{k}$ 是k个两两互质的正整数，则同余式组(1)的解为

$x \equiv c_{1} + M_{1} c_{2} + M_{2} c_{3} + \dots + M_{k - 1} c_{k} (\mod m)$ , (7)

其中，

$M_{i} = m_{1} m_{2} \dots m_{i}, i = 1, 2, \dots, k$ , (8)

而 $m = M_{k}$ ，

(9)

${M^{'}}_{i} M_{i} \equiv 1 (\mod m_{i + 1}), i = 1, 2, \dots, k - 1$ . (10)

证因 $m_{1}, m_{2}, \dots, m_{k}$ 两两互质，故满足(10)式的整数 ${M^{'}}_{i}$ 是存在的。首先证明，

$c_{1} + M_{1} c_{2} + M_{2} c_{3} + \dots + M_{k - 1} c_{k} \equiv b_{i} (\mod m_{i}), i = 1, 2, \dots, k$ . (11)

显然， $c_{1} + M_{1} c_{2} + M_{2} c_{3} + \dots + M_{k - 1} c_{k} \equiv b_{i} (\mod m_{i}), i = 1, 2$ ．而当 $3 \leq i \leq k$ 时，由(8)，(9)和(10)式得

$\begin{array}{l} c_{1} + M_{1} c_{2} + M_{2} c_{3} + \dots + M_{k - 1} c_{k} \equiv c_{1} + M_{1} c_{2} + \dots + M_{i - 2} c_{i - 1} + M_{i - 1} c_{i} \\ \equiv c_{1} + M_{1} c_{2} + \dots + M_{i - 2} c_{i - 1} + M_{i - 1} \cdot {M^{'}}_{i - 1} [b_{i} - (c_{1} + M_{1} c_{2} + \dots + M_{i - 2} c_{i - 1})] \\ \equiv c_{1} + M_{1} c_{2} + \dots + M_{i - 2} c_{i - 1} + 1 \cdot [b_{i} - (c_{1} + M_{1} c_{2} + \dots + M_{i - 2} c_{i - 1})] = b_{i} (\mod m_{i}) \end{array}$ .

要证明同余式组(1)的解是(7)，只需证明(1)式和(7)式等价即可。设整数x满足(1)式，则

$x \equiv b_{i} (\mod m_{i}), i = 1, 2, \dots, k$ . (12)

由(11)和(12)式得

$x \equiv c_{1} + M_{1} c_{2} + M_{2} c_{3} + \dots + M_{k - 1} c_{k} (\mod m_{i}), i = 1, 2, \dots, k$ .

但 $m_{1}, m_{2}, \dots, m_{k}$ 两两互质，故(7)式成立。

反之，设整数x 满足(7)式，则

$x \equiv c_{1} + M_{1} c_{2} + M_{2} c_{3} + \dots + M_{k - 1} c_{k} (\mod m_{i}), i = 1, 2, \dots, k$ . (13)

由(11)和(13)式得，(1)式成立。

推论设 $m_{1}, m_{2}, \dots, m_{k}$ 是k个两两互质的正整数， $M_{i} = m_{1} m_{2} \dots m_{i} (i = 1, 2, \dots, k)$ ， $m = M_{k}$ ，整数 ${M^{'}}_{i}$ 满足

${M^{'}}_{i} M_{i} \equiv 1 (\mod m_{i + 1}), i = 1, 2, \dots, k - 1$ ,

$c_{1}$ 是 $b_{1}$ 被 $m_{1}$ 除所得的余数， $c_{2}$ 是 ${M^{'}}_{1} (b_{2} - c_{1})$ 被 $m_{2}$ 除所得的余数， $c_{3}$ 是 ${M^{'}}_{2} [b_{3} - (c_{1} + M_{1} c_{2})]$ 被 $m_{3}$ 除所得的余数， $\dots$ ，是 ${M^{'}}_{k - 1} [b_{k} - (c_{1} + M_{1} c_{2} + \dots + M_{k - 2} c_{k - 1})]$ 被 $m_{k}$ 除所得的余数，则同余式组(1)的解为

$x \equiv c_{1} + M_{1} c_{2} + \dots + M_{k - 1} c_{k} (\mod m)$ , (14)

其中 $0 \leq c_{1} + M_{1} c_{2} + \dots + M_{k - 1} c_{k} \leq m - 1$ 。

证根据定理2，(14)为同余式组(1)的解．下面证明

$0 \leq c_{1} + M_{1} c_{2} + \dots + M_{k - 1} c_{k} \leq m - 1$ .

易知， $0 \leq c_{i} \leq m_{i} - 1, i = 1, 2, \dots, k$ 。故

$0 \leq c_{1} + M_{1} c_{2} \leq m_{1} - 1 + M_{1} (m_{2} - 1) = M_{1} - 1 + M_{1} (m_{2} - 1) = M_{2} - 1$ ,

$0 \leq c_{1} + M_{1} c_{2} + M_{2} c_{3} \leq M_{2} - 1 + M_{2} (m_{3} - 1) = M_{3} - 1$ ,

$\dots$

$0 \leq c_{1} + M_{1} c_{2} + \dots + M_{k - 1} c_{k} \leq M_{k - 1} - 1 + M_{k - 1} (m_{k} - 1) = M_{k} - 1 = m - 1$ .

例1 解同余式组

$x \equiv 1 (\mod 3), x \equiv - 1 (\mod 5), x \equiv 2 (\mod 7), x \equiv - 2 (\mod 11)$ .

解为了更便于应用定理2的推论求解，把这个同余式组改写为

$x \equiv - 2 (\mod 11), x \equiv 2 (\mod 7), x \equiv - 1 (\mod 5), x \equiv 1 (\mod 3)$ .

这里， $m_{1} = 11, m_{2} = 7, m_{3} = 5, m_{4} = 3, b_{1} = - 2, b_{2} = 2, b_{3} = - 1, b_{4} = 1$ 。

$\begin{array}{l} M_{1} = m_{1} = 11, M_{2} = m_{1} m_{2} = 11 \times 7 = 77, \\ M_{3} = m_{1} m_{2} m_{3} = 77 \times 5 = 385, \\ M_{4} = m_{1} m_{2} m_{3} m_{4} = 385 \times 3 = 1155 = m \end{array}$ .

取满足 ${M^{'}}_{1} M_{1} \equiv 1 (\mod m_{2})$ 即 $11 {M^{'}}_{1} \equiv 1 (\mod 7)$ 的一个整数 ${M^{'}}_{1} = 2$ 。

取满足 ${M^{'}}_{2} M_{2} \equiv 1 (\mod m_{3})$ 即 $77 {M^{'}}_{2} \equiv 1 (\mod 5)$ 的一个整数 ${M^{'}}_{2} = - 2$ 。

取满足 ${M^{'}}_{3} M_{3} \equiv 1 (\mod m_{4})$ 即 $385 {M^{'}}_{3} \equiv 1 (\mod 3)$ 的一个整数 ${M^{'}}_{3} = 1$ 。

$b_{1} = - 2 \equiv 9 (\mod 11), c_{1} = 9.$

${M^{'}}_{1} (b_{2} - c_{1}) = 2 (2 - 9) \equiv 0 (\mod 7)$ ， $c_{2} = 0$ ，则

$c_{1} + M_{1} c_{2} = 9 + 11 \times 0 = 9$ .

${M^{'}}_{2} [b_{3} - (c_{1} + M_{1} c_{2})] = 2 (- 1 - 9) \equiv 0 (\mod 5)$ ， $c_{3} = 0$ ，则

$c_{1} + M_{1} c_{2} + M_{2} c_{3} = 9 + 77 \times 0 = 9$ .

${M^{'}}_{3} [b_{4} - (c_{1} + M_{1} c_{2} + M_{2} c_{3})] = 1 \times (1 - 9) = - 8 \equiv 1 (\mod 3)$ ， $c_{4} = 1$ ，则

$c_{1} + M_{1} c_{2} + M_{2} c_{3} + M_{3} c_{4} = 9 + 385 \times 1 = 394$ .

故由定理2的推论得，该同余式组的解为

$x \equiv 394 (\mod 1155)$ .

例2 解同余式组

$x \equiv b_{1} (\mod 11), x \equiv b_{2} (\mod 7), x \equiv b_{3} (\mod 6), x \equiv b_{4} (\mod 5)$ .

解这里 $m_{1} = 11, m_{2} = 7, m_{3} = 6, m_{4} = 5$ ，

$M_{1} = m_{1} = 11, M_{2} = m_{1} m_{2} = 77, M_{3} = 462, M_{4} = 2310 = m$ .

由 $11 {M^{'}}_{1} \equiv 1 (\mod 7)$ 取 ${M^{'}}_{1} = 2$ 。

由 $77 {M^{'}}_{2} \equiv 1 (\mod 6)$ 取 ${M^{'}}_{2} = - 1$ 。

由 $462 {M^{'}}_{3} \equiv 1 (\mod 5)$ 取 ${M^{'}}_{3} = - 2$ 。

由 $c_{1} \equiv b_{1} (\mod \mod 11)$ 取 $c_{1} = b_{1}$ 。

由 $c_{2} \equiv {M^{'}}_{1} (b_{2} - c_{1}) = 2 b_{2} - 2 b_{1} (\mod 7)$ 取 $c_{2} = 2 b_{2} - 2 b_{1}$ ，则

$c_{1} + M_{1} c_{2} = b_{1} + 11 (2 b_{2} - 2 b_{1}) = 22 b_{2} - 21 b_{1}$ .

由

$c_{3} \equiv {M^{'}}_{2} [b_{3} - (c_{1} + M_{1} c_{2})] = - [b_{3} - (22 b_{2} - 21 b_{1})] \equiv - b_{3} - 2 b_{2} + 3 b_{1} (\mod 6)$ 取 $c_{3} = - b_{3} - 2 b_{2} + 3 b_{1}$ ，则

$c_{1} + M_{1} c_{2} + M_{2} c_{3} = 22 b_{2} - 21 b_{1} + 77 (- b_{3} - 2 b_{2} + 3 b_{1}) = - 77 b_{3} - 132 b_{2} + 210 b_{1}$ .

由

$\begin{matrix} c_{4} \equiv {M^{'}}_{3} [b_{4} - (c_{1} + M_{1} c_{2} + M_{2} c_{3})] \\ = - 2 [b_{4} - (- 77 b_{3} - 132 b_{2} + 210 b_{1})] \\ \equiv - 2 b_{4} + b_{3} + b_{2} (\mod 5) \end{matrix}$ ,

取 $c_{4} = - 2 b_{4} + b_{3} + b_{2}$ ，则

$\begin{array}{l} c_{1} + M_{1} c_{2} + M_{2} c_{3} + M_{3} c_{4} \\ = - 77 b_{3} - 132 b_{2} + 210 b_{1} + 462 (- 2 b_{4} + b_{3} + b_{2}) \\ = - 924 b_{4} + 385 b_{3} + 330 b_{2} + 210 b_{1} \end{array}$ .

故由定理2得，同余式组的解为

$x \equiv - 924 b_{4} + 385 b_{3} + 330 b_{2} + 210 b_{1} (\mod 2310)$ ,

即

$x \equiv 1386 b_{4} + 385 b_{3} + 330 b_{2} + 210 b_{1} (\mod 2310)$ .

文章引用

杨继明. 孙子定理的一个证明
A Proof of Chinese Remainder Theorem[J]. 理论数学, 2019, 09(03): 265-269. https://doi.org/10.12677/PM.2019.93034

参考文献

1. 潘承洞, 潘承彪. 初等数论(第二版) [M]. 北京: 北京大学出版社, 2003.

2. 闵嗣鹤, 严士健. 初等数论(第三版) [M]. 北京: 高等教育出版社, 2003.

3. 杨继明. 解一元线性同余式组的一个简便方法[J]. 抚州师专学报(自然科学版), 1996(3): 22-23.

4. 杨继明, 李桂仙. 关于线性不定方程组与线性同余式组[J]. 甘肃教育学院学报(自然科学版), 2000, 14(2): 16-21.

5. 杨继明. 关于R-模上的方程组[J]. 南都学坛, 1994, 14(6): 18-25.

期刊菜单