一次同余式与孙子定理

1、一次同余式与孙子定理知识扫描：1:本节将讨论一次同余方程和由此引申出的重要定理一一孙子定理，首先介绍若干概念。设整系数多项式fx二anxn川川a0,若有整数c,满足fc三0modm,则称c是满足同余方程的解，记作x三cmodm.(注：这是因为除以x余c的数都满足这样方程)。当且仅当c!,c2都是方程的解，且g与c模m不同余时，我们称d,c2是方程的两个不同解。一般情况，我们说同余方程的解数，即指模仃两两不同余的解的个数。2:最简单的同余方程是一次同余方程ax三bmodm,m?a同余方程有解的充要条件是a,m/b(注：必要性，若有解，则b可用a,x的式子表达，所以a,m/b;充分性，一，互素(a

2、,m)(a,m)amam则可知pq1=bpqb=b,因为a,m/b,则可知(a,m)(a,m)(a,m)(a,m)ax三bmodm有解)。特别地，在(a,m)=1时，同余方程必有解。事实上：(a,m)=1,x遍历模m的一组完系时，aXj也遍历模m的一组完系。因此，有且仅有一个r0=xi使得aXi三ar0三bmodm，即同余方程至多有一个解。进一步，一定存在a使得a"筆三1(modm于是x三aj(mb(modm),即为(a,m)=1时，同余方程的解。3.设k1,ai,bi是整数，mj是正整数，i=1,2,k,则称下面这k个同余式r=modm1)a2x+b2三0(modm2)akx+bk

3、三0(modmk)为一次同余方程式组，显然，其中若有一个同余方程无解。则方程组无解。当其中每个同余方程都有解时，可将求解转化为求若干个下述方程的解。x三g(modm1)x三q(modm2)x三厲(modmk)为了讨论上式的本质，我们先来看k=2的情况。定理1：设m=mim2.xX是模mi的完全剩余系，xj（2是模m2的完全剩余系，贝VXjj二Xj1gXj2是模m的完全剩余系。（即X1,X2分别遍历模mp模m2的完全剩余系时，XuxOI+mhxf遍历模口=口和2的完全剩余系。）证明：此时Xij共有m=mim2个数，因而只需证明它们对m两两不同余。若X1O+m1X）=x/）+m|X2f*modmm

4、）,则x（O+gxf）三x2C）+m|X2（2*modm）则Xi1=X21，同时X11-m1x/X2+m1x/?modm2卜贝Uxf）=血（2）定理得证！定理1刻画了完系的某种结构，表明大模m=gm?的完系，可以表示为两个较小的模的完系的“组合”。同时我们应注意到，（g,m2尸1,xC遍历模口的完系时m2x1也遍历模叶的完系（这个性质非常常用并且有用）定理2：设口=耳叫,何,口2戸仃门xf分别遍历模m，m的完全剩余系，则Xj）+m|X（2遍历模m叫的完全剩余系。进一步分析，我们可以得到一般情形的刻画。定理3:设m=耳叫mk,m,m2mk两两既约，再设m=mj：Mj1_j_k及x=）+M2x（2

5、）+Mkx，那么当X1，x（k分别遍历模叶，m2,，mk的完全剩余系时，x遍历模m=mm2mk的完全剩余系。证明：k=2时，即定理2设k=n时定理成立。当k=n+1时，记xC）=m一x）+mx（n）.叫*mnE*我们有x=mn卅注：g卅与-互素,x（n遍历的完系，x（n*遍历0十mumu模的完系）由当k=2时上式成立，命题得证！。定理4:孙子定理（中国剩余定理）设m11m2/,mk是两两既约的正整数，那么同余方程：fx三G（modm1）x三c2（modm2）1x=Ckmodmk的解是x三MmJgM2M2'c2MkMckmodm,这里mgm/mim二mjMj1玄j玄k,MjMj1modm

6、jj弐k孙子定理依旧刻画的是剩余系的结构，请读者将其与定理3进行对比，可以看出，孙子定理是着重刻画一组已定下的较小模的剩余类与一个较大的模的某个剩余类间的关系。中国剩余定理在做题时的指导在于它能断定同余方程组的模两两互素时，一定有解。甚至有些时候，我们并不关心解的是什么，而关注是否有解，怎样使其有解。例题分析例1:解同余方程组x三1(mod3)x三1(mod5)x三2(mod7)x三2(mod11)解：取m=3,m2=5,m3=7,m4=11,这时M!=5_711,M2=3了11M=5311,M4=573又由Mi=-11-1=1mod3,所以1三MjMjM11mod3,可取“=1.由M2三2-

7、2-1三1mod5,所以1三M2M2jM2jmod5,可取M2=1由M3三354三4mod7,所以1三M3M34M3二mod7,可取M3°=2.由M4三357三6mod11,所以可取M4=2.由孙子定理知同余方程的解为：x=394mod1155.例2：任意给定的整数n,证明：一定存在n个连续正整数，其中每一个都有大于1的平方因子。证明：由于素数有无穷多个，因而对于任意的n，均可选出n个不同的素数p1,p2/,pn。2222考虑同余方程组X=-imodPi，由于P1，P2/，Pn显然两两互素，由中国剩余定理知上述同余方程组有解，于是x1,x2,xn这n个数分别被p12，p22/，pn2

8、整除，命题得证！评注：在构造同余式时，选择质数的某些形式作为模式十分有效的，再看一个构造的例子。例3:能否找到含有2005个自然数的集合，使1S中任意两数互素；2S中任意k个数的和为合数。分析与解：2005显然是“年份数据”，为此考虑n个元素的集合，由于同时满足上述两个条件不易找到一个直接构造，只能一步步地探索。对于满足1的n元集合石容易构造的，故设我们已找到一个满足1的集合：x1,x2xn?,下面关心怎样更进一步约束或者变动该集合。我们当然希望需要控制的“k数和”变少自然想到了归纳构造。我们设x1,x2xn已经满足了上述两个条件，下面用x1,x2x.推出xnd应为何物。1必Xn中含xn1的“

9、k数和”有2n-1个k2注：含xn1的k数和个数为：C设这些和为S1SS2n),则T1=S-焉十“2=5-Xn知,T2nS2n_-xH1均为定值，我们想让xn1+S-xn1，xn1+S2-人1，Xn1+S2n-xn1均为合数，这利用中国剩余定理是容易办到的，因为同余方程组：焉十三xn4r-S三-T(modpi)是有解的，其中SP2,P2n4是两两互素的数，且Pi=1.这样我们就让、x,，Xn+满足2回头看此时，焉+1是否满足1呢？这一点并不确定，从而应当控制一下口的值。由于Xl,，Xn已经是两两互质，所以若Xn+1能表示为kX1Xn啲形式，则X|,，Xn+1两两互素，这实际上要求Xn+1三1m

10、odXXn.至此，怎样控制口已经非常明确了，我们只需2"-1个质数山，P2,卩卯它们均与a1吐匚-an互素，考虑2n个同余式xn彳三TmodPi菱i=1,2,2n-1,xnq三1modaA_a<an，由中国剩余定理，这样的xnd存在。至此完成了归纳构造！特别的，n=2005时我们能找到一个适合题目要求的集合。例4：求具有下述性质的n，存在0,1,2，n-1的排列ai,a2,，an使得aq,aqa2,aa2a3,，aqa2an恰好构成模n的完全剩余系。解：首先实验几个较小的n,n=1时，显然满足条件，n=2时，1,0满足条件n=3时，12,0满足条件，n=4时，13,2,0满足条

11、件，n=5时，12,4,3,0满足n=6时，经实验没有满足条件的排列，n=7时,(16,2,4,5,3,0)满足条件，n=8时，没有满足要求的排列。通过上述实验，我们猜想n为质数时，均是满足条件，尽管这可能是不全面的。下面证明这个结论。事实上，对任意质数p,由中国剩余定理，对每个k=2,3，p,存在bk,使得bk三0modk-1,bk三kmodp,用ak表示ck被p除的余数k=2,3,pk1则bk三akk-1三kmodp.注：实际上是为了得到ak令q=1,下面证明玄仁a2,ap互不相同从而a1,a2,ap是模p的完系事实上，由app-1三p三0modp,有ap=0，故印ap。又当k=2,3,p

12、-1时，akk-1=kmodp，故p寣ikk-1,所以pak,即akap.若存在k,l,2込k：丨込p-1,使得ak二ai二a,则akk-1丨二aklI三klmodpa,I1丨二akl-k三klmodp,从而ak-I=aklI-akl-k三0modp这说明p/a,矛盾！若存在k,2_k：p-1,使得ak二a则k-1二akk-1=kmodp,说明：p/-1,矛盾以上说明了a1,a2/,ak的确是0,1,2,p-1的排列，同时aa2ak三2-1aza?ap=2a3aap=：3-1asa/ap三k-1akmodp,注：往前看用了个推出来的公式。所以当n为质数时满足条件。接下来，我们考虑一下其他可能情

13、形，稍作分析，即可知对大于4的合数n,n均不满足题意。若n=p2,记q=2p：n;否则n=pq,1”：P”：q”：n,在这两种情况下均有pq三0modn且p,q23,n设ai,a2,an是满足条件的序列，则k=1,2,nT时，ak=0,否则a1aak三0modn,aa2ak三0modn,于是存在k,l:：n,使ak二p,a|记m二max：k,l”：n,则akal/a!a2am.因此有a1a2am三0modn,aa2am1三0modn矛盾！于是证得n>4为合数时，不满足题目要求！所以，符合条件的n应为1,4及所有质数。例5证明：存在一个正整数n,使得对于任意正整数k,n_2k1均为合数。分

14、析与解答：题中要求对变化着的k,使得n2k7均为合数，有两种自然的想法：1考虑该式是否能进行因式分解；2证明该式恒为某个质数或某几个质数的倍数。对于前者，似乎不容易做到，因为要使该式能进行分解的n总要求和k有些联系，若n=23k1,但这不符合题中“n为定数”的要求；把角度转向2，这看似好像很容易做到，这时因为我们只需要考虑2k模一些质数得到的余数，在利用孙子定理确定n的值。下面就关心2k模质数后的余数。为了满足题意，我们要确保两件事，即k取遍所有正整数时，我们只能用有限个质数做模否则无法使用中国剩余定理，同时对于每个作为模的质数p,2k模p只能出现一种余数否则这样的数不存在，而这不容易做到，其难处在于我们能否找到几组剩余类，使得对任意的k都必属于其中之一，对于上述这种剩余类，我们称其为“同余覆盖式”。分析表明，它是存在的，且不只一组，下面给出一组，希望读者能将其记住k三1mod2七三1mod3飞三2mod4+三4mod8飞三0mod12飞三8mod24请自行证明对任意的k,它至少适合上述6个式子中的一个。