中国剩余定理证明

中国剩余定理

"剩余倍分法"互除余一 互除少一

证明"孙子定理"不完善 不稳定的表现

作者：张景刚 zhangyi003@yahoo.cn

www.sxcopyright.com 2008.08.08

孙子定理：

例 解同余式组

解 因3，5，7两两互质，故可由孙子定理给出解答， ＝3 5 7＝105，

故由孙子定理，所给同余式的解为： ≡2 35 2+1 21 3+1 15 2（mod 105）即

≡23（mod 105）。

以上孙子定理的解法，是计算出乘率×衍数×余数各项相加，减去两个乘积而得到的一个数，它不完善且解法较为复杂，普及应用有一定难度，还不稳定。

用"剩余倍分法"把"孙子定理"简化成一般解法，使剩余问题获解时，即有正基数，也有负基数，有正余数，也有负余数。互除余1能解，互除少1也能解（不限制大余数问题），把其解法转化成一般算法、使它完善，稳定可普及应用。

用潘成洞，潘成彪2005《北京大学出版社》157页，简明数论一题论述：

例 X≡3（mod8）

X≡1（mod5）

X≡1（mod3） 答案X≡－29（mod120）

用"剩余倍分法"简化式对比计算，答案□=91。

3……1

□÷ 5……1

8……3

根据反证法：下式余数的少数，是上式（例4÷3=商1余1，如果=商2就少2）的"补充数"，称负余数。

3……1少2

□ ÷5……1少4

8……3少5

用倍分法计算出正、负基数：

正基数 40 ＋96＋105 = 241

除 数 3 × 5 × 8 = 120

负基数 80 ＋24 ＋15 = 119

用式方法一解：余数×基数各项相加，除以乘积余数既是。

① 正基数，正余数

（1×40＋1×96＋3×105）÷（3×5×8）

=451÷120……91

② 正基数，负余数

（2×40＋4×96＋5×105）÷（3×5×8）

=989÷120……29

③ 负基数，负余数

（2×80＋4×24＋5×15）÷（3×5×8）

=331÷120……91

④ 负基数，正余数

（1×80＋1×24＋3×15）÷（3×5×8）

=149÷120……29

显然用29还原 加余数，减少数，不符合题意，用负－29还原符合题意减余数，加少数，但－29来历隐性明显，说服力不强。（低级学校不能接受）

用91还原减余数，加少数，符合题意，91为正确答案。

以上解法与"孙子定律"基本相同，但是有两种答案。

如果用"剩余倍分法"互除余一 互除少一计算不存在以上两个答案。

用方法二解：

① 用正基数，正余数

（3×□＋1）÷5=□……1

｛6（5＋1－1）＋1｝÷（5×3）

=31÷15……1

（15×□＋1）÷8=□……3

｛105（8＋3-1）＋1｝÷（8×15）

=1051÷120……91

方法二解：

③ 用正基数，负余数

（3×□－2）÷5=□…－4

｛6（5－4＋2）－2｝÷（3×5）

=16÷15……1

（15×□＋1）÷8=□…－5

｛105（8－5－1）＋1｝÷（8×15）

=211÷120……91

方法三解：

② 负基数，负余数

（3×□－2）÷5=□…－4

｛9（5＋4－2）－2｝÷（3×5）

=61÷15……1

（15×□＋1）÷8=□…－5

｛15（8＋5＋1）＋1｝÷（8×15）

=211÷120……91

方法三解：

④ 负基数，正余数

（3×□＋1）÷5=□……1

｛9（5－1＋1）＋1｝÷（5×3）

=46÷15……1

（15×□＋1）÷8=□……3

｛15（8－3＋1）＋1｝÷（8×15）

=91÷120……91

答案□=91

再证，用"剩余倍分法"解："物不知数"

3……2

□÷ 5……3

7……2

根据反证法：下式余数的少数，是上式（例5÷3=商1余2，如果=商2就少1）的"补充数"，称负余数。

3……2少1

□÷5……3少2

7……2少5

用倍分法计算出正、负基数：

正基数70＋21＋15=106

除 数 3× 5× 7 =105

负基数35＋84＋90=209

用式剩余倍分法、方法一解：余数×基数各项相加，处以乘积余数既是。

① 用正基数,正余数解：

（2×70＋3×21＋2×15）÷（3×5×7）

=233÷105……23

② 用正基数，负余数解：

（1×70＋2×21＋5×15）÷（3×5×7）

=187÷105……82

③ 负基数，负余数解

（1×35＋2×84＋5×90）÷（3×5×7）

=653÷105……23

④ 负基数，正余数解：

（1×35＋2×84＋5×90）÷（3×5×7）

=502÷105……82

用23还原减余数，加少数。

用82还原加余数，减少数。用-82还原减余，加少数。（低级学校不能接受）

以上解法与"孙子定律"基本相同，但是有两种答案。

如果用"剩余倍分法"互除余一 互除少一计算不存在以上两个答案。

方法二解：

① 用正基数，正余数

（3×□＋2）÷5=□……3

｛6（5＋3－2）＋2｝÷（5×3）

=38÷15……8

（15×□＋8）÷7=□……2

｛15（7＋2-8）＋8｝÷（7×15）

=23÷105……23

方法二解

② 用正基数，负余数

（3×□－1）÷5=□…－2

｛6（5－2＋1）－1｝÷（3×5）

=23÷15……8

（15×□＋8）÷7=□…－5

｛15（7－5－8）＋8｝÷（7×15）（据说明：7可以扩大2倍数）

=23÷105……23

方法三解：

③ 负基数，负余数

（3×□－1）÷5=□…－2

｛9（5＋2－1）－1｝÷（3×5）

=53÷15……8

（15×□＋8）÷7=□…－5

｛90（7＋5＋8）＋8｝÷（7×15）

=1808÷105……23

方法三解

④ 负基数，正余数

（3×□＋2）÷5=□……3

｛9（5－3＋2）＋2｝÷（5×3）

=38÷15……8

（15×□＋8）÷7=□……2

｛90（7－2＋8）＋8｝÷（7×15）

=1178÷105……23

答案□=23

从以上对比认为"孙子定理"，解法复杂，有时还不稳定，"剩余倍分法"不管在那种情况下都稳定，且解法简单，便于普及推广，更适用于解应用题。

例： 一个住校生，家里每星期给他36元生活费。该生每天实际只用生活费5元，某天他小姨到学校看他并给了50元钱，他用此钱买了两本喜爱的课外读物花10元，买学习用具花2元，放假回家后说明情况并给家长交回55元。

问：该生带几个星期的生活费？实际在校住几天？一共有多少钱？花去多少钱？

用方法二解：

列式（36×□＋50－10－2）÷5＝□……55元

｛36×（5＋55-50＋10＋2）＋50－10－2｝÷（5×36）

＝（36×22＋50－10－2）÷180

＝830÷180……110

答; 1，（110－50＋10＋2）÷36＝2， （括号内□内最小数）

2，（110－55）÷5＝11， （括号外□内最小数）

3 36×2＋50＝122，

4，122－55＝67。

答：该生带2个星期的生活费，实际住校11天，一共有122元，花去67元。

用孙子定理（即中国剩余定理）列表解决：

这题可由孙子定理算出，设该数为x，列出同余方程：

x≡2(mod3);x≡3(mod5);x≡2(mod7)

列表解答：

除数 余数 最小公倍数 衍数 乘率 各总 答数

3 2 5*7 2 35*2*2=140 140+

5 3 3*5*7=105 7*3 1 21*1*3=63 63+30

7 2 5*3 1 15*1*2=30 =233

所以最小答数为233除以105的余数：233-2*105=23

于是x≡23(mod 105)

这个数最小为23