数学奥赛辅导第二讲 整除

1数学奥赛辅导第二讲整除知识、方法、技能整除是整数的一个重要内容，这里仅介绍其中的几个方面：整数的整除性、最大公约数、最小公倍数、方幂问题。Ⅰ.整数的整除性初等数论的基本研究对象是自然数集合及整数集合。我们知道，整数集合中可以作加、减、乘法运算，并且这些运算满足一些规律（即加法和乘法的结合律和交换律，加法与乘法的分配律），但一般不能做除法，即，如ba,是整除，0b，则ba不一定是整数。由此引出初等数论中第一个基本概念：整数的整除性。定义一：（带余除法）对于任一整数a和任一整数b，必有惟一的一对整数q，r使得rbqa，br0，并且整数q和r由上述条件惟一确定，则q称为b除a的不完全商，r称为b除a的余数。若0r，则称b整除a，或a被b整除，或称ba是的倍数，或称ab是的约数（又叫因子），记为ab|。否则，b|a。任何a的非1,a的约数，叫做a的真约数。0是任何整数的倍数，1是任何整数的约数。任一非零的整数是其本身的约数，也是其本身的倍数。由整除的定义，不难得出整除的如下性质：（1）若.|,|,|cacbba则（2）若.,,2,1,,|,|1niZcbcabainiiii其中则（3）若ca|，则.|cbab反之，亦成立。2（4）若||||,|baba则。因此，若baabba则又,|,|。（5）a、b互质，若.|,|,|cabcbca则（6）p为质数，若,|21naaap则p必能整除naaa,,,21中的某一个。特别地，若p为质数，.|,|apapn则（7）如在等式mkkniiba11中除开某一项外，其余各项都是c的倍数，则这一项也是c的倍数。（8）n个连续整数中有且只有一个是n的倍数。（9）任何n个连续整数之积一定是n的倍数。本讲开始在整除的定义同时给出了约数的概念，又由上一讲的算术基本定理，我们就可以讨论整数的约数的个数了。定理一：设大于1的整数a的标准分解式为nnppppppan211(21为质数，i均为非负整数），则a的约数的个数为niiad1)1)(（。所有的约数和为：niiippai1111)(。事实上，由算术基本定理的推论知niiad1)1()(，而各约数的和就是niiiipap1)1(展开后的各项之和，所以niniiiippppaii11111)1()(3例如，25200=24·32·52·7，所以90)11)(12)(12)(14()25200(d，999441717151513131212)25200(2335。Ⅱ.最大公约数和最小公倍数定义二：设a、b是两个不全为0的整数。若整数c满足：bcac|,|，则称bac,为的公约数，ba与的所有公约数中的最大者称为ba与的最大公约数，记为),(ba。如果),(ba=1，则称ba与互质或互素。定义三：如果ad是、b的倍数，则称ad是、b的公倍数。ba与的公倍数中最小的正数称为ba与的最小公倍数，记为],[ba。最大公约数和最小公倍数的概念可以推广到有限多个整数的情形，并用),,,(21naaa表示naaa,,,21的最大公约数，],,,[21naaa表示naaa,,,21的最小公倍数。若1),,,(21naaa，则称naaaa,,,,321互质，若naaa,,,21中任何两个都互质，则称它们是两两互质的。注意，n个整数互质与n个整数两两互质是不同的概念，前者成立时后者不一定成立（例如，3，15，8互质，但不两两互质）；显然后者成立时，前者必成立。因为任何正数都不是0的倍数，所以在讨论最小公倍数时，一般都假定这些整数不为0。同时，由于|||,|,baba与有相同的公约数，且|)||,(|),(baba（有限多个亦成立），因此，我们总限于在自然数集合内来讨论数的最大公约数和最小公倍数。显然，若ba,的标准分解式为iniiniippbpaii(,11为质数，iia,为非负整数），则niiiipba1),min(),(①4nimaniiipba1),(],[②例如3960=23·32·5·11，756=22·33·7，则（3960，756）=22·32=36，[3960，756]=23·33·5·7·11=83160。求最大公约数也可以用辗转相除法，其理论依据是：定理二：设a、b、c是三个不全为0的整数，且有整数t使得cbta，则a、b与b、c有相同的公约数，因而),(),(cbba，即).,(),(btabba因为，若ad是、b的任一公约数，则由bdcdcbtabdad是即知和,||,|、c的公约数；反之，若d是b、c的任一公约数，d也是a、b的公约数。辗转相除法：设a、baNb且,，由带余除法有.0,,0,,0,,0,111111212221111nnnnnnnnnnnrrqrrrrrqrrrrrqrbbrrbqa③因为每进行一次带余除法，余数至少减1，即11nnrrrb，而b为有限数，因此，必有一个最多不超过b的正整数n存在，使得0nr，而01nr，故由定理二得：).,(),,(),(),(11211babrrrrrrrrnnnnn（）例如，（3960，756）=（756，180）=（180，36）=36。具体算式如下：5由定义和上述求法不难得出最大公约数和最小公倍数的如下性质：（1）),(),(,bambmamNm则。（2）设bac,为的公约数，则.),(),(cbacbca特别地，若1),(),,(cbcabac则。（3）设naaa,,,21是任意n个正整数，如果nnncaccaccaa),(,,),(,),(1332221，则nncaaa),,,(21。因21121111|,|,|,|,|,|nnnnnnnnnnnnccacccacccac故而，如此类推得出nc能整除nnncaaa于是,,,,11是它们的一个公约数。又设naaac,,,21为的任一公约数，则21|,|acac，因而2|cc，同理可推出3|cc，如此类推最后可得ncc|。于是nccc||，故nc是最大公约数。（4）若cba),(，则一定有整数yx和，使得cbyax。特别地，1),(ba存在1,byaxyx使得。这可由辗转相除法的③式逆推而得byaxrcn。（5）若),(),(,1),(bcbacba则。（6）Nba,①)(],[],[Nkbakbkak；②bam,为的任一公倍数，则mba|],[；③abbaba],)[,(，特别地，若abbaba],[,1),(则。①可由③直接得到，②可由最小公倍数定义得，③根据①、②式知，6],)[,(babaniniiiiiabppii11),min(。（7）设naaa,,,21是任意n个正整数。若],[,,],[,],[1332221nnammammaamn，则nnmaaa],,,[21。这是一个求多个整数的最小公倍数的方法。它可用证明③类似的方法来证明。Ⅲ.方幂问题一个正整数n能否表成m个整数的k次方和的问题称为方幂和问题。特别地，当1m时称为k次方问题，当2k时，称为平方和问题。能表为某整数的平方的数称为完全平方数。简称平方数，关于平方数，明显有如下一些简单的性质和结论：（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，4，7。（6）平方数的约数的个数为奇数。（7）任何四个连续整数的乘积加1，必定是一个平方数。进一步研究可得到有关平方和的几个结论:定理三：奇素数p能表示成两个正整数的平方和的充要条件是.14mp定理四：设正整数pmn2，其中p不再含平方因数，n能表示成两个整数的平方的充要条件是p没有形如34q的质因数。定理五：每个正整数都能表示成四个整数的平方和。这几个定理的证明略。这里重点是介绍有关k方幂的解法技巧。k方幂中许多问题实质上是不定方程的整数解问题，比如著名的勾股数问题。7赛题精讲例1：证明：对于任何自然数n和k，数1042),(3kknnknf都不能分解成若干个连续的正整数之积。（1981年全国高中联赛试题）【证明】由性质9知，只需证明数),(knf不能被一个很小的自然数n整除。因,1)1)(1()3(31033),(333kkkkkkkkknnnnnnnnnknf),1)(1(|3),3(3|33kkkkknnnnn31，故3),(knf，因而),(knf不能分解成三个或三个以上的连续自然数的积。再证),(knf不能分解成两个连续正整数的积。由上知，)(13),(Nqqknf，因而只需证方程：)1(13xxq无正整数解。而这一点可分别具体验算234,134,3rx时，)1(xx均不是13q形的数来说明。故),(knf对任何正整数n、k都不能分解成若干个连续正整数之积。例2：设p和q均为自然数,使得.131911318131211qp证明：p可被1979整除。(第21届IMO试题)【证明】)131814121(2)1319131211(qp=)6591211()1319131211(=)99019891()131816611()131916601(=1979×)99098911318661113196601(8两端同乘以1319！得1319！*).(1979Nmmqp此式说明1979|1319！×.p由于1979为质数，且19791319！，故1979|p。【评述】把1979换成形如23k的质数，1319换成*)(12Nkk，命题仍成立。牛顿二项式定理和nbabababannnn(|)(,|)(为偶数),nbabann(|)(为奇数)在整除问题中经常用到。例3：对于整数n与k，定义,),(112nrkrknF求证：)1,(nF可整除).,(knF（1996加拿大数学竞赛试题）【证明】当mn2时，,)12()1,2(21mrmmrmFmmrkmrkrrkmF2112112),2(],)12([)12(12112112112kmrkmrkmrkrmrrmr由于[…]能被12)12(mrmr整除，所以),2(kmF能被12m整除，另一方面，),2(kmF,)2(])2([1212121112kkkmrkmmrmr上式中[…]能被mrmr2)2(整除，所以),2(kmF也能被m整除。因m与2m+1互质，所以),2(kmF能被m（2m+1）（即)1,(mF）整除。类似可证当12mn时，F（2m+1，k）能被F（2m+1,1）整除。故),(knF能被)1,(nF整除。9例4：求一对整数ba,，满足：(1))(baab不能被7整除；（2）777)(baba能被77整除。(第25届IMO试题)【解】777)(baba=)](5)(3)[(7223355bababaabbaab=.))((7222abbabaab根据题设要求(1)(2)知，|,)(|72226abba即.|7223abba