离散数学课件 第八章 数论

第八章数论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⌉是整数，且满足a≤⌈a⌉＜a+1

取整函数定义8.5设c是任意整数/实数，⌊a

⌋表示不大于a的最大整数，称为a的下取整函数，即⌊a

⌋是整数，且满足a-1<⌊a

⌋≤a例如⌊2.3

⌋=2，⌊-2.3

⌋=-3，⌊2

⌋=2，⌊-2

⌋=-2

素数算数基本定理8.2素数第8章数论

素数定义8.6一个大于1的整数，若它的正约数仅有1和它本身，则称其为素数（Prime）或质数；否则称为合数（Compositenumber）。如7、11是素数，而8、15是合数。1既不是素数，也不是合数。2是唯一的偶素数。定理8.8若a是大于1的正整数，p是素数且p|a，则a=p。定理8.9设a,b是正整数，p是素数且p|ab，则必有p|a或p|b。一般地，设p是素数，且p|(a₁a₂⋯aₖ)，则必存在1≤i≤k，使p|aᵢ。

定理8.10设a是任意大于1的整数，则a除1外的最小正因数q一定是素数，并且，当a是合数时，q≤√a。证明假定q不是素数，由定义8.6，q有除1外的最小正约数q₁，即1<q₁<q，有q₁|q，但q|a，所以q₁|a，这与q是a的正因数矛盾，故q是素数。当a是合数时，则存在q，使得a=a₁q，且a₁>1。由于q是a的不等于1的最小正因数，所以q≤a₁，q²≤qq₁，即q≤√a。推论若a是合数，则a必有一个小于等于√a的素因子。素数

素数例8.7验证157是素数。解：因为√157小于13，而13以内的素因子有2,3,5,7,11，而这些数都不能整除157，所以157是素数。一般地，对任意给定的一个正整数N，我们可求出一切不超过N的素数，称为爱氏筛法：（1）把不超过N的一切整数按从小到大的顺序列成数表。（2）在表中先划去1，然后顺序地划去一切不超过√N的素数的所有倍数，这时，剩下的数即为所求素数。

素数例8.8作60以内的素数表。解：先按从小到大的顺序写出1到60的所有整数。因为√60<8，故只需划去2,3,5,7的所有倍数和1即可，所剩下的数即是60以内的所有素数。所以小于60的所有素数有2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59。

素数定理8.11素数有无穷多个。证明：设p是任一素数，作整数a=p!+1。若a为素数，由于a>p，于是存在大于p的素数a。若a为合数，设q是a的最小真约数，则q是素数，但q不能整除p!，故q>p，可见仍有大于p的素数存在，因而素数有无穷多个。

算数基本原理定理8.12任意大于1的正整数，除因数的顺序外，可唯一地分解为素因数的乘积，即a=p₁p₂⋯pᵣ，pᵢ是素数，i=1,⋯,r如果a=q₁q₂⋯qₛ，qⱼ是素数，j=1,⋯,s则有{p₁,p₂,⋯,pᵣ}={q₁,q₂,⋯,qₛ}。

算数基本原理证明如果a是素数，则令a=p₁，结论成立。如果a是合数，则令p₁是a的最小素因数，于是有a=p₁a₁，1<a₁<a。如果a₁是素数，则令a₁=p₂，结论成立。如果a₁是合数，则令p₂是a₁的最小素因数，于是有a₁=p₂a₂，从而有a=p₁p₂a₂，如此进行下去，由于a>a₁>a₂>⋯，所以，经过有限次后，必有a=p₁p₂⋯pᵣ，pᵢ是素数，i=1,2,…,r。

算数基本原理下面证明其唯一性。当r=1时，如a=q₁q₂⋯qₛ，因p₁是素数，所以有s=1，所以{p₁}={q₁}。假设r-1时成立。因为a=p₁p₂⋯pᵣ=q₁q₂⋯qₛ，所以p₁|q₁q₂⋯qₛ，由定理8.9知，p₁整除a=q₁q₂⋯qₛ中的某一数，不妨设p₁|q₁，从而有p₂⋯pᵣ=q₂⋯qₛ

算数基本原理由归纳假设有{p₂,⋯,pᵣ}={q₂,⋯,qₛ}，又因p₁=q₁，所以有{p₁,p₂,⋯,pᵣ}={q₁,q₂,⋯,qₛ}证毕。

算数基本原理此定理说明素数是构成整数的“基本元素”。如果将a的素因数中相同的素数归在一起，则有其中，p₁,⋯,pᵣ是互异素数。式（7.2）称为a的标准分解式，也称为整数a的素因子分解。

例如：26=2×131320=2²×3×115775=3×5²×7×1199099=3²×7×11²×13利用整数的素因子分解可求最大公约数和最小公倍数。算数基本原理

算数基本原理

定理8.13

设整数a,b的素因子分解式分别为其中，p₁,⋯,pₖ是互不相同的素数，a₁,⋯,aₖ,b₁,⋯,bₖ是非负数。则

算数基本原理

例8.9求132和240的最大公约数与最小公倍数。解因子分解132和240为132=2²×3×11240=2⁴×3×5所以有gcd(132,240)=2²×3×5⁰×11⁰=12lcm(132,240)=2⁴×3×5×11=2640

同余的概念同余类一次同余式8.3同余第8章数论

同余的概念定义8.7设m是正整数，a与b是整数，若m|(a-b)，则称a模m同余于b，或a与b模m同余（Congruence），记作a≡b(modm)。否则，说a与b模m不同余，记作a≢b(modm)。例如，17=9(mod8)，15=0(mod5)，29≢16(mod9)

同余的概念定义8.8设m是正整数，a与b是整数，若m除a、b的余数相同，则称a与b模m同余。易知a≡b(modm)⇔a=b+mt，t∈Z从定义可以看出，同余与整除间的关系，即整除与同余可以相互转化，因此关于同余的有关问题，我们可以用整除的语言来叙述。

同余的概念定理8.14设a=r₁+mq₁，0≤r₁<mb=r₂+mq₂，0≤r₂<m则a≡b(modm)当且仅当r₁=r₂。

同余的概念证明由已知a-b=(r₁-r₂)+m(q₁-q₂)必要性：设a≡b(modm)，则有m|(a-b)，但是由已知有|r₁-r₂|<m，所以|r₁-r₂|=0，即r₁=r₂。充分性：如果r₁=r₂，则a-b=m(q₁-q₂)，即m|(a-b)，所以a≡b(modm)。即a与b模m同余，当且仅当m除a、b所得的余数相同。作为两个整数之间的一种二元关系，同余具有很多性质。

同余的概念性质8.1同余关系是等价关系自反性：对任意整数a，有a≡a(modm)对称性：若a≡b(modm)，则b≡a(modm)传递性：若a≡b(modm)，b≡c(modm)，则a≡c(modm)同余模的算术运算具有以下性质：如果a≡b(modm)，c≡d(modm)，则(a±c)≡(b±d)(modm)，ac≡bd(modm)

同余的概念性质8.2（1）如果a+b≡c(modm)，则a-c≡b(modm)（2）如果an≡bn(modm)，且gcd(m,n)=1，则a≡b(modm)（3）如果a≡b(modm)，是a,b,m的正公因子，则

同余的概念证明由已知，令a=a₁n,b=b₁n,m=m₁n，因a≡b(modm)，则有a₁n=b₁n+m₁nt,t∈Z从而有a₁=b₁+m₁t,t∈Z（4）如果a≡b(modm)，则gcd(a,m)=gcd(b,m)

同余类定义8.9设m是给定的正整数，则全体正整数可以分为m个类（子集），记为：j₀,j₁,⋯,j{m-1}，其中，ji={mq+i,q∈Z},i=0,1,⋯,m-1。则称j₀,j₁,⋯,j{m-1}为模m的同余类。定理8.15设m是给定的正整数，j₀,j₁,⋯,j{m-1}是模m的同余类，则有（1）每个整数恰包含在一个ji里，0≤i≤m-1。（2）两个整数a,b属于同一类的充要条件是a≡b(modm)。

证明（1）设a是任意整数，则由带余除法得a=r+mt，0≤r≤m−1。所以a在jr

中。

又因为r是由a唯一确定的，所以a只能在jr

中。（2）必要性：设a,b是两个整数，并且都在jr

内，则

a=r+mq₁，b=r+mq₂所以a≡b(modm)充分性：由同余定义可知a,b在某一个同余类jr

内，0≤r≤m−1。同余类

同余类由性质8.1知，同余关系是等价关系，整数a在模m同余关系下的等价类记作[a]m，称做等价类，可简记为am。把整数集合Z在模m同余关系下的商集记作Zm。可以在Zm上定义加法和乘法：对任意的整数a,b，有[a]+[b]=[a+b]，[a]·[b]=[ab]

同余类加法和乘法表见表8.1和表8.2。表8.2乘法表*5[0][1][2][3][4][0][0][0][0][0][0][1][0][1][2][3][4][2][0][2][4][1][3][3][0][3][1][4][2][4][0][4][3][2][1]表8.1加法表+5[0][1][2][3][4][0][0][1][2][3][4][1][1][2][3][4][0][2][2][3][4][0][1][3][3][4][0][1][2][4][4][0][1][2][3]

一次同余式定义8.10设m>0，方程ax≡b(modm)（7.3）称为一次同余式，使上式成立的整数称为同余式的解。由同余性质，如果整数r是其解，则与r同余的所有整数都是其解。

一次同余式定理8.16设a,m∈Z，如果gcd(a,m)=1，则方程（7.3）在同余意义下恰有一个解。证明：由gcd(a,m)=1可知，存在s,t∈Z，使得as+mt=1，于是有asb+mtb=b，从而asb≡b(modm)令x=sb，则有ax≡b(modm)。设∃y∈Z，使得ay≡b(modm)，则由同余性质知ax≡ay(modm)，又gcd(a,m)=1，所以有x≡y(modm)形如

一次同余式定理8.17（孙子定理）如果m₁,m₂,⋯,mₖ两两互素，则同余方程对于模m=m₁m₂⋯mₖ有唯一解。

一次同余式例8.11

（孙子算经）今有物知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？解

由题意得同余方程

一次同余式例8.12

解同余方程组解由2x≡1(mod5)解得x≡3(mod5)，由3x≡4(mod7)解得x≡6(mod7)，于是原同余方程组化为可由孙子定理中的方法解得，也可用同余的定义解。令x=3+5y，有3+