高中数学奥赛辅导 第二讲 整除

数学奥赛辅导 第二讲

整除

知识、方法、技能

整除是整数的一个重要内容，这里仅介绍其中的几个方面：整数的整除性、最大公约数、最小公倍数、方幂问题.

Ⅰ. 整数的整除性

初等数论的基本研究对象是自然数集合及整数集合. 我们知道，整数集合中可以作加、减、乘法运算，并且这些运算满足一些规律（即加法和乘法的结合律和交换律，加法与乘法的分配律），但一般不能做除法，即，如a,b是整除，b 0，则初等数论中第一个基本概念：整数的整除性.

定义一：（带余除法）对于任一整数a和任一整数b，必有惟一的一对整数q，r使得

a

不一定是整数. 由此引出b

a 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.否则，ba.

任何a的非 a, 1的约数，叫做a的真约数. 0是任何整数的倍数，1是任何整数的约数.

任一非零的整数是其本身的约数，也是其本身的倍数. 由整除的定义，不难得出整除的如下性质： （1）若a|b,b|c,则a|c.

（2）若a|bi,则a|

cb,其中c

iii 1

n

i

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.

（6）p为质数，若p|a1 a2 an,则p必能整除a1,a2, ,an中的某一个. 特别地，若p为质数，p|an,则p|a.

（7）如在等式

a b

ii 1

k 1

nm

k

中除开某一项外，其余各项都是c的倍数，则这一项也是c

的倍数.

（8）n个连续整数中有且只有一个是n的倍数. （9）任何n个连续整数之积一定是n的倍数.

本讲开始在整除的定义同时给出了约数的概念，又由上一讲的算术基本定理，我们就可以讨论整数的约数的个数了.

定理一：设大于1的整数a的标准分解式为a p11 p2 pnn(p1 p2 pn为质数， i均为非负整数），则a的约数的个数为

d(a) （ i 1).

i 1

n

所有的约数和为：

(a)

i 1

n

pi i 1 1

.

pi 1

事实上，由算术基本定理的推论知d(a)

(

i 1

n

i

1)，而各约数的和就是

(1 p

i 1

n

i

paii)展开后的各项之和，所以

n

n

ip1 1

(a) (1 pi pi) p 1i 1i 1i

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

Ⅱ. 最大公约数和最小公倍数

定义二：设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 则

i

，p,b p i i(pi为质数，ai, i为非负整数）

i

i 1

i 1

n

n

(a,b) pimin( i, i) ①

i 1n

n

[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).

因为，若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能整除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]

p

i 1

n

i

min( i, i) pi i i ab.

i 1

n

（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时，称为平方和问题. 能表为某整数的平方的数称为完全平方数.简称平方数，关于平方数，明显有如下一些简