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

数论定理一. 知识要点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）小定理：设p为质数，a为整数，p a，则它也常常写成这里不需假定p a，但p应为素数2. 中国剩余定理（孙子定理）中国剩余定理：设是两两互质的正整数，是任意整数，则同余方程组对模有唯一解 解：设依题设，有，由裴蜀定理知，存在整数，使得，对，其中能被整除，而被除的余数恰为从而是同余方程组的解又设x，y均为同余方程组的解，则有，即，亦即所以同余方程组对模有唯一解3. 威尔逊（wilson）定理威尔逊（wilson）定理：设p为质数，则 解：对于任意整数a，且1ap1，由裴蜀定理知，存在整数a，使得称a为a的数论倒数，且不妨设1ap1若有整数b，满足，则将此式两边同乘以a，有这说明对于不同整数a，1ap1，对应着不同的数论倒数a又若整数a的数论倒数是它自身，则，亦即，故或当时，显然有当p2时，有2，3，p2这p3个数恰好配成互为数论倒数的对数，故它们的积于是4. 拉格朗日定理设p为质数，n是非负整数，多项式是一个模p为n次的整系数多项式（即p an），则同余方程 （），至多有n个解（在模p的意义下）证明：我们对n用归纳法当时，因为p a0，故同余方程（）无解，命题成立设当时命题成立，则当时，若命题不成立，即同余方程（）至少有个解，设为 ，我们考虑多项式 ，其中是l次多项式并且首项系数，满足，从而由归纳假设知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）设为素数且，于是由费尔马小定理知，而故，即因此，上述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，设，记，由中国剩余定理知，存在，使，则取，即知，从而，故，且因此取，即知，从而，故下证：当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，且，（否则，矛盾）此时，与引理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，则取，且结论成立说明：这里是直接构造证明，首先发现恒等式，进一步对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 | 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中第二天的压轴题，是本次竞赛中难度最大的一道试题其困难之处在于寻求一个合适的质数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整除，即有（这里实际上给出了威尔逊定理的另一种证明），于是（1）得证，即将x换成x即得，从而 ，对模p2并利用（1）可得，即，从而当l为奇数且1lp时，有说明：本例的结论是一个很有用的结论，应用它可解决一些问题例9. 确定所有的正整数对（n，p），满足：p是一个素数，n2p，且能够被整除（第40届IMO试题）分析：第40届IMO是题目很难的一届IMO，这道数论题是第二天测试的第1个题目，但仍然具有极大的难度这道题实际上是证明，很容易联想到利用阶的思想（但具体实现却存在着重重困难），最颇费思量的条件是n2p，莫非它有着某些暗示？解：当p=2时，只有整数n1，2满足要求下面考虑P为不小于3的奇质数的情形这时候，为奇数，故n只可能为奇数（因为n为的因子），先设n1设n的最小质因数为，则n可以表示成，其中，且q s，s为奇数（1），且s的每个质因数（如果s1的话）均大于q于是由可知，再根据费马小定理（注意p1与q互质），设l为p1对模q的阶，则我们又有如下三个关系式：根据定理8，可知， l s，l为偶数且由q及s的取法，故l2而1（modq），只可能是，故，又，从而题目条件化为若能被整除但它除了最后一项P2外每一项均被P3整除，矛盾故P只能等于3所求的，还有n1的平凡情形满足要求故所求的一切解为（2，2），（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）； （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），从而x30（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(modp)再注意到P 3（mod4），故是奇数，又由费马小定理，这不可能，故反设不成立，命题得证5. 解：最大的正数整数为提示：对每个，可表成形式，且0，1，2，b1，从而x能表成题目要求形式6. 解：提示：n3,而，又由二项式定理易得，故，k5而当n3，m103时，确有，故nm的最小值为1067. 解：设n2k当时，为完全平方米当mk1时，有，从而不是完全平方米数当mk1时，若有不是完全平方米数，设，其中a为正整数，于是将（*）模2k1便得，即又注意到，故，从而，因此，矛盾！综上所述，我们有8. 解：（1）由欧拉定理知，故注意到从而 （2）设则由l的最小性，知，从而说明：阶的性质便于解决一些涉及方幂的问题，在本讲例4、6中用到过9. 解：设因为120与都是偶数，可知r也是偶数定义根据费尔马小定理，对于k1，2，有所以，以下分两种情形讨论（1）当时，有（2）当时，且r是偶数，所以modp有，又因为同余方程的互不同余的解不起过r个，所以存少存在一个1，2，P1，使得ar有（因为1a,2a，（P1）a模P两两不同余，它们的构成缩剩余系统的一组代表）又因为，2（ar1）对这种情形，而r0当且仅当素数P3，且，则P分别为3，5，7，11，13，41，61记S3，5，7，11，13，31，41，61故F(P) 10. 解：用归纳构造，首选取233，其次设已取出k个数两两互质且，则令又由欧拉定理知1，2，k，故1，2，k因此1，2，k11. 解：首先注意到Fermat数，其中，且641和P6700417都是素数考察同余方程组 ， ， 由于2321，641，P是两两互素的，由中国剩余定理知其唯一解为即（其中、N）设（r为非负整数，t为奇数），令（1）当r0，1，2，3，4时，由于故，同时是合数（2）当r5时，由于，且同时，所以g(n)是合数（3）当时，由于同时所以g(n)是合数综上所述，对一切自然数n，g(n)k2n1都是合数12. 解：将S的所有17元子集记为A1、A2、，An，其中再定义Tk为满足下面要求的17元子集的集合：的元素之和我们的想法是证明事实上，只需要证明对一切，成立即可容易验证1999为质数，（17，1999）1，因而存在惟一的s1，2，1999，使17s1（mod1999）于是我们按如下方式构造一个映射：若（A为某一个17元集合BS，且B的元素之和A的元素之和17Sk1（mod1999），故，则定义f-1(B) A由f为一一映射可得，又，即S的所有17元“好子集”的个数为13. 解：1990是个与年份有关的数，在大多数情况下均可将其一般化为n由于直接构造所涉及情况太多，故可考虑归纳构造，只想