数学建模社区-数学中国
标题:
中国剩余定理新解
[打印本页]
作者:
wangzc1634
时间:
2012-12-25 20:01
标题:
中国剩余定理新解
中国剩余定理新解
! m( p6 @! M G; W1 T9 A
为什么要编写本文？因为，中国剩余定理属于算术问题，算术的特征是准确性和唯一性。编写的目的是为了让人们确认它的准确性和唯一性，探索最简单的计算方法，便于人们推广应用。
0 W- @; N( s7 Z6 x4 |* ?" [
本文的主要内容：1、原题，2、基本原理，3、计算方法比较，4、中国剩余定理的扩展，5、趣谈中国剩余定理。
d. N. T" O6 [
一、原题
5 R9 I3 M6 Y! _4 K
中国剩余定理，又叫孙子定理，原文是：
~6 D0 N( u, D8 U
“《孙子算经》中的题目：有物不知其数，三个一数余二，五个一数余三，七个一数又余二，问该物总数几何？
. |2 r( N1 c' n3 x7 A. L( e
《孙子算经》中的解法：三三数之，取数七十，与余数二相乘；五五数之，取数二十一，与余数三相乘；七七数之，取数十五，与余数二相乘。将诸乘积相加，然后减去一百零五的倍数。”对于这种解法（以下简称前人的计算方法）。
4 C( O D6 U" Y2 p6 j( A
那么，前人计算方法的原理是什么？只有从计算原理，才知道该计算方法是否正确，所求之数是否存在，存在于什么范围之内？计算方法最简单、最方便的是什么？
* ` Y2 \) M+ P) M" e2 Z
中国剩余定理，是从一种现象开始，寻找解决现象的方法。本人认为应该从基础原理开始，便于人们掌握和应用：
6 c- k9 d- N; Z/ m
二、基本原理
' `) [3 R- M# l
1、在整数中，用不同的器具，如2，3，5，7，11，13，17，…，N（素数）量一个固定的数，每一个量器都有一个固定的余数。
( }( M6 o. }- U7 d3 f4 n& N- C
如某数为53，用2，3，5，7进行衡量，有53/2余1，53/3余2，53/5余3，53/7余4，即，53除以2，3，5，7都有一个固定的余数，也只有一个固定的余数。
* P0 G T( s5 Y( f
2、用2，3，5，7，11，13，17，…，N作为器具，每一个量器取一个固定的余数，在2*3*5*7*11*13*17*…*N之内(也就是在除数的最小公倍数之内)，满足这些余数条件的数只有一个（具体分析见后）。
" R" k7 z- g+ v
如用2，3，5，7量M，当M/2余1，M/3余2，M/5余4，M/7余5，得M＝89，89必然存在于2*3*5*7＝210之内，在每210个连续数之内满足M/2余1，M/3余2，M/5余4，M/7余5的数只有一个数，可以用89+210N表示。
/ l1 X. y; x7 u1 ~9 Q. k3 w8 j3 x
必然存在的理由依据：用2，3，5，7，11，13，17，…，N作为器具时。自然数除以2可以取2种余数，余0，余1；除以3可以取3种余数，余0，余1，余2；除以5可以取5种余数，余0，余1，余2，余3，余4；…，除以N可以取N种余数，余0，余1，余2，余3，余4，…，余N-1。不同的余数排列组合共有2*3*5*7*11*13*17*…*N个，正好对应2*3*5*7*11*13*17*…*N之内的数，每一组不同的余数对应这之内的一个数。为什么存在一一对应呢？请看下面的具体计算。
5 p1 g8 f- k* j& ]7 O; V( G' V
3、除以A余C的数，为等差数列C+AN中的数，也只有C+AN中的数满足除以A余C。
" P0 b4 T( h* M! ~
如除以7余3的数，为等差数列3+7N中的数，也只有3+7N中的数满足除以7余3。
9 Z1 z: P+ T+ @5 C( x
4、除以A，B，…，C都余K，称为同余项。满足除以A，B，…，C都余K的数为等差数列K+（A*B*…*C）N，也只有K+（A*B*…*C）N中的数满足分别除以A，B，…，C都余K。
) [8 y. y0 h! ^* H
三、计算方法比较
# ~7 ]. F2 y$ B. b
计算方法，指求除以素数2，3，5，7，11，13，17，…，N各取一个固定的余数，在2*3*5*7*11*13*17*…*N之中，寻找满足这些条件的这一个数的方法。
5 R U2 @! t8 a9 f# I
上面虽然说的是除以素因子2，3，5，7，11，…，N的依次排列，换为不同的素数A，B，C，D，E，…，Z这种说法仍然成立；排列顺序不一定依次，可以按自己的须要，认为怎样计算方便就怎样进行排列。
' W4 j. B1 f4 z4 P. R
解决这一问题，前人有两种方法，本人有一种计算方法，下面以同一个题进行比较：
9 z+ u2 B& X5 f$ Q" i
方法一、
' S0 C9 ]" c% _0 S0 r$ w5 z
前人的计算方法为什么成立？其解题思路为：
. p, {3 r3 S# @! e+ m+ ^% G
令某数为M，令素数为A，B，C，D，…，Z，已知M/A余a，M/B余b，M/C余c，M/D余d，…，M/Z余z。求M=？
4 |6 Q, |4 y9 W4 U$ l4 g
因为A，B，C，D，…，Z为不同的素数，故，B*C*D*…*Z不可能被A整除，有（B*C*D*…*Z）N中取A个连续项，这A个连续项分别除以A的余数必然存在0，1，2，3，…，A-1，每一个余数都不缺少。所以，从这A个连续项中必然能寻找到除以A余1的数。再用除以A余1的这个数*a，其积必然除以A余a，这个除以A余a的数，为能够被素数B*C*D*…*Z整除的数，为第一个数；
2 X+ a8 ^1 l3 l' T" b
再按同样的道理，从A*C*D*…*Z的倍数中寻找除以B余b的数，该数具备被素数A，C，D，…，Z整除的特性，为第二个数；
! g" T8 I& G0 l ^
因为，第一个数除以A余a，第二个数能被素数A，C，D，…，Z整除，即能被A整除，所以，第一个数+第二个数之和，仍然保持除以A余a；
! O9 L: _3 l# l) z( ?* p' ]! U# h
同理，第二个数除以B余b，因第一个数能被B整除，所以，第二个数+第一个数之和，仍然保持除以B余b。即，第一个数+第二个数之和，为满足除以A余a，除以B余b，并且，能被C，D，…，Z整除。
' S$ N5 t& `, O0 Y
按同样的方法，从A*B*D*…*Z的倍数中寻找除以C余c的数，该数具备能被A，B，D，…，Z整除的特性，为第三个数；
5 o' c# c0 M. T( a: ?6 }
因第一个数和第二个数，都能被C整除，故第三个数+（第一个数+第二个数），仍然保持除以C余c；又因第三个数能被A、B整除，所以，（第一个数+第二个数）+第三个数之和，仍然保持除以A余a，除以B余b。即第一个数+第二个数+第三个数之和，为除以A余a，除以B余b，除以C余c的数，而且，能被素数D，…，Z整除的数；
3 Q1 \$ V! [+ R) _" o |
依此类推，按上面的方法寻找到除以各素数余数的数之总和，为满足除以各素数余数的条件的数。总和再减去能被这几个素数共同整除的数（A*B*C*D*…*Z）N后，其差仍然保持除以各素数余数的条件的数。由此构成前人对中国剩余定理的解法。
. k1 H/ p( R: p
例：某数为M，M/3余2，M/5余4，M/7余3，M/11余6，求M＝？
6 G3 V; T' S- W t3 k
解：
7 L# a% ~ P" R+ O& P6 ~6 o
1、5*7*11＝385，对385N取3项：385，770，1155，因385/3余1，有385*2＝770，为除以3余2的数；
, }9 i* X0 _3 p2 _- V
2、3*7*11＝231，对231N取5项：231，462，693，924，1155，因231/5余1，有231*4＝924，为除以5余4的数；
' j5 T) v$ Y- e
3、3*5*11＝165，对165N取7项：165，330，495，660，825，990，1155，有330/7余1，得330*3＝990，为除以7余3的数；
+ o8 L- @. q& M& v! [' M) d9 P# D
4、3*5*7＝105，对105N取11项：105，210，315，420，525，630，735，840，945，1050，1155，因210/11余1，有210*6＝1260，为除以11余5的数；
* X# o6 e- |6 g' y+ B
5、770+924+990+1260＝3944，因3*5*7*11＝1155，3944/1155余479，即479为满足这些条件的数。
. H: r4 B- [: I6 G$ y& w8 J
其实，前人的计算方法，完全可以简化一个步骤，直接寻找满足余数条件的数，省略一步乘以余数得寻找之数：
6 [3 }) N$ s( {2 c# e- y7 h
1、5*7*11＝385，对385N取3项：385，770，1155，因770/3余2；
& e& ?& y3 G, z* A5 ?
2、3*7*11＝231，对231N取5项：231，462，693，924，1155，因924/5余4；
& z/ n: K: P7 [& E4 }3 i
3、3*5*11＝165，对165N取7项：165，330，495，660，825，990，1155，因990/7余3；
: }$ _0 C; W* l
4、3*5*7＝105，对105N取11项：105，210，315，420，525，630，735，840，945，1050，1155，因105/11余6。
$ ~& L+ a$ E9 F% {
5、770+924+990+105＝2789，因3*5*7*11＝1155，2789/1155余479，即479为满足这些条件的数。
3 Y. \; r1 \: _( u1 k# _$ T
方法二、
; F6 m5 i, E5 v- [8 _& N
除以3余2为等差数列2+3N有：2，5，8，11，14，…，479，…，1154，要取5*7*11＝385项，
/ a/ q; x( m- ^6 s
除以5余4为等差数列4+5N有：4，9，14，19，…，479，…，1154，要取3*7*11＝231项。
. q- w+ ]( A! D: m. E. `5 R
除以7余3为等差数列3+7N有：3，10，17，24，…，479，…，1151，要取3*5*11＝165项，
0 N9 O& u4 ^% R3 X }( T3 G4 T
除以11余6为等差数列6+11N有：5，16，27，38，…，479，…，1149，要取3*5*7＝105项。
U# Y9 ^" U- o& g% B8 M: ~
因4个等差数列在1155内，只有479都同时存在，所以，只有479为满足这些条件的数。
/ ^) W+ Z5 v3 Z. p& V/ k( R
方法二对于计算较大的剩余数，很不适用，不可取。
, a+ p4 ~8 f- d/ l2 O2 e; x6 |( q; w, X
本人的方法：
& c; v6 ?! v7 `7 l5 G
该计算方法，可以直观地说明剩余数在范围内存在的必然性和唯一性。我们边计算，边说明。
j. i# ^4 Y7 h5 G1 Q5 d L1 N* U
(1)，初步计算：
# j6 o3 B1 b x, |
对于素数11来说，1，2，3，4，5，6，7，8，9，10，11，在这11个连续数中，只有6除以11余6，满足除以11余6为等差数列6+11N；
0 x3 R( q8 D$ ]/ |! F
素数7，对6+11N取7项，6，17，28，39，50，61，72，这7个数除以7余1，2，3，4，5，6，0都存在，这就是存在的必然性；只有17/7余3，这就是唯一性。因11*7＝77，即在77之内满足除以11余6，除以7余3的数只有17，满足这两个条件的数为17+77N，表明每77个连续数之内只有一个数满足这两个条件。
6 v1 G+ C0 J2 b; o% T
素数5，对17+77N取5项：17，94，171，248，325，这5个数除以5余1，2，3，4，0都存在，这就是存在的必然性；只有94除以5余4，这就是唯一性。因77*5＝385，即在385之内满足除以11余6，除以7余3，除以5余4的数只有94，满足这三个条件的数为94+385N，表明每385个连续数中只有一个数满足这三个条件。
* z( P* w2 D/ Q, `# y" Z
素数3，对94+385N取3项：94，479，864，这3个数除以3余1，2，0都存在，这就是存在的必然性；只有479除以3余2，这就是唯一性。因385*3＝1155，满足这4个条件的数为479+1155N，表明每1155个连续数中只有一个数满足这四个条件，也必然有一个数满足这四个条件。
! p9 L- T" _) b5 [5 H8 ^. |: D
(二)，简化计算(该方法实用于计算大数)：
S5 I) K' g2 a+ U" V3 D9 W
1，素数11，除以11余6为等差数列6+11Ｎ；
+ c1 E2 ~9 t0 y3 @4 G! y: S
2，素数7，将等差数列6+11Ｎ的首项和公差同除以7的余数为6和4，组成新的等差数列6+4Ｎ，取7项之内必然有除以7余3的数，第一项6，第二项(6+4)-7＝3，当出现与余数相同的数时，就不需要再往下计算了。代入原等差数列6+11*(2-1)＝17，因11*7＝77，得新的等差数列17+77Ｎ；
9 K$ M' U Z: `, e; h
3，素数5，将17+77Ｎ同除以5变为2+2Ｎ，取5项之内：2，4，得第二项满足条件，代入有17+77＝94，因77*5＝385，得新的等差数列94+385Ｎ；
0 L0 s3 Z; q# F
4，素数3，将94+385Ｎ同除以3变为1+1Ｎ，取3项之内：1，2，得第二项满足条件，代入有94+385＝497，因11*7*3*5＝1155，即497+1155Ｎ数列的数都满足这4个条件。
- T* {6 N" b& F5 s$ u: l8 L
本人的这种方法，是在3+5+7+11＝26个数之内，寻找在1155之内满足除以这4个素数余数条件的数，这种方法也叫滚雪球的方法，容易理解、操作都比前人的简单、方便。
0 X2 K; c6 s! L) S
2 V. a8 r* i4 W( x q$ n
方法二、同余的解法：
2 d* M% H4 n0 X% z, b
例M/5余3，M/11余4，M/19余3，M/29余4，M/37余3，求M＝？
q3 G5 m( y( J- N% ~
M除以5，19，37同余3，满足除以5，19，37都余3为等差数列3+（5*19*37）N，即3+3515N；
$ c. e, N1 y7 R9 M
M除以11，29同余4，满足除以11和29都余4为等差数列4+（11*29）N′，即4+319 N′。
0 n4 J5 F' R6 K- v; {8 W
这里又出现三种解法：
, ]1 P: G1 N Q2 | J3 q6 l
1、将3+3515N取319项，4+319 N′取3515项，共同有之数为此题的解；
5 e) R. e( i5 N/ @- Q' A k
2、将3+3515N取319项，寻找除以319余4的数，为此题的解；
# \, j' Q( r$ [
方法1和2比较烦锁（略）。
6 w: _) K1 q( {* b) E
3、将3+3515N同除以29得等差数列3+6Ｎ取29项之内：3，9，15，21，27，4(当≥29时，减去29再算，下类似)，得第6项除以29余4，代入原等差数列3+3515(6-1)＝17578，因3515*29＝101935，得等差数列17578+101935N。
/ I2 [0 A' Y5 O5 X2 E- L
将等差数列17578+101935N同除以11得等差数列0+9Ｎ，取11项内：0，9，7，5，3，1，10，8，6，4，得第10项除以11余4，代入原等差数列17578+101935*(10-1)＝934993。又因5*11*19*29*37＝1121285，即在1121285之内只有M为934993时，满足M/5余3，M/11余4，M/19余3，M/29余4，M/37余3。等差数列934993+1121285N的数，都满足这些条件。
5 m% |, Y. t0 c ~# W
四、中国剩余定理的扩展
& E9 e' T, W% ]
中国剩余定理在初始阶段，都是除以素数的余数。后来，不可避免地扩展到除以合数的余数问题。当涉及除以合数的余数后，就出现了有的题有解，有的题无解。这到底是为什么？
7 ]/ |: S [+ u& ?7 a8 N
前面说的是除以不同素数的余数，那么，除以任意数的余数是否存在必然性和唯一性呢？
7 r3 }- E! `- Q! N
这里的任意数，不包括0和1，任意数分为单合数、多合数、混合数、素数：
0 j7 q0 r% U5 z8 O; t( J! {! V
单合数，指由单个素因子组成的合数，如8，16等由单个素因子2组成；9，27，81等由单个素因子3组成。
7 V& C2 k: |% q# E& Q+ X
多合数指两个以上不同素因子组成的合数，如30＝2*3*5。
8 }# J/ ~1 s8 R2 D( d6 b
混合数指由单合数与多合数组成的合数，如840＝8*3*5*7。
3 ~/ X5 `4 J* u1 Z
例一，M/16余3，M/105余4，M/11余5，M/3余1，求M＝？
! h Q; W0 `4 {, f7 q1 R! P, W. ^. m
首先审题：16为单个素因子2，105＝3*5*7，还有11，3。这里只有一个重复素因子3，对于单个素因子3已经明确M/3余1；在多合数中M/105余4，用该余数4/3余1，没有矛盾，该题为可解之题。
/ I+ G, I4 N/ S& l
抛开重复素数3后有：16*105*11＝18480，表明在18480内该题有解，有唯一的解：
4 c; Z$ U5 n( Q9 p2 z6 z; r
满足除以105余4为等差数列4+105N，将4+105N化为4+9Ｎ取16项内：4，13，6，15，8，1，10，3，得第8项满足除以16余3，代入原等差数列4+105(8-1)＝739，因105*16＝1680，即在1680内同时满足除以105余4，除以16余3，只有739，得等差数列739+1680N；
/ ]" X" K" J# \' K# y4 l8 D
将该等差数列739+1680N化为2+8Ｎ，取11项：2，10，7，4，1，9，6，3，0，8，5，满足除以11余5为11项，代入的等差数列739+1680(11-1)＝17539，因1680*11＝18480，满足这些条件的数只有17539+18480N等差数列的数。
& J3 T4 k2 |) J
例二，Ｍ/135余37，Ｍ/63余28，Ｍ/105余7，求Ｍ＝？
% j/ f3 S( t% b5 H6 \
这里的135＝3*3*3 *5，63＝3*3*7，105＝3*5*7。单合数有3的平方，3的立方；素数有3，5，7。计算最小公倍数时，单合数取素数Ｎ次方中最高的，即3*3*3＝27，表明该题有除数27，5，7。有27*5*7＝945，那么，满足这些条件的最小数在它们的公倍数945之内。
0 f& u3 r5 u& m8 ~) b
审题：37/3余1，28/3余1，7/3余1；37/5余2，7/5余2；28/7余0，7/7余0。其余数除以素因子的余数，都没有矛盾，表明该题有解。
c- n2 t* a4 L: f# Y6 _+ U1 s5 v8 L9 X
因Ｍ/135包括Ｍ/27和Ｍ/5，所以，该题变为：Ｍ/135余37，Ｍ/7余0。
N7 n# e$ |- t8 j3 U) D
Ｍ/135余37为等差数列37+135Ｎ，化为2+2Ｎ取7项内：2，4，6，1，3，5，0，得第7项除以7余1，代入原等差数列37+135*(7-1)＝847，即847+945Ｎ数列的数都满足这些条件。
/ G% X9 ^3 b) U: A; o& Q1 C o
说明：
5 h1 W5 o$ b+ g5 ~4 I
1、 单个素因子组成的合数是不能拆分的，其除数取素数Ｎ次方中最高的；
3 z$ J Z e) B9 t; s z6 X- U
2、 多个素因子组成的合数是可以拆分的，拆分方法：为总余数除以各素因子；
. ^( ^9 w' n9 x/ z& p# x6 }
3、 重复素因子，应先检验是否有矛盾，无矛盾是可解之题，有矛盾是无解之题；
. j/ T! m' L2 \: X, u! r# v
4、 重复素因子，重复合数，应当抛开重复后，再进行计算。
" Y* M4 R. Q) ?0 q9 g! {% U+ O
再举一个重复数的抛开，如M/105余19，M/165余139，求M＝？
/ v+ O# r Z9 Y* i
审题：105＝3*5*7，165＝3*5*11，两个合数中都有素因子3和5，因总余数19/3余1，139/3余1；19/5余4，139/5余4，余数除以素因子的余数无矛盾，该题有解。
6 v: X2 N* N4 Y9 h
选择抛开105中的3和5，剩余7，有19/7余5，原题变为M/7余5，M/165余139。
7 s6 Q) r3 I7 k& }6 l5 y8 J
由M/165余139为等差数列139+165N，先化为6+4Ｎ取7项内：6，3，0，4，1，5，第6项满足除以7余5，代入原等差数列139+165*(6-1)＝964，因165*7＝1155，得满足该题的解为964+1155N。
. E2 a: n9 W' B2 W6 s+ ]! S
中国剩余定理的结论：
. k3 v+ b; p2 r. [. `
令任意固定整数为M，当M/A余a，M/B余b，M/C余c，M/D余d，…，M/Z余z时，这里的A，B，C，D，…，Z为除数，除数为任意自然数（不包括0和1）时；余数a，b，c，d，z为自然整数时。
' W( @9 v* ~5 n4 }/ f+ S
1、当题正确时，在这些除数的最小公倍数内有解，有唯一的解，每一个最小公倍数内都有唯一的解；当题错误时，在整个自然数范围内都无解。
8 s; D) y* p4 ?0 m7 D
2、当M在两个或两个以上的除数的最小公倍数内时，这两个或两个以上的除数和余数同时定位M在最小公倍数内的具体位置，也就是M的大小。
3 S' |% z7 g6 q* b/ Q! x) i
五、趣谈中国剩余定理
0 t x5 b. u# Q5 q8 _# N
我们以57为例，有57/2余1，57/3余0，57/5余2，57/7余1，57/11余2，57/13余5，57/17余6，57/19余0，57/23余11，57/29余28，57/31余26，57/37余20，57/41余16，57/43余14，57/47余10。
7 {& W4 C* \! |" O1 m9 ?3 ?
这里有15个素数作为57的参照，那么，所有素数的乘积大于57许多；分别乘积，大于57的也有许多，素数如3*5*7=105，2*3*11=66，2*47=94都大于57。所有素数的乘积与部分素数的乘积，对于57的定位如何呢？
3 \, a1 ]3 I; v3 n) y4 O# P6 y0 e8 J
（一）部分素数
) O+ ]0 M& V3 S0 W6 D, y0 z: E! ?
1、按3*5*7=105，为：
8 r( A6 J- I, F9 Z
满足除以7余1为等差数列1+7N，取5项有1，8，15，22，29，满足除以5余2为22，因7*5=35，得等差数列22+35N，
4 i9 F" M" {* @* N5 B3 _; t
对等差数列22+35N取3项为，22，57，92，满足除以3余0为57，因35*3=105，得等差数列57+105N满足除以3，5，7的余数条件；
) c1 v) X; }8 R7 e0 y* K% C0 `
2、按2*3*11=66，为：
# C* k& z# S) I) S& G
满足除以11余2为等差数列2+11N，取3项有2，13，24，满足除以3余0为24，因11*3=33，得等差数列24+33N，取2项24，57，有57满足除以2余1，因33*2=66，得等差数列57+66N满足除以2，3，11的余数条件；
1 N7 l0 }+ |- ^2 |
3、按2*47=94为：满足除以47余10为等差数列10+47N，取2项10，57，有57满足除以2余1，因2*47＝94，得等差数列57+94Ｎ满足除以2和47的余数条件。
' w Z; d, {6 `3 \( H( m
（二）、全部素数
+ C% ~- E. E1 R. ?0 P$ ?
前面计算了除以素因子3，5，7的余数后，得等差数列57+105N，
+ |! w% e1 t* E
再计算11时，将57+105N取11项，57，162，267，…，只有第一项满足除以11余2，因105*11=1155，得等差数列57+1155N，再计算13时，将该等差数列取13项，57，1212，2367，…，只有第一项满足除以13余5；……。
9 c: K3 G: |0 s3 t( @
也就是说，在614889782588491410之内的任意一个数，锁定了它除以这些素因子的余数；反过来除以这些素因子的余数，也锁定了在614889782588491410之内的这个数。不论你先计算除以哪一个素因子的余数，后计算除以哪一个素因子的余数，结果都是一样的。
. G0 A h0 {$ @% L4 g! {1 o
从这里也可以看出，当几个素因子的乘积大于这个数时，从除以这几个素因子的余数，就可以准确地计算出这个数。
: w4 v: x f% P8 ?9 I
四川省三台县工商局：王志成。
4 z1 S8 {( i+ O# }2 l8 A1 t
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5