离散数学课件 8.1整数

第八章数论8.1整除8.2素数8.3同余8.4应用整除最大公约数最小公倍数取整函数

8.1整除第8章数论

整除定义8.1

对于整数a和非零整数b，若存在正数c，使得a=bc，则称b能整除a或a能被b整除，b是a的约数或因数，a是b的倍数，记作b|a；若这样的c不存在，则称b不能整除a或a不能被b整除，记作b∤a。例如：8能被±1，±2，±4，±8整除，±1，±2，±4，±8都是8的因数。一般地，称1和正整数本身为它的平凡因数，其他因数称为真因数。

整除例8.1：设a、b均为正整数，不超过a的正整数中有多少个能被b整除。解：能被b整除的数都是bk的形式，其中，k是正整数。所以，不超过a且能被b整除的整数个数是使0<bk≤a或0<k≤a/b成立的整数k的个数。即有⌊a/b

⌋个正整数，既不超过a，又能被整除。如：3和12这两个整数，不超过12的正整数中有3，6，9，12四个整数能被3整除。

整除定理8.1对称性：b|a⇔-b|a⇔b|-a⇔|a|||b|证明

b|a⇔∃c∈Z∧a=bc⇔-a=b(-c)⇔a=(-b)(-c)⇔-a=(-b)c

整除定理8.2传递性：如果b|a，a|c，且a≠0，b≠0，则b|c。证明定理8.3如果b|a，则a=0或|b|≤|a|；如果a|b，b|a，则a=±b；如果a|b，则对任意正数c，有a|bc。

整除定理8.4a|b，a|c，则对任意整数m,n，有a|(nb+mc)证明由定理8.3知，存在整数m,n，使得a|mb,a|nc，即存在整数s,r，使得mb=as,nc=ar，进而有mb+nc=a(s+r)，所以有a|(mb+nc)。

下面讨论整除或不整除一般情形。对任意正数，或者整除，或者不能整除，一般地。定理8.5（带余除法）：对任意两个整数a,b，其中b≠0，则存在唯一一对整数s,r，使得a=bs+r，0≤r<|b|其中，b称为除数、a称为被除数、s称为商、r称为余数。整除

例8.2360被33除时的商和余数是多少？因为，所以360被33除时的商是10，余数是30。例8.3-11被3除时的商和余数是多少？因为，所以-11被3除时的商是-4，余数是1。对任意正数，能整除的充分必要条件是被除时的余数为0。应用带余除法可求两个数的最大公约数。

整除

最大公约数定义8.2设d是一个非零整数，若d|a且d|b，则称d是a和b的公约数。若d是a和b的公约数中的最大者，则称d是a和b的最大公约数（GreatestCommonDivisor），记作d=gcd(a,b)不全为0的两个整数的最大公约数的确存在，因为这两个整数的公约数集合是有限的，求两个整数的最大公约数的一个方法是求出两个整数的所有正的公约数，然后取其中最大的。

例8.4求12和36的最大公约数解

因为12和36的正公约数是1，2，3，4，6和12，所以gcd(12,36)=12。约定gcd(0,0)=0，若gcd(a,b)=1，则称a,b互素（Coprime）。易知，若a,b不全为零，则gcd(a,b)>0。最大公约数

最大公约数定理8.6设a,b,c是任意三个不全为零的数，且a=bq+c，其中q∈Z，则（1）a,b与a,c有相同的公约数；（2）gcd(a,b)=gcd(a,c)。

最大公约数证明

（1）设m是a与b的任一公约数，即m|a,m|b，由定理8.4知，m是a-bq的约数，因而m是b与c的公约数。同理可证b,c的任一公约数也是a,b的公约数，所以a,b与a,c有相同的公约数。（2）自然就成立了。下面给出求两个整数的最大公约数的更有效方法，即利用两个整数的素因子分解。假定两个不全为零的整数a和b的素因子分解为其中每个指数都是非负整数。则gcd(a,b)可由下面公式给出：

最大公约数例8.5

求500和120的最大公约数下面介绍求任意两个数的最大公约数的方法-------辗转相除法。

例8.6用辗转相除法求452和610的最大公约数。解

辗转使用除法得

121=100·1+21100=21·4+1621=16·1+516=5·3+15=1·5最大公约数

所以gcd(100,121)=1，即100和121是互素的。从后向前逐个回代有

1=16-5·3=16-(21-16)·3=16·4-21·3=(100-21·4)·4-21·3=100·4-(121-100)·19=100·23-121·19最大公约数

定义8.3设a,b是两个非零整数，若a|m,b|m，则称m是a与b的公倍数。在a与b有无穷多个公倍数中，其中最小的正整数称为a,b的最小公倍数（LeastCommonMultiple），记作lcm(a,b)。如：14与21的最小公倍数是42。最小公倍数

最小公倍数证明记lcm(a,b)=M，设m=Mq+r，0≤r≤M。因为a|m，a|M，r=m-Mq，所以有a|r。同理有b|r。由定义知，r=0，即M|m。素因子分解也可以用来求最小公倍数。假设不全为零的整数a和b的素因子分解如前面给出。则a和b的最小公倍数由下式给出：

最小公倍数例8.6求432和95256的最小公倍数。解因为432=2⁴·3³，95256=2³·3⁵·7²，则有lcm(432,95256)=2^max(4,3)·3^max(3,5)·7^max(0,2)=2³·3⁵·7²=4·243·49=142884对两个正整数，最大公约数和最小公倍数有以下关系：ab=gcd(a,b)·lcm(a,b)

取整函数取整函数是数论经常用到的两个重要函数。定义8.4设a是任意实数，⌈a⌉表示不小于a的最小整数，称为a的上取整函数，即⌈a⌉是整数，且满足