Question

中国剩余定理证明

书上有一处没看明白 =代表同于符号 ijk下标
性质11.3.2
如果a,b对于m同余
c,d对于m同余
那么 a+b ,c+d对于m同余
-------------------------------------------
证明：假设对i=1，2，3……k，有
Xi=ai(mod mi)
Xi=0(mod mj)

j!=i 1<=j<=k

令X=X1+X2……Xk 有性质11.3.2，有
X=ai(mod mi) i=1,2,3……
//请问一个是Mi 一个是Mj怎么推出来的？？
性质11.3.2
如果a,b对于m同余
c,d对于m同余
那么 a+c ,b+d对于m同余

那两个除数不一样的

Mi和Mj不是一个数怎么能用这个性质呢

Answer 1

中国剩余定理
"剩余倍分法"互除余一 互除少一
证明"孙子定理"不完善 不稳定的表现
作者：张景刚 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元。

Answer 2

中国剩余定理
"剩余倍分法"互除余一 互除少一
证明"孙子定理"不完善 不稳定的表现
作者：张景刚 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
http://zhidao.baidu.com/question/29794605.html?si=3&wtp=wk
http://baike.baidu.com/view/65313.html?wtp=tt
我在这里祝你学习进步

Answer 3

我是原来2楼的那个，我再补充下。
还看我下面举的那个例子。

转化为数学公式表达是：
求最小数N，满足
N≡5（mod 9），N≡1（mod 7），N≡2（mod5）
因此，就像题中和你的证明中那样
取X1=225，满足225≡0（mod 9），N≡0（mod 5）N≡1（mod7)
取X2=252，满足252≡0（mod 9），N≡2（mod 5），N≡0（mod7）
取X3=140，满足140≡5（mod 9），N≡0（mod 5），N≡0（mod7）

这样，比如对于5而言，应用你给的性质，617=225+252+140≡0+2+0≡2（mod5）
同样对于7和9也满足
所以617再减它们公倍数得305也满足，即完成。

楼主把这个例子和你的证明过程对照一下就明白了。

Mi和Mj直至Mk相当于以下的中的a1、a2、……an，即除数。

设有一数N，分别被两两互素的几个数a1、a2、……an相除得余数R1、R2、……Rn，即
N≡Ri（modai）（i＝1、2、……n）

剩余定理思路就是
对于Mi（Mi是任意的一个除数），构造出一个Xi能被其余的所有除数Mj（j不等于i）整除，只对Mi余ai
这样，构造出的所有数求和即为所求。

举例
有一个年级的同学,每9人一排多5人,每7人一排多1人, 每5人一排多2人,问这个年级至少有多少人？

此题中Mi就是9，7，5。

5 和 9 的公倍数依次是 45、90、135、180、225 ……
这些公倍数中，取被7除余1的数是 225

9 和 7 的公倍数依次是 63、126、189、252……
这其中，取被5除余2的是 252

5 和 7 的公倍数是 35、70、105、140、……
其中被9除余5的数是 140

把以上 225 252 140 三个数相加，求得
225 + 252 + 140 = 617 满足题中要求。
由于求最少人数，所以：

5 7 9 三个数的最小公倍数是 5*7*9=315

617-315 = 302 也是满足的，最小的。

因此 302 就是这个年级至少人数。

希望对你有帮助，有疑问可以发消息给我再交流。

Answer 4

问题一：

性质11.3.2
如果a,b对于m同余
c,d对于m同余
那么 a+b ,c+d对于m同余
错了。应当是
a+c==b+d mod m
或a+d==b+c mod m

证：
a=b+mx
c=d+my
故a+c=b+d+m(x+y)，即a+c==b+d mod m
另有
a+d=b+c+m(x-y)，即a+d==b+c mod m

以上这个性质根本无需利用xi==ai mod Mi的过程来证明。

问题二：
证明：假设对i=1，2，3……k，有
Xi=ai(mod mi)
Xi=0(mod mj)

j!=i 1<=j<=k

令X=X1+X2……Xk 有性质11.3.2，有
X=ai(mod mi) i=1,2,3……
//请问一个是Mi 一个是Mj怎么推出来的？？

这个内容常常用于论证中国剩余定理或相关内容。
其中mi起主导作用，
当i=1时，j取遍2到k；
当i=2时，j取遍集合{1}并{3到k};
当i=3时，j取遍集合{1,2}并{4到k};
总之，i取某个值时，j取遍集合{1到k}扣除{i的值}
严格的写,就是j属于集合{j为整数，1<=j<=k}-{i}
减号-表示对集合作差运算，即求差集。
因此，Mi, Mj二者一主一从，二者相关，并不矛盾。

Answer 5

求X(mod mi)时，将X分拆成X1+X2…+Xi+…+Xk，其中只有Xi≡ai(mod mi)，其它的Xj≡0(mod mi)，所以得X≡Xi≡ai(mod mi).

在验算X(mod mi)时，并不出现mj啊。
---------------------------------------------------------------以上10-18 15:02

>>证明：假设对i=1，2，3……k，有
>>Xi=ai(mod mi)
>>Xi=0(mod mj) (j!=i 1<=j<=k)
>>
>>令X=X1+X2……Xk 有性质11.3.2，有
>>X=ai(mod mi) i=1,2,3……
>>//请问一个是Mi 一个是Mj怎么推出来的？？

答：以上是按Xi不动、跑遍mi来陈列的，如果改为按mi不动、跑遍Xi来列陈，事情就清楚了。

证明：假设对i=1，2，3……k，有
Xi=ai(mod mi)
Xj=0(mod mi) (j!=i 1<=j<=k)

令X=X1+X2……Xk 有性质11.3.2，有
X=ai(mod mi) i=1,2,3……

可见，在验算X(mod mi)时，并不出现mj。