高中数学竞赛讲座---同余理论及其应用(二)

数论定理一.知识要点1.欧拉定理和费尔马小定理缩系的定义：设m为正整数，一个模m的剩余类称为与模m互素的余类，如果它中的数与m互素．在与模m互素的各个剩余类中分别取一个代表所构成的集合称为模m的一组缩系．很显然，缩系具有以下性质：（1）模m的缩系中含有（m）个数（（m）是小于m的正整数中且与m互素的个数）．（2）设mrr,1是（m）个与m互素的整数，则mrr,1模m两两不同余．（3）设1,ma，且mrr,1是模m的一组缩系，则mararar,,,21是模m的一组缩系．欧拉（Euler）定理：设m是大于1的整数，a为整数，且1,ma，则mammod1．解：设mxxx,,,21是模m的缩系．因为1,ma，所以maxaxax,,,21也是模m的缩系．这两个缩系分别乘起来得mxxxaxaxaxmmmod·2121，且1,21mxxxm．从而mammod1mammod1．特别地，取m为质数p，有费尔马（Fermat）小定理：设p为质数，a为整数，pa，则papmod11．它也常常写成paapmod．这里不需假定pa，但p应为素数．2.中国剩余定理（孙子定理）中国剩余定理：设kmmm,,21是两两互质的正整数，kaaa,,,21是任意整数，则同余方程组.mod,mod,mod2211kkmaxmaxmax对模kmmm21有唯一解．解：设kimmmmMiki,,2,121．依题设，有1,iimM，由裴蜀定理知，存在整数ib，使得iiimbMmod1，ki,2,1．对kkkMbaMbaMbax222111，其中iiiMba能被kiimmmm,,,,111整除，而被im除的余数恰为ia．从而kiiiiMbax1是同余方程组的解．又设x，y均为同余方程组的解，则有yxm1，yxm2，…，yxmk，即yxmmmk21，亦即kmmmyx21mod．所以同余方程组对模kmmm21有唯一解．3.威尔逊（wilson）定理威尔逊（wilson）定理：设p为质数，则ppmod1!1．解：对于任意整数a，且1≤a≤p－1，由裴蜀定理知，存在整数a’，使得paamod1'．称a’为a的数论倒数，且不妨设1≤a’≤p－1．若有整数b，满足pbamod1'，则将此式两边同乘以a，有pabmod．这说明对于不同整数a，1≤a≤p－1，对应着不同的数论倒数a’．又若整数a的数论倒数是它自身，则paamod1，亦即paamod011，故1a或pmod1．当2p时，显然有ppmod1!1．当p＞2时，有2，3，…，p－2这p－3个数恰好配成互为数论倒数的23p对数，故它们的积pppmod1123223．于是pppmod1111!1．4.拉格朗日定理设p为质数，n是非负整数，多项式01axaxaxfnn是一个模p为n次的整系数多项式（即pan），则同余方程pxfmod0（※），至多有n个解（在模p的意义下）．证明：我们对n用归纳法．当0n时，0axf，因为pa0，故同余方程（※）无解，命题成立．设当ln时命题成立，则当1ln时，若命题不成立，即同余方程（※）至少有2l个解，设为pcccxlmod,,,221①，我们考虑多项式11111111cxacxacxacfxfllllll11111111cxacxacxacfxfllllllxhcxxacxll111②，其中xh是l次多项式并且首项系数1la，满足1lap，从而由归纳假设知l次同余方程pxhmod0③，至多有个l个解，但由①，②可知同余方程③至少有l＋1个解．pcccxlmod,,,232，矛盾！故当1ln时命题成立．综上所述，命题得证．二.典型例题例1.已知正整数k≥2，kppp,,,21为奇质数，且1,21kpppa．证明：111121kpppa有不同于kppp,,21的奇质因数．证明：由1,21kpppa，有1,1pa．由费尔马小定理，11mod11pap．又k≥2，kppp,,,32kppp,,,32为奇质数，则211121kppp为正整数，从而12111mod121pakppp，即12111121kpppap.同理，1211121kpppa能被P2，P3，…Pk整除，从而1211121kpppa不能被kpppp,,,,321整除．注意到211121kppp是一个偶数，则0211121kpppa或1（mod4），因此4不整除1211121kpppa，故1211121kpppa异于kppp,,,21的奇质因数．所以1121111112121kkppppppaa1211121kpppa有异于kppp,,,21的奇质因数．例2.对于自然数n，如果对于任何整数a，只要1nan，就有12nan，则称n具有性质P．（34届IMO预）（1）求证：每个素数n都具有性质P．（2）求证：有无穷多个合数也都具有性质P．证：（1）设pn为素数且1pap，于是1,pa．由费尔马小定理知11pap，而1111aaaapp．故1ap，即pamod1．因此，paimod1，1,,2,1,0pi．上述p个同余式累和，得ppaaappmod0121．故11212aaaappp，即12pap．（2）设n是具有性质P的合数．若1nan，则1,an．由欧拉定理，有nanmod1，又因nanmod1，由阶的性质知，nannmod1,．如果1,nn，则namod1，于是利用（1）中证明可得12nan．因此，问题化为求无穷多个合数n，使1,nn．对任何素数p≥5，取p－2的素因数q，并令pqn．这时11qpn．因为2pq，所以q(p－1)．又因q≤p－2＜p，故p(q－1)．因此，有1,nn．对于每个这样的合数n，若1nan，则1an，因而nakmod1，,2,1,0k．故12nan．因为对于每个素数p≥5都可按上述程序得到具有性质P的相应合数pn，且p＜pn＜p2，所以，有无穷多个合数n具有性质P．例3.求所有整数n≥2，满足：对所有的整数a，b，且1,,nbna，nbamod的充分必要条件是nabmod1．（第41届IMO预选题）解：若n有奇素因子p，设npa||，记1npna，Na．由中国剩余定理知，存在Zx，使nxmod1，apxmod2，则1,nx．取xba，即知nxmod12，从而apmod14，故3p，且1a．因此1,5n．取5ba，即知nmod125，从而24n，故24,12,8,6,4,3,2n24,12,8,6,4,3,2n．下证：当n取上述值时，满足条件．注意到，当2a时，有8mod12a；当3a时，有3mod12a，又24n，32243，故必有namod12（因为1,na）．对Zba,，且1,,nbna，nbamod，则nabmod1．对Zba,，且1,,nbna，nabmod1，则nabamod12．从而aban又1,na，有ban，即nbamod．综上，所求n的值为2，3，4，6，8，12，24．例4.求所有正整数n，满足对所有的正整数n，存在一个整数m，使12n是92m的因子．（第39届IMO预选题）解：引理1：若p为4k－1（k≥2）型质数，则不存在Zm，使pmmod92．证明：设pmmmod31pmmmod31（∵13,p，∴m1存在），Nm1．又∵pmmod912,∴)(mod121pm．由费马小定理知，pmmpppmod11121212111，矛盾．引理2：当1≤i＜j时，有112,1222ji112,1222ji，且13,122i．证明：∵12mod211121222222iijijij，∴12,1212,12222iji12,1212,12222iji．又∵3mod2111222ii，∴13,23,122i．对于原题，若9122mn，n≥2．设tnS2，2t．若t≥3，则1212nt，从而9122mt．又必存在4k－1型素数p，且3p，12tp（否则，4mod1111121t，矛盾）．此时92mp，与引理1矛盾．故t=1，从而Sn2，且1212123121212222SS．由引理2及中国剩余定理知，存在Nm1，使12mod22211iim，i=1，2，…，s－1．故12mod0121222211iim12mod0121222211iim．令13mm，有12mod013922122Smm．因此，9122mn．综上，所求正整数n为2的幂次2i（i=1，2，…）．数论中存在性问题是最常见的，除了运用数论存在性定理来解决外，还需要有直接构造的能力．例5.证明：每个正有理数能被表示成3333dcba的形式，且其中a，b，c，d是正整数．（40届IMO预选题）证明：设该正有理数为p．（1）当2,21p时，333321121ppppp，其中2p－1，2－p，p＋1Q．（2）当p≥2时，由于1,41323，故有Nn，使2,21323pn，由（1）有333333333322132132213223pppppnnnnn．（3）当21,0p时，由于4,1233，故有Nn，使2,21233pn，由（1）有333333333232123123212332pppppnnnnn．综上，总有Qdcbam1111,,,,，使31313131313131313dcmbmadcbamp,设ma1，mb1，c1，d1的分母公倍数为n，则取Nmnaa1，Nmnbb