数学奥赛辅导 第二讲
整除
知识、方法、技能
整除是整数的一个重要内容，这里仅介绍其中的几个方面：整数的整除性、最大公约数、最小公倍数、方幂问题.
Ⅰ. 整数的整除性
初等数论的基本研究对象是自然数集合及整数集合. 我们知道，整数集合中可以作加、减、乘法运算，并且这些运算满足一些规律（即加法和乘法的结合律和交换律，加法与乘法的分配律），但一般不能做除法，即，如a,b是整除，b?0，则初等数论中第一个基本概念：整数的整除性.
定义一：（带余除法）对于任一整数a和任一整数b，必有惟一的一对整数q，r使得
a不一定是整数. 由此引出ba?bq?r，0?r?b，并且整数q和r由上述条件惟一确定，则q称为b除a的不完全商，
r称为b除a的余数.
若r?0，则称b整除a，或a被b整除，或称a是b的倍数，或称b是a的约数（又叫因子），记为b|a.否则，b| a.
任何a的非?a,?1的约数，叫做a的真约数. 0是任何整数的倍数，1是任何整数的约数.
任一非零的整数是其本身的约数，也是其本身的倍数. 由整除的定义，不难得出整除的如下性质： （1）若a|b,b|c,则a|c.
（2）若a|bi,则a|?cb,其中ciii?1ni?Z,i?1,2,?,n.
（3）若a|c，则ab|cb.反之，亦成立.
（4）若a|b,则|a|?|b|.因此，若a|b,又b|a,则a??b. （5）a、b互质，若a|c,b|c,则ab|c.
1
（6）p为质数，若p|a1?a2???an,则p必能整除a1,a2,?,an中的某一个. 特别地，若p为质数，p|an,则p|a.
（7）如在等式
?a??bii?1k?1nmk中除开某一项外，其余各项都是c的倍数，则这一项也是c的倍数.
（8）n个连续整数中有且只有一个是n的倍数. （9）任何n个连续整数之积一定是n的倍数.
本讲开始在整除的定义同时给出了约数的概念，又由上一讲的算术基本定理，我们就可以讨论整数的约数的个数了.
定理一：设大于1的整数a的标准分解式为a?p11?p2?pnn(p1?p2???pn为质数，?i均为非负整数），则a的约数的个数为
???d(a)??（?i?1).
i?1n所有的约数和为：
?(a)??i?1npi?i?1?1.
pi?1事实上，由算术基本定理的推论知d(a)??(?i?1ni?1)，而各约数的和就是
?(1?pi?1ni???paii)展开后的各项之和，所以
nn?ip1?1 ?(a)??(1?pi???pi)??i?1i?1pi?1?i例如，25200=24·32·52·7，所以
d(25200)?(4?1)(2?1)(2?1)(1?1)?90，
25?133?153?172?1?(25200)?????99944.
2?13?15?17?1Ⅱ. 最大公约数和最小公倍数
2
定义二：设a、b是两个不全为0的整数.若整数c满足：c|a,c|b，则称c为a,b的公约数，a与b的所有公约数中的最大者称为a与b的最大公约数，记为(a,b).如果(a,b)=1，则称a与b互质或互素.
定义三：如果d是a、b的倍数，则称d是a、b的公倍数. a与b的公倍数中最小的正数称为a与b的最小公倍数，记为[a,b].
最大公约数和最小公倍数的概念可以推广到有限多个整数的情形，并用(a1,a2,?,an)表示a1,a2,?,an的最大公约数，[a1,a2,?,an]表示a1,a2,?,an的最小公倍数.
若(a1,a2,?,an)?1，则称a1,a2,a3,?,an互质，若a1,a2,?,an中任何两个都互质，则称它们是两两互质的.注意，n个整数互质与n个整数两两互质是不同的概念，前者成立时后者不一定成立（例如，3，15，8互质，但不两两互质）；显然后者成立时，前者必成立.
因为任何正数都不是0的倍数，所以在讨论最小公倍数时，一般都假定这些整数不为0.同时，由于a,b与|a|,|b|有相同的公约数，且(a,b)?(|a|,|b|)（有限多个亦成立），因此，我们总限于在自然数集合内来讨论数的最大公约数和最小公倍数.
显然，若a,b的标准分解式为a?则
?pi?1ni?i，,b??pi?i(pi为质数，ai,?i为非负整数）
i?1n(a,b)??pimin(?i,?i) ①
i?1nn[a,b]??piman(?i,?i) ②
i?1例如 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使得a?bt?c，则a、b与b、c有相同的公约数，因而(a,b)?(b,c)，即(a,b)?(b,a?bt).
3
因为，若d是a、b的任一公约数，则由d|a,d|b和a?bt?c知d|c,即d是b、c的公约数；反之，若d是b、c的任一公约数，d也是a、b的公约数.
辗转相除法：设a、b?N?,且a?b， 由带余除法有
??b?r1q2?r2,0?r2?r1,????? ③ rn?2?rn?1qn?rn,0?rn?rn?1,??rn?1?rnqn?1?rn?1,rn?1?0.??因为每进行一次带余除法，余数至少减1，即b?r1???rn?rn?1，而b为有限数，因此，必有一个最多不超过b的正整数n存在，使得rn?0，而rn?1?0，故由定理二得：
a?bq1?r1,0?r1?b,rn?(rn?1,rn)?(rn,rn?1)???(r2,r1）?（r1,b)?(a,b).
例如，（3960，756）=（756，180）=（180，36）=36. 具体算式如下：
5（q1） 3960（a） 756（b） 4（q2） 3780 720
180（r1） 36（r2） 5（q3） 180
0（r3）
由定义和上述求法不难得出最大公约数和最小公倍数的如下性质： （1）m?N,则(am,bm)?m(a,b). （2）设c为a,b的公约数，则(,)?abcc(a,b)ab.特别地，若c?(a,b),则(,)?1. ccc（3）设a1,a2,?,an是任意n个正整数，如果(a1,a2)?c2,(c2,a3)?c3,?,(cn?1,an)?cn， 则(a1,a2,?,an)?cn.
因cn|an,cn|cn?1,而cn?1|an?1,cn?1|cn?2,故cn?1|an?1,cn|cn?2，如此类推得出cn能整
4
除an,an?1,?,a1,于是cn是它们的一个公约数.又设c为a1,a2,?,an的任一公约数，则
c|a1,c|a2，因而c|c2，同理可推出c|c3，如此类推最后可得c|cn. 于是c?|c|?cn，故
cn是最大公约数.
（4）若(a,b)?c，则一定有整数x和y，使得ax?by?c. 特别地，(a,b)?1?存在x,y使得ax?by?1. 这可由辗转相除法的③式逆推而得c?rn?ax?by. （5）若(a,b)?1,则(ac,b)?(c,b). （6）a,b?N? ①[ak,bk]?k[a,b](k?N?)；
②m为a,b的任一公倍数，则[a,b]|m；
③(a,b)[a,b]?ab，特别地，若(a,b)?1,则[a,b]?ab.
①可由③直接得到，②可由最小公倍数定义得，③根据①、②式知，
(a,b)[a,b]?
?pi?1nimin(?i,?i)??pi?i??i?ab.
i?1n（7）设a1,a2,?,an是任意n个正整数.若[a1,a2]?m2,[m2,a3]?m3,?,[mn?1,an]?mn，则[a1,a2,?,an]?mn.
这是一个求多个整数的最小公倍数的方法.它可用证明③类似的方法来证明.
Ⅲ.方幂问题 一个正整数n能否表成m个整数的k次方和的问题称为方幂和问题.特别地，当m?1时称为k次方问题，当k?2时，称为平方和问题. 能表为某整数的平方的数称为完全平方数.简称平方数，关于平方数，明显有如下一些简单的性质和结论： （1）平方数的个位数字只可能是0，1，4，5，6，9. （2）偶数的平方数是4的倍数，奇数的平方数被8除余1，即任何平方数被4除的余数
5