- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
例3 gcd(12,18)=6, lcm(12,18)=36. 对任意的正整数a, gcd(0,a)=a, gcd(1,a)=1, lcm(1,a)=a.
19.2 最大公约数和最小公倍数
定理4： (1) 若a | m, b | m, 则 lcm(a,b)| m. (2) 若d |a, d |b, 则d | gcd(a,b). 证 (1) 记M=lcm(a,b), 设m=qM+r, 0≤r<M.
欧几里得算法-辗转相除法
除法算法: a=qb+r, 0≤r <|b|, 记余数r=a mod b 例如, 20 mod 6=2, 13 mod 4=3, 10 mod 2=0
定理5： 设a=qb+r, 其中a, b, q, r 都是整数, 则 gcd(a,b) = gcd(b,r).
证明：只需证a与b和b与r有相同的公因子. 设d是a与b的公因
-3d -2d -d 0 d 2d 3d
性质：令a，b，c为整数，有如下结论： 1）若a |b且a |c, 则 x, y, 有a | xb+yc. 2）若a |b且b |c, 则a |c. 3）若 a |b，那么对于所有整数 m≠0都有 a | mb.
19.1 素数
2. 素数 定义2：大于 1 且只能被 1 和自身整除的正整数称为素数
19.2 最大公约数和最小公倍数
利用整数的素因子分解, 求最大公约数和最小公倍数. 设
ap1r1p2r2pkrk, bp1s1p2s2 pk sk, 其中p1,p2,…,pk是不同的素数, r1,r2,…,rk,s1,s2,…,sk是非负
整数. 则
gcd(a,b)=
p p p , mr1 i,n s1)(mri2,n s2)(
欧几里得算法-辗转相除法
C语言代码：
int gcd(int x，int y) { int g;
if (x < 0) x = -x; if (y < 0) y = -y; if (x+y = = 0)
printf("Error!\n"); g = y； while(x>0){
g = x； x = y%x; Hale Waihona Puke = g; } return g; }
19.1 素数
定理 2：如果n是合数，那么n必有一个小于或等于 n 的素
因子。
证：如果n是合数，它有一个因子a，使得1＜ a ＜ n， 于是 nab，这样 a n或b n，这个因子或是素
数，或是有素因子。无论哪种情况，n都有小于或等于
n 的素因子
例2：证明101是素数。 证明思路：101不含有不超过 101 的素因子。
由a | m, a | M, 及r=mqM, 可推出a | r. 同理, 有b | r. 即, r是a
和b的公倍数. 根据最小公倍数的定义, 必有r=0. 得证M | m. (2) 记D=gcd(a,b), 令m=lcm(d,D). 若m=D, 自然有d |D, 结 论成立. 否则m>D, 注意到d |a, D|a, 由(1), 得m |a. 同理, m |b. 即, m是a和b的公因子, 与D是a和b的最大公约数矛盾.
子, 即d |a且d |b. 注意到, r=aqb, 由性质可得d |r. 从而,
d |b且d |r, 即d也是b与r的公因子. 反之一样, 设d是b与r的公 因子, 即d |b且d |r. 注意到, a=qb+r, 故有d |a. 从而, d |a且d |b, 即d也是a与b的公因子.
欧几里得算法-辗转相除法
19.2 最大公约数和最小公倍数
d是a与b的公因子(公约数): d |a且d |b m是a与b的公倍数: a | m且b | m 定义3：设a和b是两个不全为0的整数, 称a与b的公因子中 最大的为a与b的最大公因子, 或最大公约数, 记作gcd(a,b). 设a和b是两个非零整数, 称a与b最小的正公倍数为a与b的 最小公倍数, 记作lcm(a,b).
19.1 素数
定理 3：有无穷多个素数。
梅森数(Marin Mersenne): 2p1, 其中p为素数。 当n是合数时, 2n1一定是合数,
2ab1=(2a1)(2a(b1)+2a(b2)+…+2a+1). 梅森数可能是素数, 也可能是合数: 221=3, 231=7, 251=31, 271=127都是素数, 而2111=2047=23×89是合数. 到2019年找到的最大梅森素数是2134669171, 有4百万位.
（质数）。大于 1 又不是素数的正整数称为合数。
算术基本定理：每个正整数都可以唯一地表示为素数的乘 积，其中素数因子从小到大依次出现，即 ap1r1p2r2..p.krk
例1：100, 641, 999的素因子分解为： 100=2×2×5×5=22×52 641=641 999=3×3×3×37=33×37
初等数论
主要内容
素数 最大公约数与最小公倍数 同余 在计算机科学中的应用
19.1 素数
1. 整除 定义1：设a, b是两个整数，且a≠0， 若存在整数c 使 b=ac，则称b 被a 整除，或 a 整除b，记作 a|b. 此时, 又称 b 是a 的倍数，a是b 的因子. 把 a不整除 b 记作 a b.
1
2
mrik,n sk)( k
p p p lcm(a,b)=
mr a 1,s1 x)(mr a 2,sx 2)(
1
2
mr a k,sx k)( k
例4 求150和220的最大公约数和最小公倍数. 解 150=2×3×52, 168=23×3×7.
gcd(150,168)=21×31×50×70=6, lcm(150,168)=23×31×52×71=4200.
最大公因数的求法：辗转相除法
例5：求gcd(15,36)
gcd(54,30)
36=15 2+6
54=30+24
15=6 2+3
30=24+6
6=3 2+0
24=4 6+0
因此，gcd(15,36)=3
gcd(54,30)=6
原理： gcd(a,b) = gcd(b,r)
这里，gcd(36,15) = gcd(6,15) = gcd(6,3) = 3
