全国高中数学竞赛专题座同余理论及其应用技术(二)

《全国高中数学竞赛专题座同余理论及其应用技术(二)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数论定理一.知识要点1.欧拉定理和费尔马小定理缩系的定义：设m为正整数，一个模m的剩余类称为与模m互素的余类，如果它中的数与m互素．在与模m互素的各个剩余类中分别取一个代表所构成的集合称为模m的一组缩系．很显然，缩系具有以下性质：（1）模m的缩系中含有（m）个数（（m）是小于m的正整数中且与m互素的个数）．（2）设是（m）个与m互素的整数，则模m两两不同余．（3）设，且是模m的一组缩系，则是模m的一组缩系．矚慫润厲钐瘗睞枥庑赖。欧拉（Euler）定理：设m是大于1的整数，a为整数，且，则．解：设是模m的缩系．因为，所以也是模m的缩系．

2、这两个缩系分别乘起来得，且．从而．特别地，取m为质数p，有费尔马（Fermat）小定理：设p为质数，a为整数，pa，则．它也常常写成．这里不需假定pa，但p应为素数．聞創沟燴鐺險爱氇谴净。2.中国剩余定理（孙子定理）中国剩余定理：设是两两互质的正整数，是任意整数，则同余方程组对模有唯一解．解：设．依题设，有，由裴蜀定理知，存在整数，使得，．对，其中能被整除，而被除的余数恰为．从而是同余方程组的解．又设x，y均为同余方程组的解，则有，，…，，即，亦即．所以同余方程组对模有唯一解．残骛楼諍锩瀨濟溆塹籟。3.威尔逊（wilson）定理12/

3、12威尔逊（wilson）定理：设p为质数，则．解：对于任意整数a，且1≤a≤p－1，由裴蜀定理知，存在整数a’，使得．称a’为a的数论倒数，且不妨设1≤a’≤p－1．若有整数b，满足，则将此式两边同乘以a，有．这说明对于不同整数a，1≤a≤p－1，对应着不同的数论倒数a’．又若整数a的数论倒数是它自身，则，亦即，故或．当时，显然有．当p＞2时，有2，3，…，p－2这p－3个数恰好配成互为数论倒数的对数，故它们的积．于是．酽锕极額閉镇桧猪訣锥。4.拉格朗日定理设p为质数，n是非负整数，多项式是一个模p为n次的整系数多项式（即pan），

4、则同余方程（※），至多有n个解（在模p的意义下）．彈贸摄尔霁毙攬砖卤庑。证明：我们对n用归纳法．当时，，因为pa0，故同余方程（※）无解，命题成立．设当时命题成立，则当时，若命题不成立，即同余方程（※）至少有个解，设为①，我们考虑多项式謀荞抟箧飆鐸怼类蒋薔。②，其中是l次多项式并且首项系数，满足，从而由归纳假设知l次同余方程③，至多有个l个解，但由①，②可知同余方程③至少有l＋1个解．，矛盾！故当时命题成立．综上所述，命题得证．厦礴恳蹒骈時盡继價骚。二.典型例题例1.已知正整数k≥2，为奇质数，且．证明：有不同于的奇质因数．证明：由，

5、有．由费尔马小定理，．又k≥2，为奇质数，则为正整数，从而，即12/12.同理，能被P2，P3，…Pk整除，从而不能被整除．注意到是一个偶数，则或1（mod4），因此4不整除，故异于的奇质因数．所以有异于的奇质因数．例2.对于自然数n，如果对于任何整数a，只要，就有，则称n具有性质P．（34届IMO预）（1）求证：每个素数n都具有性质P．（2）求证：有无穷多个合数也都具有性质P．证：（1）设为素数且，于是．由费尔马小定理知，而．故，即．因此，，．上述p个同余式累和，得．故，即．（2）设n是具有性质P的合数．若，则．由欧拉定理，有，又因

6、，由阶的性质知，．如果，则，于是利用（1）中证明可得．因此，问题化为求无穷多个合数n，使．对任何素数p≥5，取p－2的素因数q，并令．这时．因为，所以q(p－1)．又因q≤p－2＜p，故p(q－1)．因此，有．对于每个这样的合数n，若，则，因而，．故．因为对于每个素数p≥5都可按上述程序得到具有性质P的相应合数，且p＜＜p2，所以，有无穷多个合数n具有性质P．茕桢广鳓鯡选块网羈泪。例3.求所有整数n≥2，满足：对所有的整数a，b，且，的充分必要条件是．（第41届IMO预选题）解：若n有奇素因子p，设，记，．由中国剩余定理知，存在，使，

7、，则．取，即知，从而12/12，故，且．因此．取，即知，从而，故鹅娅尽損鹌惨歷茏鴛賴。．下证：当n取上述值时，满足条件．注意到，当2a时，有；当3a时，有，又，，故必有（因为）．对，且，，则．对，且，，则．从而又，有，即．综上，所求n的值为2，3，4，6，8，12，24．籟丛妈羥为贍偾蛏练淨。例4.求所有正整数n，满足对所有的正整数n，存在一个整数m，使是的因子．（第39届IMO预选题）解：引理1：若p为4k－1（k≥2）型质数，则不存在，使．证明：设（∵，∴m1存在），．又∵,∴．由费马小定理知，，矛盾．引理2：当1≤i＜j时，有，

8、且．证明：∵，∴．又∵，∴．对于原题，若，n≥2．设，2t．若t≥3，则，从而．又必存在4k－1型素数p，且，（否则，，矛盾）．此时，与引理1矛盾．故t=1，从而，且．由引理2及中国剩余定理知，存在，使，i=1，2，…，