《全国高中数学竞赛专题座同余理论及其应用技术(二)》由会员分享，可在线阅读，更多相关《全国高中数学竞赛专题座同余理论及其应用技术(二)（12页珍藏版）》请在金锄头文库上搜索。
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，有费尔马（Fermat
2、）小定理：设p为质数，a为整数，pa，则它也常常写成这里不需假定pa，但p应为素数聞創沟燴鐺險爱氇谴净。2. 中国剩余定理（孙子定理）中国剩余定理：设是两两互质的正整数，是任意整数，则同余方程组对模有唯一解解：设依题设，有，由裴蜀定理知，存在整数，使得，对，其中能被整除，而被除的余数恰为从而是同余方程组的解又设x，y均为同余方程组的解，则有，即，亦即所以同余方程组对模有唯一解残骛楼諍锩瀨濟溆塹籟。3. 威尔逊（wilson）定理威尔逊（wilson）定理：设p为质数，则解：对于任意整数a，且1ap1，由裴蜀定理知，存在整数a，使得称a为a的数论倒数，且不妨设1ap1若有整数b，满足，则将此式两
3、边同乘以a，有这说明对于不同整数a，1ap1，对应着不同的数论倒数a又若整数a的数论倒数是它自身，则，亦即，故或当时，显然有当p2时，有2，3，p2这p3个数恰好配成互为数论倒数的对数，故它们的积于是酽锕极額閉镇桧猪訣锥。4. 拉格朗日定理设p为质数，n是非负整数，多项式是一个模p为n次的整系数多项式（即pan），则同余方程（），至多有n个解（在模p的意义下）彈贸摄尔霁毙攬砖卤庑。证明：我们对n用归纳法当时，因为pa0，故同余方程（）无解，命题成立设当时命题成立，则当时，若命题不成立，即同余方程（）至少有个解，设为，我们考虑多项式謀荞抟箧飆鐸怼类蒋薔。，其中是l次多项式并且首项系数，满足，从而
4、由归纳假设知l次同余方程，至多有个l个解，但由，可知同余方程至少有l1个解，矛盾！故当时命题成立综上所述，命题得证厦礴恳蹒骈時盡继價骚。二. 典型例题例1. 已知正整数k2，为奇质数，且证明：有不同于的奇质因数证明：由，有由费尔马小定理，又k2，为奇质数，则为正整数，从而，即.同理，能被P2，P3，Pk整除，从而不能被整除注意到是一个偶数，则或1（mod4），因此4不整除，故异于的奇质因数所以有异于的奇质因数例2.对于自然数n，如果对于任何整数a，只要，就有，则称n具有性质P（34届IMO预）（1）求证：每个素数n都具有性质P（2）求证：有无穷多个合数也都具有性质P证：（1）设为素数且，于是由
5、费尔马小定理知，而故，即因此，上述p个同余式累和，得故，即（2）设n是具有性质P的合数若，则由欧拉定理，有，又因，由阶的性质知，如果，则，于是利用（1）中证明可得因此，问题化为求无穷多个合数n，使对任何素数p5，取p2的素因数q，并令这时因为，所以q (p1)又因qp2p，故p (q1)因此，有对于每个这样的合数n，若，则，因而，故因为对于每个素数p5都可按上述程序得到具有性质P的相应合数，且pp2，所以，有无穷多个合数n具有性质P茕桢广鳓鯡选块网羈泪。例3. 求所有整数n2，满足：对所有的整数a，b，且，的充分必要条件是（第41届IMO预选题）解：若n有奇素因子p，设，记，由中国剩余定理知，
6、存在，使，则取，即知，从而，故，且因此取，即知，从而，故鹅娅尽損鹌惨歷茏鴛賴。下证：当n取上述值时，满足条件注意到，当2 a时，有；当3 a时，有，又，故必有（因为）对，且，则对，且， ，则从而又，有，即综上，所求n的值为2，3，4，6，8，12，24籟丛妈羥为贍偾蛏练淨。例4. 求所有正整数n，满足对所有的正整数n，存在一个整数m，使是的因子（第39届IMO预选题）解：引理1：若p为4k1（k2）型质数，则不存在，使证明：设（，m1存在），又, 由费马小定理知，矛盾引理2：当1ij时，有，且证明：，又，对于原题，若，n2设，2 t若t3，则，从而又必存在4k1型素数p，且，（否则，矛盾）此时
7、，与引理1矛盾故t=1，从而，且由引理2及中国剩余定理知，存在，使，i=1，2，s1故預頌圣鉉儐歲龈讶骅籴。令，有因此，综上，所求正整数n为2的幂次2i（i=1，2，）数论中存在性问题是最常见的，除了运用数论存在性定理来解决外，还需要有直接构造的能力例5. 证明：每个正有理数能被表示成的形式，且其中a，b，c，d是正整数（40届IMO预选题）证明：设该正有理数为p（1）当时，其中2p1，2p，p1（2）当p2时，由于，故有，使，由（1）有（3）当时，由于，故有，使，由（1）有综上，总有，使,设ma1，mb1，c1，d1的分母公倍数为n，则取，且结论成立渗釤呛俨匀谔鱉调硯錦。说明：这里是直接构造
8、证明，首先发现恒等式，进一步对p2，或0p构造例6.证明：不存在非负整数k和m，使得铙誅卧泻噦圣骋贶頂廡。证明：注意到或时，上述不定方程无解，于是，可设满足上述方程的k，m为正整数（1）若为合数，设，2pq，注意到，应有48 | k！故k6，于是12pk，故（）| k！，进而（）| 48，结合7，可知=8，12，24或48，分别代入，两边约去48后，可得矛盾（2）若为质数，由威尔逊定理，可知k！，于是，| 47，进而=47，这要求46！48=4847m，从而m1，两边除以48可知，两边模4，可知，故m为偶数设m=2k，则由可知2，由232 |，而，故232 | ，利用二项式定理，从而23 |
9、k，进而m46，这时，式右边比左边大矛盾擁締凤袜备訊顎轮烂蔷。注：一般地，若n4，且n为合数，则n |（n1）！，依此可以证明威尔逊定理的逆定理也成立例7. 设p是质数，证明：存在一个质数q，使得对任意整数n，数不是q的倍数（第44届IMO试题）证明：由于则中至少有一个质因子q，满足q对的模不等于1。下面证明q为所求假设存在整数n，使得，则由q的选取，有另一方面，由费马小定理，有（由于q为质数且）由于p2 (q1)，有，因此，从而，这则导出1PPP1P（modp）。由q的选取，有，矛盾所以，命题成立贓熱俣阃歲匱阊邺镓騷。注：此题是第44届IMO中第二天的压轴题，是本次竞赛中难度最大的一道试题其
10、困难之处在于寻求一个合适的质数q，只需将其取为的一个恰当的质因子当年参赛的中国队的6名国家队员中仅有2人解出了此题，本题的难度由此可见坛摶乡囂忏蒌鍥铃氈淚。例8.设p3是质数，A1表示集合1，2，p1中两两不同的l个正整数的乘积之和，即A1=12（p1），A2=1213（p2）（p1），Ap1=（p1）！证明：蜡變黲癟報伥铉锚鈰赘。（1）当1lp2时，；（2）当1lp且l为奇数时，解：设，则同余方程有p1个解x=1，2，p1由费马小定理可知也有p1个解x=1，2，p1从而同余方程至少有p1个解但是買鲷鴯譖昙膚遙闫撷凄。是p2次多项式，故由拉格朗日定理知的各项系数均能被p整除，即有（这里实际上给
11、出了威尔逊定理的另一种证明），于是（1）得证，綾镝鯛駕櫬鹕踪韦辚糴。，即将x换成x即得，从而，对模p2并利用（1）可得，即，从而当l为奇数且1lp时，有说明：本例的结论是一个很有用的结论，应用它可解决一些问题驅踬髏彦浃绥譎饴憂锦。例9. 确定所有的正整数对（n，p），满足：p是一个素数，n2p，且能够被整除（第40届IMO试题）猫虿驢绘燈鮒诛髅貺庑。分析：第40届IMO是题目很难的一届IMO，这道数论题是第二天测试的第1个题目，但仍然具有极大的难度这道题实际上是证明，很容易联想到利用阶的思想（但具体实现却存在着重重困难），最颇费思量的条件是n2p，莫非它有着某些暗示？锹籁饗迳琐筆襖鸥娅薔。解：
12、当p=2时，只有整数n1，2满足要求下面考虑P为不小于3的奇质数的情形这时候，为奇数，故n只可能为奇数（因为n为的因子），先设n1设n的最小质因数为，则n可以表示成，其中，且q s，s为奇数（1），且s的每个质因数（如果s1的话）均大于q于是由可知，再根据费马小定理（注意p1与q互质），设l为p1对模q的阶，则我们又有如下三个关系式：根据定理8，可知， ls，l为偶数且由q及s的取法，故l2而1（modq），只可能是，故，又，从而题目条件化为若能被整除但構氽頑黉碩饨荠龈话骛。它除了最后一项P2外每一项均被P3整除，矛盾故P只能等于3所求的，还有n1的平凡情形满足要求故所求的一切解为（2，2），
13、（3，3），（1，P）（P为任意质数）輒峄陽檉簖疖網儂號泶。三. 训练题1. 13（50）20011742001模1989的最小非负剩余为2. 81除以一个正整数n，在它的小数部分的4个连续数位上出现了1995，则满足这样的要求的最小的n尧侧閆繭絳闕绚勵蜆贅。3. 证明数列11，111，1111，中无完全平方数4. 设P为型的质数，a、b为整数且能被P整除，则5. 不能表示成形式的最大正整数是多少？这里a、b是给定的两个互质正整数6. 设n1，求最小的，使得7. 已知正整数满足mn是偶数，并且为完全平方数求证：8. 满足（这a是整数，m1，且（a、m）1）的最小正整数l称为a模m的阶证明：（1
14、）；（2）设正整数t使得，则9.对素数，定义，求的值（第34届IMO中国国家队选拔考试）10. 证明：数列2n3,n2，3，4中有一个无穷子数列，其中的项两两互质11. 证明：存在一个正整数k，使得对各个正整数n，数是合数12. 集合S1，2，3，4，5，1999，若S的一个非空子集的元素之和恰好是1999的倍数，则称这个集为S的“好子集”求S的所有17元“好子集”个数识饒鎂錕缢灩筧嚌俨淒。13.能否找到1990个自然数的集合S，使（1）S中任意两数互质；（2）S中任意个数的和为合数四. 参考答案1. 30因198991317，记原数为x，则x4（mod13），x4（mod17），x3（mod9），从而x凍鈹鋨劳臘锴痫婦胫籴。30（mod1989）2. 401设1995，而8110ktnr，这里1rn1995再设若，则由若，则由，可得而，于是,又，注意意到，结合可得，而故401是最小的3.解：因113（mod4），111100113（mod4），11111100113（mod4），即数列的每一项mod4均余3，而，a20或1（mod4），故所给数列中无安全平方数恥諤銪灭萦欢煬鞏鹜錦。4.解：采用反证法反设P a，则P b，且a2b2
