数学奥赛辅导第二讲整除知识、方法、技能整除是整数的一个重要内容，这里仅介绍其中的几个方面：整数的整除性、最大公约数、最小公倍数、方幂问题.Ⅰ.整数的整除性初等数论的基本研究对象是自然数集合及整数集合.我们知道，整数集合中可以作加、减、乘法运算，并且这些运算满足一些规律（即加法和乘法的结合律和交换律，加法与乘法的分配律），但一般不能做除法，即，如ba,是整除，0b，则ba不一定是整数.由此引出初等数论中第一个基本概念：整数的整除性.定义一：（带余除法）对于任一整数a和任一整数b，必有惟一的一对整数q，r使得rbqa，br0，并且整数q和r由上述条件惟一确定，则q称为b除a的不完全商，r称为b除a的余数.若0r，则称b整除a，或a被b整除，或称ba是的倍数，或称ab是的约数（又叫因子），记为ab|.否则，b|a.任何a的非1,a的约数，叫做a的真约数.0是任何整数的倍数，1是任何整数的约数.任一非零的整数是其本身的约数，也是其本身的倍数.由整除的定义，不难得出整除的如下性质：（1）若.|,|,|cacbba则（2）若.,,2,1,,|,|1niZcbcabainiiii其中则（3）若ca|，则.|cbab反之，亦成立.（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的标准分解式为nnppppppan211(21为质数，i均为非负整数），则a的约数的个数为niiad1)1)(（.所有的约数和为：niiippai1111)(.事实上，由算术基本定理的推论知niiad1)1()(，而各约数的和就是niiiipap1)1(展开后的各项之和，所以例如，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),,,(21naaa，则称naaaa,,,,321互质，若naaa,,,21中任何两个都互质，则称它们是两两互质的.注意，n个整数互质与n个整数两两互质是不同的概念，前者成立时后者不一定成立（例如，3，15，8互质，但不两两互质）；显然后者成立时，前者必成立.因为任何正数都不是0的倍数，所以在讨论最小公倍数时，一般都假定这些整数不为0.同时，由于|||,|,baba与有相同的公约数，且|)||,(|),(baba（有限多个亦成立），因此，我们总限于在自然数集合内来讨论数的最大公约数和最小公倍数.显然，若ba,的标准分解式为iniiniippbpaii(,11为质数，iia,为非负整数），则niiiipba1),min(),(①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的公约数；反之，若bd是、c的任一公约数，ad也是、b的公约数.辗转相除法：设a、baNb且,，由带余除法有.0,,0,,0,,0,111111212221111nnnnnnnnnnnrrqrrrrrqrrrrrqrbbrrbqa③因为每进行一次带余除法，余数至少减1，即11nnrrrb，而b为有限数，因此，必有一个最多不超过b的正整数n存在，使得0nr，而01nr，故由定理二得：例如，（3960，756）=（756，180）=（180，36）=36.具体算式如下：5（q1）3960（...
