﻿ 孙子定理的一个证明

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

Abstract: A proof of Chinese Remainder Theorem is given.

1. 引言

$x\equiv 2\left(\mathrm{mod}3\right),x\equiv 3\left(\mathrm{mod}5\right),x\equiv 2\left(\mathrm{mod}7\right)$.

$x\equiv 2×70+3×21+2×15\equiv 233\equiv 23\left(\mathrm{mod}105\right)$.

2. 主要结果及应用

$m={m}_{1}{m}_{2}\cdots {m}_{k},m={m}_{i}{M}_{i},i=1,2,\cdots ,k$ ,

$x\equiv {b}_{1}\left(\mathrm{mod}{m}_{1}\right),x\equiv {b}_{2}\left(\mathrm{mod}{m}_{2}\right),\cdots ,x\equiv {b}_{k}\left(\mathrm{mod}{m}_{k}\right)$. (1)

$x\equiv {{M}^{\prime }}_{1}{M}_{1}{b}_{1}+{{M}^{\prime }}_{2}{M}_{2}{b}_{2}+\cdots +{{M}^{\prime }}_{k}{M}_{k}{b}_{k}\left(\mathrm{mod}m\right)$ , (2)

${{M}^{\prime }}_{i}{M}_{i}\equiv 1\left(\mathrm{mod}{m}_{i}\right),i=1,2,\cdots ,k$. (3)

${{M}^{\prime }}_{i}{M}_{i}x\equiv {{M}^{\prime }}_{i}{M}_{i}{b}_{i}\left(\mathrm{mod}{m}_{i}\right),i=1,2,\cdots ,k$.

$\left({{M}^{\prime }}_{1}{M}_{1}+\cdots +{{M}^{\prime }}_{k}{M}_{k}\right)x\equiv {{M}^{\prime }}_{1}{M}_{1}{b}_{1}+\cdots +{{M}^{\prime }}_{k}{M}_{k}{b}_{k}\left(\mathrm{mod}{m}_{i}\right),i=1,2,\cdots ,k$.

$\left({{M}^{\prime }}_{1}{M}_{1}+\cdots +{{M}^{\prime }}_{k}{M}_{k}\right)x\equiv {{M}^{\prime }}_{1}{M}_{1}{b}_{1}+\cdots +{{M}^{\prime }}_{k}{M}_{k}{b}_{k}\left(\mathrm{mod}m\right)$. (4)

${{M}^{\prime }}_{i}\left(i=1,2,\cdots ,k\right)$ 满足(3)式，故

${{M}^{\prime }}_{1}{M}_{1}+{{M}^{\prime }}_{2}{M}_{2}+\cdots +{{M}^{\prime }}_{k}{M}_{k}\equiv 1\left(\mathrm{mod}{m}_{i}\right),i=1,2,\cdots ,k$. (5)

${m}_{1},{m}_{2},\cdots ,{m}_{k}$ 两两互质，故由(5)式得

${{M}^{\prime }}_{1}{M}_{1}+{{M}^{\prime }}_{2}{M}_{2}+\cdots +{{M}^{\prime }}_{k}{M}_{k}\equiv 1\left(\mathrm{mod}m\right)$ (6)

$\begin{array}{c}x\equiv {{M}^{\prime }}_{1}{M}_{1}{b}_{1}+{{M}^{\prime }}_{2}{M}_{2}{b}_{2}+\cdots +{{M}^{\prime }}_{k}{M}_{k}{b}_{k}\\ \equiv {{M}^{\prime }}_{i}{M}_{i}{b}_{i}\equiv {b}_{i}\left(\mathrm{mod}{m}_{i}\right),i=1,\cdots ,k\end{array}$.

$x\equiv {c}_{1}+{M}_{1}{c}_{2}+{M}_{2}{c}_{3}+\cdots +{M}_{k-1}{c}_{k}\left(\mathrm{mod}m\right)$ , (7)

${M}_{i}={m}_{1}{m}_{2}\cdots {m}_{i},i=1,2,\cdots ,k$ , (8)

$m={M}_{k}$

(9)

${{M}^{\prime }}_{i}{M}_{i}\equiv 1\left(\mathrm{mod}{m}_{i+1}\right),i=1,2,\cdots ,k-1$. (10)

${c}_{1}+{M}_{1}{c}_{2}+{M}_{2}{c}_{3}+\cdots +{M}_{k-1}{c}_{k}\equiv {b}_{i}\left(\mathrm{mod}{m}_{i}\right),i=1,2,\cdots ,k$. (11)

$\begin{array}{l}{c}_{1}+{M}_{1}{c}_{2}+{M}_{2}{c}_{3}+\cdots +{M}_{k-1}{c}_{k}\equiv {c}_{1}+{M}_{1}{c}_{2}+\cdots +{M}_{i-2}{c}_{i-1}+{M}_{i-1}{c}_{i}\\ \equiv {c}_{1}+{M}_{1}{c}_{2}+\cdots +{M}_{i-2}{c}_{i-1}+{M}_{i-1}\cdot {{M}^{\prime }}_{i-1}\left[{b}_{i}-\left({c}_{1}+{M}_{1}{c}_{2}+\cdots +{M}_{i-2}{c}_{i-1}\right)\right]\\ \equiv {c}_{1}+{M}_{1}{c}_{2}+\cdots +{M}_{i-2}{c}_{i-1}+1\cdot \left[{b}_{i}-\left({c}_{1}+{M}_{1}{c}_{2}+\cdots +{M}_{i-2}{c}_{i-1}\right)\right]={b}_{i}\left(\mathrm{mod}{m}_{i}\right)\end{array}$.

$x\equiv {b}_{i}\left(\mathrm{mod}{m}_{i}\right),i=1,2,\cdots ,k$. (12)

$x\equiv {c}_{1}+{M}_{1}{c}_{2}+{M}_{2}{c}_{3}+\cdots +{M}_{k-1}{c}_{k}\left(\mathrm{mod}{m}_{i}\right),i=1,2,\cdots ,k$.

${m}_{1},{m}_{2},\cdots ,{m}_{k}$ 两两互质，故(7)式成立。

$x\equiv {c}_{1}+{M}_{1}{c}_{2}+{M}_{2}{c}_{3}+\cdots +{M}_{k-1}{c}_{k}\left(\mathrm{mod}{m}_{i}\right),i=1,2,\cdots ,k$. (13)

${{M}^{\prime }}_{i}{M}_{i}\equiv 1\left(\mathrm{mod}{m}_{i+1}\right),i=1,2,\cdots ,k-1$ ,

${c}_{1}$${b}_{1}$${m}_{1}$ 除所得的余数， ${c}_{2}$${{M}^{\prime }}_{1}\left({b}_{2}-{c}_{1}\right)$${m}_{2}$ 除所得的余数， ${c}_{3}$${{M}^{\prime }}_{2}\left[{b}_{3}-\left({c}_{1}+{M}_{1}{c}_{2}\right)\right]$${m}_{3}$ 除所得的余数， $\cdots$${{M}^{\prime }}_{k-1}\left[{b}_{k}-\left({c}_{1}+{M}_{1}{c}_{2}+\cdots +{M}_{k-2}{c}_{k-1}\right)\right]$${m}_{k}$ 除所得的余数，则同余式组(1)的解为

$x\equiv {c}_{1}+{M}_{1}{c}_{2}+\cdots +{M}_{k-1}{c}_{k}\left(\mathrm{mod}m\right)$ , (14)

$0\le {c}_{1}+{M}_{1}{c}_{2}+\cdots +{M}_{k-1}{c}_{k}\le m-1$.

$0\le {c}_{1}+{M}_{1}{c}_{2}\le {m}_{1}-1+{M}_{1}\left({m}_{2}-1\right)={M}_{1}-1+{M}_{1}\left({m}_{2}-1\right)={M}_{2}-1$ ,

$0\le {c}_{1}+{M}_{1}{c}_{2}+{M}_{2}{c}_{3}\le {M}_{2}-1+{M}_{2}\left({m}_{3}-1\right)={M}_{3}-1$ ,

$\cdots$

$0\le {c}_{1}+{M}_{1}{c}_{2}+\cdots +{M}_{k-1}{c}_{k}\le {M}_{k-1}-1+{M}_{k-1}\left({m}_{k}-1\right)={M}_{k}-1=m-1$.

$x\equiv 1\left(\mathrm{mod}3\right),x\equiv -1\left(\mathrm{mod}5\right),x\equiv 2\left(\mathrm{mod}7\right),x\equiv -2\left(\mathrm{mod}11\right)$.

$x\equiv -2\left(\mathrm{mod}11\right),x\equiv 2\left(\mathrm{mod}7\right),x\equiv -1\left(\mathrm{mod}5\right),x\equiv 1\left(\mathrm{mod}3\right)$.

$\begin{array}{l}{M}_{1}={m}_{1}=11,{M}_{2}={m}_{1}{m}_{2}=11×7=77,\\ {M}_{3}={m}_{1}{m}_{2}{m}_{3}=77×5=385,\\ {M}_{4}={m}_{1}{m}_{2}{m}_{3}{m}_{4}=385×3=1155=m\end{array}$.

${b}_{1}=-2\equiv 9\left(\mathrm{mod}11\right),{c}_{1}=9.$

${{M}^{\prime }}_{1}\left({b}_{2}-{c}_{1}\right)=2\left(2-9\right)\equiv 0\left(\mathrm{mod}7\right)$${c}_{2}=0$，则

${c}_{1}+{M}_{1}{c}_{2}=9+11×0=9$.

${{M}^{\prime }}_{2}\left[{b}_{3}-\left({c}_{1}+{M}_{1}{c}_{2}\right)\right]=2\left(-1-9\right)\equiv 0\left(\mathrm{mod}5\right)$${c}_{3}=0$，则

${c}_{1}+{M}_{1}{c}_{2}+{M}_{2}{c}_{3}=9+77×0=9$.

${{M}^{\prime }}_{3}\left[{b}_{4}-\left({c}_{1}+{M}_{1}{c}_{2}+{M}_{2}{c}_{3}\right)\right]=1×\left(1-9\right)=-8\equiv 1\left(\mathrm{mod}3\right)$${c}_{4}=1$，则

${c}_{1}+{M}_{1}{c}_{2}+{M}_{2}{c}_{3}+{M}_{3}{c}_{4}=9+385×1=394$.

$x\equiv 394\left(\mathrm{mod}1155\right)$.

$x\equiv {b}_{1}\left(\mathrm{mod}11\right),x\equiv {b}_{2}\left(\mathrm{mod}7\right),x\equiv {b}_{3}\left(\mathrm{mod}6\right),x\equiv {b}_{4}\left(\mathrm{mod}5\right)$.

${M}_{1}={m}_{1}=11,{M}_{2}={m}_{1}{m}_{2}=77,{M}_{3}=462,{M}_{4}=2310=m$.

$11{{M}^{\prime }}_{1}\equiv 1\left(\mathrm{mod}7\right)$${{M}^{\prime }}_{1}=2$

$77{{M}^{\prime }}_{2}\equiv 1\left(\mathrm{mod}6\right)$${{M}^{\prime }}_{2}=-1$

$462{{M}^{\prime }}_{3}\equiv 1\left(\mathrm{mod}5\right)$${{M}^{\prime }}_{3}=-2$

${c}_{1}\equiv {b}_{1}\left(\mathrm{mod}\mathrm{mod}11\right)$${c}_{1}={b}_{1}$

${c}_{2}\equiv {{M}^{\prime }}_{1}\left({b}_{2}-{c}_{1}\right)=2{b}_{2}-2{b}_{1}\left(\mathrm{mod}7\right)$${c}_{2}=2{b}_{2}-2{b}_{1}$，则

${c}_{1}+{M}_{1}{c}_{2}={b}_{1}+11\left(2{b}_{2}-2{b}_{1}\right)=22{b}_{2}-21{b}_{1}$.

${c}_{3}\equiv {{M}^{\prime }}_{2}\left[{b}_{3}-\left({c}_{1}+{M}_{1}{c}_{2}\right)\right]=-\left[{b}_{3}-\left(22{b}_{2}-21{b}_{1}\right)\right]\equiv -{b}_{3}-2{b}_{2}+3{b}_{1}\left(\mathrm{mod}6\right)$${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\left(-{b}_{3}-2{b}_{2}+3{b}_{1}\right)=-77{b}_{3}-132{b}_{2}+210{b}_{1}$.

$\begin{array}{c}{c}_{4}\equiv {{M}^{\prime }}_{3}\left[{b}_{4}-\left({c}_{1}+{M}_{1}{c}_{2}+{M}_{2}{c}_{3}\right)\right]\\ =-2\left[{b}_{4}-\left(-77{b}_{3}-132{b}_{2}+210{b}_{1}\right)\right]\\ \equiv -2{b}_{4}+{b}_{3}+{b}_{2}\left(\mathrm{mod}5\right)\end{array}$ ,

${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\left(-2{b}_{4}+{b}_{3}+{b}_{2}\right)\\ =-924{b}_{4}+385{b}_{3}+330{b}_{2}+210{b}_{1}\end{array}$.

$x\equiv -924{b}_{4}+385{b}_{3}+330{b}_{2}+210{b}_{1}\left(\mathrm{mod}2310\right)$ ,

$x\equiv 1386{b}_{4}+385{b}_{3}+330{b}_{2}+210{b}_{1}\left(\mathrm{mod}2310\right)$.

[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.

Top