1、竞赛数学中的初等数论贾广素编著2006-8-21序言数论是竞赛数学中最重要的一部分，特别是在1991年，IMO在中国举行，国际上戏称那一年为数论年，因为6道IMO试题中有5道与数论有关。数论的魅力在于它可以适合小孩到老头，只要有算术基础的人均可以研究数论在前几年还盛传广东的一位农民数学爱好者证明了哥德巴赫猜想，当然，这一谣言最终被澄清了。可是这也说明了最难的数论问题，适合于任何人去研究。初等数论最基础的理论在于整除，由它可以演化出许多数论定理。做数论题，其实只要整除理论即可，然而要很快地解决数论问题，则要我们多见识，以及学习大量的解题技巧。这里我们介绍一下数论中必需的一个内容：对于，满足，其中
2、。除了在题目上选择我们努力做到精挑细选，在内容的安排上我们也尽量做到讲解详尽，明白。相信通过对本书学习，您可以对数论有一个大致的了解。希望我们共同学习，相互交流，在学习交流中，共同提高。编者：贾广素2006-8-21于山东济宁第一节整数的p进位制及其应用正整数有无穷多个，为了用有限个数字符号表示出无限多个正整数，人们发明了进位制，这是一种位值记数法。进位制的创立体现了有限与无限的对立统一关系，近几年来，国内与国际竞赛中关于“整数的进位制”有较多的体现，比如处理数字问题、处理整除问题及处理数列问题等等。在本节，我们着重介绍进位制及其广泛的应用。基础知识给定一个m位的正整数A，其各位上的数字分别记
3、为，则此数可以简记为：（其中）。由于我们所研究的整数通常是十进制的，因此A可以表示成10的次多项式，即，其中且，像这种10的多项式表示的数常常简记为。在我们的日常生活中，通常将下标10省略不写，并且连括号也不用，记作，以后我们所讲述的数字，若没有指明记数式的基，我们都认为它是十进制的数字。但是随着计算机的普及，整数的表示除了用十进制外，还常常用二进制、八进制甚至十六进制来表示。特别是现代社会人们越来越显示出对二进制的兴趣，究其原因，主要是二进制只使用0与1这两种数学符号，可以分别表示两种对立状态、或对立的性质、或对立的判断，所以二进制除了是一种记数方法以外，它还是一种十分有效的数学工具，可以用
4、来解决许多数学问题。为了具备一般性，我们给出正整数A的p进制表示：，其中且。而仍然为十进制数字，简记为。典例分析例1将一个十进制数字2004（若没有指明，我们也认为是十进制的数字）转化成二进制与八进制，并将其表示成多项式形式。分析与解答分析：用2作为除数（若化为p进位制就以p作为除数），除2004商1002，余数为0；再用2作为除数，除1002商501余数为0；如此继续下去，起到商为0为止。所得的各次余数按从左到右的顺序排列出来，便得到所化出的二进位制的数。解：各次商数被除数除数013715316212525050110022004211111010100各次余数故，；同理，有，。处理与数字有
5、关的问题，通常利用定义建立不定方程来求解。例2求满足的所有三位数。（1988年上海市竞赛试题）解：由于，则，从而；当时，；当时，；当时，；当时，；当时，；于是所求的三位数只有512。例3一个四位数，它的个位数字与百位数字相同。如果将这个四位数的数字顺序颠倒过来（即个位数字与千位数字互换，十位数字与百位数字互换），所得的新数减去原数，所得的差为7812，求原来的四位数。（1979年云南省竞赛题）解：设该数的千位数字、百位数字、十位数字分别为，则原数颠倒后的新数由得7812即比较式两端百位、十位、个位数字得由于原四位数的千位数字不能为0，所以，从而，又显然百位数字，所以。所以所求的原四位数为197
6、9。例4递增数列1,3，4,9，10,12,13，是由一些正整数组成，它们或是3的幂，或是若个不同的3的幂之和，求该数列的第100项。（第4届美国数学邀请赛试题）解：将已知数列写成3的方幂形式：易发现其项数恰好是自然数列对应形式的二进制表示：即由于100所以原数列的第100项为。例51987可以在b进制中写成三位数，如果，试确定所有可能的和。（1987年加拿大数学竞赛试题）解：易知，从而，即，由知。由知故；又因为有12个正约数，分别为1,2，3,6，9,18,109,218,327,654,981,1962，所以，从而。又由知例6设是五位数（第一个数码不是零），是由取消它的中间一个数码后所成的
7、四位数，试确定一切使得是整数。（第3届加拿大数学竞赛试题）解：设，其中且；而是整数，可证，即即，这显然是成立的；又可证，即即，这显然也是正确的。于是，即，又因为是整数，从而；于是，即即，而但3102知为正整数）从而，显然，因而推得其中。例7若且是其各位数字和的倍数，这样的有多少个？（2004年南昌竞赛试题）解：（1）若为个位数字时，显然适合，这种情况共有9种；（2）若为100时，也适合；（3）若为二位数时，不妨设，则，由题意得即即也就是；若显然适合，此种情况共有9种；若，则由，故若，则显然可以，此时共有2810个；若（）9，则或，这样的数共有24,42,48,84共4个；综上所述，共有9191
8、0433个。例8如果一个正整数在三进制下表示的各数字之和可以被3整除，那么我们称为“好的”，则前2005个“好的”正整数之和是多少？（2005年中国奥林匹克协作体夏令营试题）解：首先考虑“好的”非负整数，考察如下两个引理：引理1.在3个连续非负整数（是非负整数）中，有且仅有1个是“好的”。证明：在这三个非负整数的三进制表示中，0,1，2各在最后一位出现一次，其作各位数字相同，于是三个数各位数字之和是三个连续的正整数，其中有且仅有一个能被3整除（即“好的”），引理1得证。引理2.在9个连续非负整数（是非负整数）中，有且仅有3个是“好的”。把这3个“好的”非负整数化成三进制，0,1，2恰好在这三个
9、三进制数的最后一位各出现一次。证明：由引理1不难得知在9个连续非负整数（是非负整数）中，有且仅有3个是“好的”。另一方面，在这三个“好的”非负整数的三进制表示中，最高位与倒数第三位完全相同，倒数第二位分别取0,1，2。若它使它们成为“好的”非负整数，则最后一位不相同，引理2得证。将所有“好的”非负整数按从小到大的顺序排成一列，设第2004个“好的”非负整数为，根据引理1，得，即。设前个“好的”正整数之和为，由于前2003个“好的”正整数之和等于前2004个“好的”非负整数之和。因此；又因为和都是“好的”正整数。因此前2005年“好的”正整数之和是：。第二节 整数的性质及其应用（1）基础知识整数
10、的性质有很多，这里我们着重讨论整数的整除性、整数的奇偶性，质数与合数、完全平方数及整数的尾数等几个方面的应用。1整除的概念及其性质在高中数学竞赛中如果不加特殊说明，我们所涉及的数都是整数，所采用的字母也表示整数。定义：设是给定的数，若存在整数，使得则称整除，记作，并称是的一个约数(因子)，称是的一个倍数，如果不存在上述，则称不能整除记作 。由整除的定义，容易推出以下性质：(1)若且，则(传递性质)；(2)若且，则即为某一整数倍数的整数之集关于加、减运算封闭。若反复运用这一性质，易知及，则对于任意的整数有。更一般，若都是的倍数，则。或着，则其中；(3)若，则或者，或者，因此若且，则；(4)互质，
11、若，则；(5)是质数，若，则能整除中的某一个；特别地，若是质数，若，则；(6)(带余除法)设为整数，则存在整数和，使得，其中，并且和由上述条件唯一确定；整数被称为被除得的(不完全)商，数称为被除得的余数。注意：共有种可能的取值：0,1，。若，即为被整除的情形；易知，带余除法中的商实际上为（不超过的最大整数），而带余除法的核心是关于余数的不等式：。证明的基本手法是将分解为与一个整数之积，在较为初级的问题中，这种数的分解常通过在一些代数式的分解中取特殊值而产生，下面两个分解式在这类论证中应用很多，见例1、例2。若是正整数，则；若是正奇数，则；（在上式中用代）(7)如果在等式中取去某一项外，其余各项
12、均为的倍数，则这一项也是的倍数；(8)n个连续整数中，有且只有一个是n的倍数；(9)任何n个连续的整数之积一定是n!的倍数，特别地，三个连续的正整数之积能被6整除；2奇数、偶数有如下性质：(1)奇数奇数=偶数，偶数偶数偶数，奇数偶数奇数，偶数偶数偶数，奇数偶数偶数，奇数奇数奇数；即任意多个偶数的和、差、积仍为偶数，奇数个奇数的和、差仍为奇数，偶数个奇数的和、差为偶数，奇数与偶数的和为奇数，和为偶数；（2）奇数的平方都可以表示成的形式，偶数的平方可以表示为或的形式；（3）任何一个正整数，都可以写成的形式，其中为负整数，为奇数。（4）若有限个整数之积为奇数，则其中每个整数都是奇数；若有限个整数之积
13、为偶数，则这些整数中至少有一个是偶数；两个整数的和与差具有相同的奇偶性；偶数的平方根若是整数，它必为偶数。3完全平方数及其性质能表示为某整数的平方的数称为完全平方数，简称平方数。平方数有以下性质与结论：（1）平方数的个位数字只可能是0,1，4,5，6,9；（2）偶数的平方数是4的倍数，奇数的平方数被8除余1，即任何平方数被4除的余数只有可能是0或1；（3）奇数平方的十位数字是偶数；（4）十位数字是奇数的平方数的个位数一定是6；（5）不能被3整除的数的平方被3除余1，能被3整数的数的平方能被3整除。因而，平方数被9也合乎的余数为0,1，4,7，且此平方数的各位数字的和被9除的余数也只能是0,1，
14、4,7；（6）平方数的约数的个数为奇数；（7）任何四个连续整数的乘积加1，必定是一个平方数。（8）设正整数之积是一个正整数的次方幂（），若（）1，则都是整数的次方幂。一般地，设正整数之积是一个正整数的次方幂（），若两两互素，则都是正整数的k次方幂。4整数的尾数及其性质整数的个位数也称为整数的尾数，并记为。也称为尾数函数，尾数函数具有以下性质：（1）；（2）；（3）；（4）；（5）若，则；（6）；（7）；（8）5整数整除性的一些数码特征（即常见结论）（1）若一个整数的未位数字能被2（或5）整除，则这个数能被2（或5）整除，否则不能；（2）一个整数的数码之和能被3（或9）整除，则这个数能被3（或9
15、）整除，否则不能；（3）若一个整数的未两位数字能被4（或25）整除，则这个数能被4（或25）整除，否则不能；（4）若一个整数的未三位数字能被8（或125）整除，则这个数能被8（或125）整除，否则不能；（5）若一个整数的奇位上的数码之和与偶位上的数码之和的差是11的倍数，则这个数能被11整除，否则不能。6质数与合数及其性质1正整数分为三类：（1）单位数1；（2）质数（素数）：一个大于1的正整数，如果它的因数只有1和它本身，则称为质（素）数；（3）如果一个自然数包含有大于1而小于其本身的因子，则称这个自然数为合数。2有关质（素）数的一些性质（1）若，则的除1以外的最小正因数是一个质（素）数。如果
16、，则；（2）若是质（素）数，为任一整数，则必有或（）1；（3）设为个整数，为质（素）数，且，则必整除某个（）；（4）（算术基本定理）任何一个大于1的正整数，能唯一地表示成质（素）因数的乘积（不计较因数的排列顺序）；（5）任何大于1的整数能唯一地写成的形式，其中为质（素）数（）。上式叫做整数的标准分解式；（6）若的标准分解式为，的正因数的个数记为，则。典例分析例1证明：被1001整除。证明：所以整除。例2对正整数，记为的十进制表示中数码之和。证明：的充要条件是。证明：设（这里，且），则，于是有对于，知，故式右端个加项中的每一个都是9的倍数，从而由整除的性质可知它们的和也能被9整除，即。由此可易推
17、出结论的两个方面。例3设是一个奇数，证明L对于任意正整数，数不能被整除。证明：时，结论显然成立。设，记所说的和为A，则：。由k是正奇数，从而结于每一个，数被整除，故被除得余数为2，从而A不可能被整除（注意）。例4设是正整数，证明：（）（）。证明：首先，当时，易知结论成立。事实上，时，结论平凡；当时，结果可由推出来（注意）。最后，的情形可化为上述特殊情形：由带余除法而，由于，从而由若是正整数，则知；而，故由上面证明了的结论知（注意时结论平凡），从而当时，也有（）（）。这就证明了本题的结论。 例5设正整数满足，证明：不是质（素）数。证法一：由，可设其中。由意味着有理数的分子、分母约去了某个正整数后
18、得既约分数，因此，同理，存在正整数使得因此，是两个大于1的整数之积，从而不是素数。注：若正整数适合，则可分解为及的形式，这一结果在某些问题的解决中很有作用。证法二：由，得，因此，因为是整数，故也是整数。若它是一个素数，设为，则由可见整除，从而素数整除或。不妨设，则，结合推出，而这是不可能的（因为）。例6求出有序整数对（）的个数，其中，是完全平方数。（1999年美国数学邀请赛试题）解：由于，可得：。又，于是若是完全平方数，则必有。然而，于是必有，即，此时，。所以所求的有序整数对（）共有98对：。例7证明：若正整数满足，则和都是完全平方数。（2006年山东省第二届夏令营试题）证法一：已知关系式即为
19、（）（）若（或者说中有一个为0时），结论显然。不妨设且，令，则，从而，将其代入得因为，所以，从而；而式又可写成；因为且，所以所以，从而。所以，所以，从而为完全平方数。所以也是完全平方数。证法二：已知关系式即为（）（）论证的关键是证明正整数与互素。记（，）。若，则有素因子，从而由知。因为是素数，故，结合知，从而由得1，这是不可能的。故，从而由推知正整数与都是完全平方数。例8证明不存在正整数，使2n2+1，3n2+1，6n2+1都是完全平方数。证明：假设存在这样的正整数，使2n2+1，3n2+1，6n2+1都是完全平方数，那么（2n2+1）（3n2+1）（6n2+1）也必定是完全平方数。而（2n2
20、+1）（3n2+1）（6n2+1）36n6+36n4+11n2+1；36n6+36n4+9n2；36n6+36n4+12n3+9n2+6n+1；所以（2n2+1）（3n2+1）（6n2+1）与（2n2+1）（3n2+1）（6n2+1）为完全平方数矛盾。例9数列的通项公式为，记，求所有的正整数，使得能被8整除（2005年上海竞赛试题）解：记注意到，可得因此，Sn+2除以8的余数，完全由Sn+1、Sn除以8的余数确定，故由(*)式可以算出各项除以8的余数依次是1,3，0,5，7,0，1,3，它是一个以6为周期的数列，从而故当且仅当练习题1证明：如果和都是大于3的素数，则6是的因子。证明：因为是奇数
21、，所以2是的因子。又因为，除以3的余数各不相同，而与都不能被3整数。于是6是的因子。2设，证明：；解：由，故（）。又因为，从而，于是由整除的性质知。3证明：对于任意正整数，数不能被整除。证明：只需证2（）2（）即可。因为若是正整数，则；若是正奇数，则；故；， 所以2（）。又因为，所以2，所以2（）2即（）2（）命题得证。4已知为正奇数，求证：。证明：因为若是正整数，则；若是正奇数，则；所以，从而；，从而；，从而；又且，所以。5设a、b、c为满足不等式1abc的整数，且（ab-1）（bc-1）（ca-1）能被abc整除，求所有可能数组（a，b，c）.（1989年上海竞赛试题）解 （ab-1）（b
22、c-1）（ca-1）=a2b2c2-abc（a+b+c）+ab+ac+bc-1，abc|（ab-1）（bc-1）（ca-1）.存在正整数k,使ab+ac+bc-1=kabc, k=k=1.若a3，此时1=-矛盾.已知a1. 只有a=2.当a=2时，代入中得2b+2c-1=bc，即 1=0b4，知b=3，从而易得c=5. 说明：在此例中通过对因数k的范围讨论，从而逐步确定a、b、c是一项重要解题技巧.第三节整数的性质及其应用（2）基础知识最大公约数与最小公倍数是数论中的一个重要的概念，这里我们主要讨论两个整数互素、最大公约数、最小公倍数等基本概念与性质。定义1.（最大公约数）设不全为零，同时整除
23、的整数（如）称为它们的公约数。因为不全为零，故只有有限多个，我们将其中最大一个称为的最大公约数，用符号（）表示。显然，最大公约数是一个正整数。当（）1（即的公约数只有）时，我们称与互素（互质）。这是数论中的非常重要的一个概念。同样，如果对于多个（不全为零）的整数，可类似地定义它们的最大公约数（）。若（）1，则称互素。请注意，此时不能推出两两互素；但反过来，若（）两两互素，则显然有（）1。由最大公约数的定义，我们不难得出最大公约数的一些简单性质：例如任意改变的符号，不改变（）的值，即；（）可以交换，（）（）；（）作为的函数，以为周期，即对于任意的实数，有（）（）等等。为了更详细地介绍最大公约数，
24、我们给出一些常用的一些性质：（1）设是不全为0的整数，则存在整数，使得；（2）（裴蜀定理）两个整数互素的充要条件是存在整数，使得；事实上，条件的必要性是性质（1）的一个特例。反过来，若有使等式成立，不妨设，则，故及，于是，即，从而。（3）若，则，即的任何一个公约数都是它们的最大公约数的约数；（4）若，则；（5）若，则，因此两个不互素的整数，可以自然地产生一对互素的整数；（6）若，则，也就是说，与一个固定整数互素的整数集关于乘法封闭。并由此可以推出：若，对于有，进而有对有。（7）设，若，则；（8）设正整数之积是一个正整数的次方幂（），若（）1，则都是整数的次方幂。一般地，设正整数之积是一个正整数
25、的次方幂（），若两两互素，则都是正整数的次方幂。定义2.设是两个非零整数，一个同时为倍数的数称为它们的公倍数，的公倍数有无穷多个，这其中最小的一个称为的最小公倍数，记作，对于多个非零实数，可类似地定义它们的最小公倍数。最小公倍数主要有以下几条性质：（1）与的任一公倍数都是的倍数，对于多于两个数的情形，类似结论也成立；（2）两个整数的最大公约数与最小公倍满足：（但请注意，这只限于两个整数的情形，对于多于两个整数的情形，类似结论不成立）；（3）若两两互素，则；（4）若，且两两互素，则。典例分析例1 设是正整数，且，它们的最小公倍数是最大公约数的120倍，求。解：设，则，其中且，于是。所以即由及（2
26、）可得：。由（1）可知只能取从而或29，故或。例2设，则。证明：设，则，其中。于是，已知条件转化为，故更有，从而转化为，但是，故，结合，知必有，同时，因此。例3设正整数的最大公约数是1，并且，证明是一个完全平方数。证明：设，则，其中，由于，故，现在问题中的等式可以转化为由此可见整除。因为，故，同样可得，再由便可以推出。设，其中是一个正整数。一方面，显然整除；另一方面，结合式，得，故，从而，但，故。因此，故，这样就证明了是一个完全平方数。例4 都是正整数，是否存在整数使得对任意的正整数，与互质？解：令，则，于是存在整数使得，令，则对任意的正整数，设，有即，而，所以，即对任意的正整数，（，）1。例
27、5 已知，证明：对于任意的正整数，都有两两互素。（2002年克罗地亚竞赛试题）证明：设（其中出现次）。由，故对于有，则是含有0次项的多项式。因此，除以的余数为1。设整数可整除和，又，则当除以时余数为1，即1。所以，矛盾！从而可知两两互素。例6求出所有的正整数对，使得是一个整数。（2006年山东省第二届夏令营试题）解：由于且，所以是对称的。不妨设。当时，则，从而2；当时，若时，则有，所以或3；若时，由于是一个整数，从而使得即，所以。又由于，所以。所以，从而得或3，所以；综上知所有的为（2,2）,(2,1),(1,2),(3,1),(1,3),(5,2),(2,5),(5,3),(3,5).例7已
28、知，且，试问的充要条件是吗？（2006年山东省第二届夏令营试题）分析：因为，所以；又，所以；令，则有又因为，所以从而上式且为奇数，即的充要条件是且为奇数。例8我们知道有1个质因子，且；有2个质因子，且如此下去，我们可以猜想： 至少有个质因子，且。试证明之。（2006年山东省第二届夏令营试题）证明：令，则，即要证是整数且有个质因子。下用数学归纳法证明是整数。时，结论显然；假设时，成立；当1时，因为(1)3+1=3323；因为，所以，即是整数。下证至少有个质因子。3323()33()23().因为()，令，则由于(,3)=1，所以(,)=1，从而必有异于质因子的质因子，所以至少有个质因子。证毕！练
29、习1若是奇数，则。分析：要证明与互质，我们只需要证明它们的公因子为1即可，但是这对于不好处理，由为奇数这一条件，我们可以想到从而找到思路。证明：由于为奇数，故，又，从而（，）（），而（）（2）1，故。2若17|(2a+3b),试证：17|(9a+5b).证明：注意到2(9a+5b)=9(2a+3b)17b,于是17|2(9a+5b).但是(17,2)=1,即得17|(9a+5b).3设是正整数，若不是整数，则必为无理数。证明：设是非整数的有理数，则可设，于是。因为故可知。但，因而。这与是整数矛盾！证毕。4设a,b是不全为0的整数，一切形如ax+by的数中，最小的正数是d，试证：d=(a,b).
30、5.记Fn1，试证：(Fn,Fm)=1,这里.第四节同余同余式性质应用非常广泛，在处理某些整除性、进位制、对整数分类、解不定方程等方面的问题中有着不可替代的功能，与之密切相关的的数论定理有欧拉定理、费尔马定理和中国剩余定理。基础知识三个数论函数对于任何正整数均有定义的函数，称为数论函数。在初等数论中，所能用到的无非也就有三个，分别为：高斯(Gauss)取整函数x及其性质，除数函数d(n)和欧拉(Euler)函数和它的计算公式。1 高斯(Gauss)取整函数设是实数，不大于的最大整数称为的整数部分，记为；称为的小数部分，记为。例如：0.50，等等。由的定义可得如下性质：性质1.；性质2.；性质3
31、.设，则；性质4.;性质5.；性质6.对于任意的正整数，都有如下的埃米特恒等式成立：；为了描述性质7，我们给出如下记号：若，且，则称为恰好整除，记为。例如：我们有等等，其实，由整数唯一分解定理：任何大于1的整数能唯一地写成的形式，其中为质（素）数（）。我们还可以得到：。性质7.若，则请注意，此式虽然被写成了无限的形式，但实际上对于固定的，必存在正整数，使得，因而，故，而且对于时，都有。因此，上式实际上是有限项的和。另外，此式也指出了乘数的标准分解式中，素因数的指数的计算方法。2除数函数d(n)正整数的正因数的个数称为除数函数，记为d(n)。这里给出d(n)的计算公式：d(n)，为素数唯一分解定
32、理中的指数。为了叙述地更加明确，我们组出素数唯一分解定理。算术基本定理（素数唯一分解定理）：任何一大于1的整数均可以分解为素数的乘积，若不考虑素数乘积的先后顺序，则分解式是唯一的。例如：。当一个整数分解成素数的乘积时，其中有些素数可以重复出现。例如在上面的分解式中，2出现了三次。把分解式中相同的素数的积写成幂的形式，我们就可以把大于1的正整数写成（1）此式称为的标准分解式。这样，算术基本定理也可以描述为大于1的整数的标准分解式是唯一的（不考虑乘积的先后顺序）。推论1.若的标准分解式是（1）式，则是的正因数的充要条件是：（2）应说明（2）不能称为是的标准分解式，其原因是其中的某些可能取零值（也有
33、可能不含有某个素因数，因而）推论2.设，且，若是整数的次方，则也是整数的次方。特别地，若是整数的平方，则也是整数的平方。3. 欧拉(Euler)函数设正整数0,1，中与互素的个数，称之为的欧拉函数，并记为。若的标准分解式是，则的计算公式是：例如：； .以下我们讲述同余的概念：同余的概念是高斯（Gauss）在1800年左右给出的。设是正整数，若用去除整数，所得的余数相同，则称为与关于模同余，记作，否则，称为与关于模不同余。定义1.（同余）设，若，则称和对模同余，记作；若不然，则称和对模不同余，记作。例如：，等等。当时，则称是对模的最小非负剩余。由带余除法可知，和对模同余的充要条件是与被除得的余数
34、相同。对于固定的模，模的同余式与通常的等式有许多类似的性质：性质1. 的充要条件是也即。性质2.同余关系满足以下规律：（1）（反身性）；（2）（对称性）若，则；（3）（传递性）若，则；（4）（同余式相加）若，则；（5）（同余式相乘）若，则；反复利用（4）（5），可以对多个两个的（模相同的）同余式建立加、减和乘法的运算公式。特别地，由（5）易推出：若，为整数且，则；但是同余式的消去律一般并不成立，即从未必能推出，可是我们却有以下结果：（6）若，则，由此可以推出，若，则有，即在与互素时，可以在原同余式两边约去而不改变模（这一点再一次说明了互素的重要性）。现在提及几个与模相关的简单而有用的性质：（7
35、）若，则；（8）若，则；（9）若，则，特别地，若两两互素时，则有；性质3.若，则；性质4.设是系数全为整数的多项式，若，则。这一性质在计算时特别有用：在计算大数字的式子时，可以改变成与它同余的小的数字，使计算大大地简化。如例3。定义2.设，是使成立的最小正整，则称为对模的阶。在取定某数后，按照同余关系把彼此同余的整数归为一类，这些数称为模的剩余类。一个类的任何一个数，都称为该类所有数的剩余。显然，同类的余数相同，不同类的余数不相同，这样我们就把全体整数按照模划分为了个剩余类：。在上述的个剩余类中，每一类任意取一个剩余，可以得到个数，称为模的一个完全剩余系。例如关系模7，下面的每一组数都是一个完
36、全剩余系：0，1，2，3，4，5，6；-7，8，16，3，-10，40，20；-3，-2，-1，0，1，2，3。 显然，一组整数成为模的完全剩余系只需要满足两个条件（1）有个数；（2）各数关于模两两不同余。最常用的完全剩余系是最小非负完全剩余系及绝对值最小完全剩余系。模的最小非负完全剩余系是：0，1，2，,;即除数为时，余数可能取到的数的全部值。当为奇数时，绝对值最小的完全剩余系是：；当为偶数时，绝对值最小的完全剩余系有两个：；。以上只是我们个人对同余及剩余类的理解，为了方便大家研究，我们把有关材料上的具体概念给出，希望大家好好地研究：定义3.（同余类）设，每一个这样的类为模的同余类。说明：整
37、数集合可以按模来分类，确切地说，若和模同余，则和属同一类，否则不属于同一类，每一个这样的类为模的一个同余类。由带余除法，任一整数必恰与0,1,，中的一个模同余，而0,1,，这个数彼此模不同余，因此模共有个不同的同余类，即。例如，模2的同余类共有两个，即通常说的偶数类与奇数类，这两类中的数分别具有形式和（为任意整数）。定义4。（剩余类）设是正整数，把全体整按对模的余数分成类，相应的个集合记为：，其中，称为模的一个剩余类。以下是几条常用性质：（1）且；（2）每一个整数仅在的一个里；（3）对于任意，则的充要条件是。定义5.（完全剩余系）一组数称为模的完全剩余系，如果对任意有且仅有一个是对模的剩余，即
38、。换一种说法更好理解：设为模的全部剩余类，从每个中任取一个，得个数组成的数组，叫做模的一个完全剩余系。说明：在个剩余类中各任取一个数作为代表，这样的个数称为模的一个完全剩余系，简称模的完系。换句话说，个数称为模的一个完系，是指它们彼此模不同余，例如0,1，2，是模的一个完系，这称作是模的最小非负完系。性质：（1）个整数构成模的一个完全剩余系两两对模不同余；（2）若，则与同时跑遍模的完全剩余系。典例分析例1试解方程：。解：因为左边是整数，因而右边的分式也应该是整数，所以于是，从而，故。但是是整数，故，代入前面的不等式，得，直接观察即知，于是。例2数100！的十进位制表示中，未尾连续地有多少位全是
39、零？解：命题等价于100！最多可以被10的多少次方整除。因为因而100！中2的指数大于5的指数，所以100！中5的指数就是所需求出的零的位数。由即可知100！的未尾连续地有24位全是数码零。例3试求被50除所得的余数。解：由于是关于的整系数多项式，而，于是知。又注意到，故又，所以注意到，因而29就是所求的余数。说明：在上述过程中，我们已经看到的作用。一般而言，知道一个整数的多少次幂关于模同余于是非常有用的。事实上，若，则对大的指数利用带余除法定理，可得，于是有，这里余数是一个比小得多的数，这样一来，计算的问题，就转化成了计算余数次幂的问题，从而使计算简单化。例4设，计算某星期一后的第天是6星期
40、几？解；星期几的问题是被7除求余数的问题。由于，于是，因而。为了把指数的指数写成的形式，还需取6为模来计算。为此我们有，进而有，依次类推，有，所以从而，这样，星期一后的第天将是星期五。例5求所有的素数，使与也是素数。分析：要使与也是素数，应该是对除以某个数素的余数进行分类讨论，最后确定只能是这个素数。由于只有两个数，所以不能太大，那样讨论起来也不会有什么效果，试验发现对本题不起任何效果，现对展开讨论。解：设，且若或4时，；若或3时，；即时，为5的倍数且比5大，不为质数。故，此时，；都是素数。即可题有唯一解。注：要使几个数同为质数，一般是对这几个数也合乎以某一质数的余数来确定，如均为质数，可得只
41、能为3，由于这是的一次式，故三个数就模3，而二次式对三个数就模5，四个数一般就模7了。例6求满足的全部正整数。分析：如果，两边，得，这是不可能的；如果，而中有一个大于1，则另一个也大于1，得，故为奇数，得，而，为奇数，从而，矛盾！所以为唯一解。注：在解不定方程时，往往要分情况讨论，也常常利用同余来导出一些性质求出矛盾！例7数列满足：证明：（1）对任意为正整数；(2)对任意为完全平方数。（2005年全国高中数学联赛试题）证明：（1）由题设得且严格单调递增.将条件式变形得两边平方整理得-得由式及可知，对任意为正整数.（2）将两边配方，得由式0（mod3）为正整数，式成立.是完全平方数.例8若可以写
42、成有限小数，那么自然数的值是多少？解：由于若与互素，则分数是既约分数；若与不互素，设它们的公约数为，且，设，则，故与的公约数是5，此时分数的分子、分母只有公约数5。由于可以写成有限小数，故约分之后的分母除了2,5以外，没还有其它的公约数，因此。因为是奇数，故，即。由于故，从而，即，故只有才是有限小数。练习1 试求方程的实数解。（答案：）2 若，试出至少5个的值。（答案：17，32，34，40，48）3 试求被25除所得的余数。（答案：24）4 设整数使，这些中最小的正整数为，试证：。特别地，若，则。证明：设，则易知，但是最小的正整数，故只能为0，即。5 设是任意整数，试证下面形状的数都不是完全
43、平方数：（1）；（2）。解：（1）不同余； （2）或3，但或1。6 求所有满足的正整数三元组。第五节初等数论中的几个重要定理基础知识定义（欧拉(Euler)函数）一组数称为是模的既约剩余系，如果对任意的，且对于任意的，若1，则有且仅有一个是对模的剩余，即。并定义中和互质的数的个数，称为欧拉（Euler）函数。这是数论中的非常重要的一个函数，显然，而对于，就是1,2，中与互素的数的个数，比如说是素数，则有。引理：；可用容斥定理来证（证明略）。定理1：（欧拉（Euler）定理）设1，则。证明：取模的一个既约剩余系，考虑，由于与互质，故仍与互质，且有，于是对每个都能找到唯一的一个，使得，这种对应关系是一一的，从而，。，故。证毕。分析与解答：要证，我们得设法找出个相乘，由个数我们想到中与互质的的个数：，由于1，从而也是与互质的个数，且两两余数不一样，故（），而（）1，故。这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。定理2：（费尔马（Fermat）小定理）对于质数及任意整数有。设为质数，若是的倍数，则。若不是的倍数，则由引理及欧拉定理得，由此即得。定理推论：设为质数，是与互质的任一整数，则。定理3：（威尔逊（Wilson）定理）设为质数，则。分析与解答：受欧拉定理的影响，我们也找个数，然后来对应乘法。证明：对于，在中，必然有一个数除
