中国剩余定理

wangzc1634

中国剩余定理

科学研究的目的：在于向简单化，科学化发展．

本文编写目的：让人们轻松地，全新地，全面地了解中国剩余定理．全面指没有死角，全新指与现有教科书完全不一样的内容．

原题：三三数之剩二，五五数之剩三，七七数之剩二，问该数几何？

令，这个数为Ｍ，三三数之剩二，指Ｍ-2能被3整除；七七数之剩二，指Ｍ-2能被7整除．即Ｍ-2能被3和7的公倍数整除，3和7的公倍数为3*7＝21，即Ｍ存在于2＋21Ｎ之中．

五五数之剩三，指Ｍ/5余3，将2＋21Ｎ等差数列的首项2，公差21同时除以5的余数为2和1，组成新的等差数列2＋1Ｎ．2＋1Ｎ与2＋21Ｎ两个等差数列除以5的余数循环是一样的，由2＋1Ｎ一眼就能看出等差数列的第2项符合条件，代入原等差数列2＋21Ｎ有：2＋21(2-1)＝23.即23符合题意．

又因为，3*5*7＝105，所以，23＋105Ｎ等差数列的数都符合题意．

一，            中国剩余定理基本原理

当除数为Ａ，Ｂ，Ｃ，Ｄ，…，Ｚ，且它们互质(指它们为不同的质数或不同质数的Ｎ次方)时，它们的最小公倍数为Ａ*Ｂ*Ｃ*Ｄ*…*Ｚ．

自然数除以Ａ的余数为：余0，余1，余2，余3，…，余Ａ-1，共Ａ种不同的余数；

自然数除以Ｂ的余数为：余0，余1，余2，余3，…，余Ｂ-1，共Ｂ种不同的余数；

自然数除以Ｃ的余数为：余0，余1，余2，余3，…，余Ｃ-1，共Ｃ种不同的余数；

自然数除以Ｄ的余数为：余0，余1，余2，余3，…，余Ｄ-1，共Ｄ种不同的余数；

……；

自然数除以Ｚ的余数为：余0，余1，余2，余3，…，余Ｚ-1，共Ｚ种不同的余数．

那么，自然数除以Ａ，Ｂ，Ｃ，Ｄ，…，Ｚ不同的余数组合为Ａ*Ｂ*Ｃ*Ｄ*…*Ｚ个，对应于自然数1到Ａ*Ｂ*Ｃ*Ｄ*…*Ｚ之内的数，即每一种余数组合对应一个自然数，形成一一对应的关系，这就是中国剩余定理的唯一性和必然性．

二，中国剩余定理的三种表现形势：

按除数划分，中国剩余定理有三种表现形势．

1，除数为不同的质数，如除数为3，5，7，11，Ｍ/3余1，Ｍ/5余2，Ｍ/7余3，Ｍ/11余4.求Ｍ＝？Ｍ在最小公倍数3*5*7*11＝1155内有解，有唯一的解．这里的3*5*7*11为3，5，7，11的最小公倍数．或者说3，5，7，11是最小公倍数1155的结构(新概念，下同)．

2，除数为不同的质数和不同质数的Ｎ次方，如，16，27，5，7，Ｍ/16余3，Ｍ/27余4，Ｍ/5余2，Ｍ/7余6，求Ｍ＝？Ｍ在最小公倍数16*27*5*7＝15120之内有解，有唯一的解．这里的16*27*5*7是16，27，5，7的最小公倍数，或者说16，27，5，7是最小公倍数15120的结构.

3，除数为任意合数，如，216，288，2025，Ｍ/216余49，Ｍ/288余265，Ｍ/2025余1696，求Ｍ＝？

这类题，首先要按最小公倍数的结构，寻找到这几个合数的最小公倍数．

最小公倍数的结构，是指最小公倍数表示为几个数的乘积，我们称这几个乘数为该最小公倍数的结构．

这里的216＝2*2*2*3*3*3，288＝2*2*2*2*2*3*3，2025＝5*5*3*3*3*3.这三个数中有质数2，3，5．

2最高为5次方32，3最高为4次方81，5最高为2次方25，那么，216，288，2025的最小公倍数为32*81*25＝64800，即最小公倍数64800的结构为32，81，25．

最小公倍数，为几个数中所含素因子的最高次方的乘积，几个素因子的最高次方也就是最小公倍数的结构．

这类题与前面两类题不同，前面两类题不可能存在错题，这类题很容易出现错题，所以，在解题之前必然先审题，审题的方法是：

审题依据为基本数学原理，一个固定的数除以另一个数的结果只有一种(余数)，方法用除以合数的余数，除以合数所含素因子．注意：必然全部检测比较．

因为，216，288都含素因子2，用除以它们的余数除以2，看是否相同：49/2余1，265/2余1，相同；

又因为，216，288，2025都含素因子3，用除以它们的余数除以3，看是否相同：49/3余1，265/3余1，1696/3余1，相同，

只有2025含素因子5，不用检测，

因为，它们的余数相同，说明该题是正确的，在最小公倍数64800内有解，有唯一的解．

如果，1个余数除以3余1，1个余数除以3余2，不相同，那么，题就是错题，错题在整个自然数中都无解．

三，            中国剩余定理的具体变化

中国剩余定理的具体变化，指余数的变化关系．

以除数为3，5，7，11为例，进行说明：

1，基本变化

自然数为1时，有1/3余1，1/5余1，1/7余1，1/11余1.

自然数为2时，有2/3余2，2/5余2，2/7余2，2/11余2，

……，

即，当自然数增加Ｎ时，所有余数都增加Ｎ．

例，当Ｍ/3余1，Ｍ/5余2，Ｍ/7余3，Ｍ/11余4时，求Ｍ＋12的余数组合？

(1＋12)/3余1，(2＋12)/5余4，(3＋12)/7余1，(4＋12)/11余5，

得Ｍ＋12的余数组合为：(Ｍ＋12)/3余1，(Ｍ＋12)/5余4，(Ｍ＋12)/7余1，(Ｍ＋12)/11余5.

这两个数分别为367和379.

2，部分变化

当Ｍ/3余1，Ｍ/5余2，Ｍ/7余3，Ｍ/11余4时，Ｍ＝367，当Ｍ′除以5，7，11的余数不变时，我们看其变化情况．

除以5，7，11的余数不变，因5*7*11＝385，其变化间隔必然是385的倍数，而385/3余1，所以，每增加385时，除以3的余数增加1，因367＋385＝752，那么，752/3余2，752/5余2，752/7余3，752/11余4；367＋385*2＝1137，即，1137/3余0，1137/5余2，1137/7余3，1137/11余4．

因为，3，5，7，11的最小公倍数为1155，针对除以5，7，11的余数不变，只有除以3的余数变化，那么，在周期(1155，下同)内只有3种变化．

同样的，3，5，7，11的最小公倍数为1155，针对除以7，11的余数不变，只有除以3，5的余数变化，那么，在周期内只有3*5＝15种变化．因7*11＝77，变化间隔为77.

同样的，3，5，7，11的最小公倍数为1155，针对除以11的余数不变，只有除以3，5，7的余数变化，那么，在周期内只有3*5*7＝105种变化．变化间隔为11.

说到这里，您一定明白：在自然数中任意取一个整数Ａ,如何寻找一个除以质数Ｂ，Ｃ，Ｄ，Ｅ,…，Ｆ余数完全一样的数了．即，Ａ±Ｂ*Ｃ*Ｄ*Ｅ*…*Ｆ.

如，与2357除以3，5，7，13的余数完全一样的数，因3*5*7*13＝1365，所以，2357±1365，即，3722和992除以3，5，7，13余数与2357除以3，5，7，13的余数完全一样.

反过来，在自然数中任意取一个整数Ｍ，寻找一个除以质数Ｂ，Ｃ，Ｄ，Ｅ,…，Ｆ余数完全不一样的数，为Ｍ±不能被Ｂ，Ｃ，Ｄ，Ｅ,…，Ｆ整除的数．

如，任意取一个数72，寻找一个除以2，3，5，7，11与72除以2，3，5，7，11余数完全不一样的数．

因为，2，3，5，7，11是连续质数，所以，大于11的任意质数都不能被2，3，5，7，11整数，即任意±一个大于11的质数都能达到这个效果．如72±31，有103和41与72除以2，3，5，7，11的余数完全不同．

四，            中国剩余定理的解法

中国剩余定理的解法，请搜索《中国剩余定理新解法》，什么类型的题都在其中．

　　　　　　　　四川省三台县工商局　王志成．

+ c# f1 A  ]/ F