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

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

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的缩系．这两个缩系分别乘起来得，且．从而．特别地，取m为质数p，有费尔马

2、（Fermat）小定理：设p为质数，a为整数，pa，则．它也常常写成．这里不需假定pa，但p应为素数．2.中国剩余定理（孙子定理）中国剩余定理：设是两两互质的正整数，是任意整数，则同余方程组对模有唯一解．解：设．依题设，有，由裴蜀定理知，存在整数，使得，．对，其中能被整除，而被除的余数恰为．从而是同余方程组的解．又设x，y均为同余方程组的解，则有，，…，，即，亦即．所以同余方程组对模有唯一解．3.威尔逊（wilson）定理11威尔逊（wilson）定理：设p为质数，则．解：对于任意整数a，且1≤a≤p－1，由裴蜀定理知，存在整数a’，使得．称a’为a的数论倒数，且不妨设1≤a

3、’≤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），则同余方程（※），至多有n个解（在模p的意义下）．证明：我们对n用归纳法．当时，，因为pa0，故同余方程（※）无解，命题成立．设当时命题成立，则当时，若命题不成立，即同余方程（※）至少有个解，设为①，我们考虑多项式②，其

4、中是l次多项式并且首项系数，满足，从而由归纳假设知l次同余方程③，至多有个l个解，但由①，②可知同余方程③至少有l＋1个解．，矛盾！故当时命题成立．综上所述，命题得证．二.典型例题例1.已知正整数k≥2，为奇质数，且．证明：有不同于的奇质因数．证明：由，有．由费尔马小定理，．又k≥2，为奇质数，则为正整数，从而，即.同理，能被P2，P3，…Pk整除，从而不能被11整除．注意到是一个偶数，则或1（mod4），因此4不整除，故异于的奇质因数．所以有异于的奇质因数．例2.对于自然数n，如果对于任何整数a，只要，就有，则称n具有性质P．（34届IMO预）（1）求证：每个素数n都具有性

5、质P．（2）求证：有无穷多个合数也都具有性质P．证：（1）设为素数且，于是．由费尔马小定理知，而．故，即．因此，，．上述p个同余式累和，得．故，即．（2）设n是具有性质P的合数．若，则．由欧拉定理，有，又因，由阶的性质知，．如果，则，于是利用（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.求所有整

6、数n≥2，满足：对所有的整数a，b，且，的充分必要条件是．（第41届IMO预选题）解：若n有奇素因子p，设，记，．由中国剩余定理知，存在，使，，则．取，即知，从而，故，且．因此．取，即知，从而，故11．下证：当n取上述值时，满足条件．注意到，当2a时，有；当3a时，有，又，，故必有（因为）．对，且，，则．对，且，，则．从而又，有，即．综上，所求n的值为2，3，4，6，8，12，24．例4.求所有正整数n，满足对所有的正整数n，存在一个整数m，使是的因子．（第39届IMO预选题）解：引理1：若p为4k－1（k≥2）型质数，则不存在，使．证明：设（∵，∴m1存在），．又∵,∴．由

7、费马小定理知，，矛盾．引理2：当1≤i＜j时，有，且．证明：∵，∴．又∵，∴．对于原题，若，n≥2．设，2t．若t≥3，则，从而．又必存在4k－1型素数p，且，（否则，，矛盾）．此时，与引理1矛盾．故t=1，从而，且．由引理2及中国剩余定理知，存在，使，i=1，2，…，s－1．故．令，有．因此，．综上，所求正整数n为2的幂次2i（i=1，2，…）．数论中存在性问题是最常见的，除了运用数论存在性定理来解决外，还需要有直接构造的能力．例5.证明：每个正有理数能被表示成的形式，且其中a，b，c，d是正整数．（