离散数学课件 初等数论

《离散数学课件 初等数论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、初等数论主要内容素数最大公约数与最小公倍数同余在计算机科学中的应用19.1素数1.整除定义1：设a,b是两个整数，且a≠0，若存在整数c使b=ac，则称b被a整除，或a整除b，记作a

2、b.此时,又称b是a的倍数，a是b的因子.把a不整除b记作ab.性质：令a，b，c为整数，有如下结论：1）若a

3、b且a

4、c,则x,y,有a

5、xb+yc.2）若a

6、b且b

7、c,则a

8、c.3）若a

9、b，那么对于所有整数m≠0都有a

10、mb.19.1素数2.素数定义2：大于1且只能被1和自身整除的正整数称为素数（质数）。大于1又不是素数的正整数称为合数。算术基本定理：每个正整数都可以唯一地表示为素数的乘积，其中素数因子

11、从小到大依次出现，即例1：100,641,999的素因子分解为：100=2×2×5×5=22×52641=641999=3×3×3×37=33×3719.1素数定理2：如果n是合数，那么n必有一个小于或等于的素因子。证：如果n是合数，它有一个因子a，使得1＜a＜n，于是，这样，这个因子或是素数，或是有素因子。无论哪种情况，n都有小于或等于的素因子例2：证明101是素数。证明思路：101不含有不超过的素因子。19.1素数定理3：有无穷多个素数。梅森数(MarinMersenne):2p1,其中p为素数。当n是合数时,2n1一定是合数,2ab1=(2a1)(2a(b1)+2a(b2)+

12、…+2a+1).梅森数可能是素数,也可能是合数:221=3,231=7,251=31,271=127都是素数,而2111=2047=23×89是合数.到2002年找到的最大梅森素数是2134669171,有4百万位.19.2最大公约数和最小公倍数d是a与b的公因子(公约数):d

13、a且d

14、bm是a与b的公倍数:a

15、m且b

16、m定义3：设a和b是两个不全为0的整数,称a与b的公因子中最大的为a与b的最大公因子,或最大公约数,记作gcd(a,b).设a和b是两个非零整数,称a与b最小的正公倍数为a与b的最小公倍数,记作lcm(a,b).例3gcd(12,18)=6,lcm(12,18)=3

17、6.对任意的正整数a,gcd(0,a)=a,gcd(1,a)=1,lcm(1,a)=a.19.2最大公约数和最小公倍数定理4：(1)若a

18、m,b

19、m,则lcm(a,b)

20、m.(2)若d

21、a,d

22、b,则d

23、gcd(a,b).证(1)记M=lcm(a,b),设m=qM+r,0≤r

24、m,a

25、M,及r=mqM,可推出a

26、r.同理,有b

27、r.即,r是a和b的公倍数.根据最小公倍数的定义,必有r=0.得证M

28、m.(2)记D=gcd(a,b),令m=lcm(d,D).若m=D,自然有d

29、D,结论成立.否则m>D,注意到d

30、a,D

31、a,由(1),得m

32、a.同理,m

33、b.即,m是a和b的公因子,与D

34、是a和b的最大公约数矛盾.19.2最大公约数和最小公倍数利用整数的素因子分解,求最大公约数和最小公倍数.设其中p1,p2,…,pk是不同的素数,r1,r2,…,rk,s1,s2,…,sk是非负整数.则gcd(a,b)=lcm(a,b)=例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.欧几里得算法-辗转相除法除法算法:a=qb+r,0≤r<

35、b

36、,记余数r=amodb例如,20mod6=2,13mod4=3,10mod2=0定理5：设a=

37、qb+r,其中a,b,q,r都是整数,则gcd(a,b)=gcd(b,r).证明：只需证a与b和b与r有相同的公因子.设d是a与b的公因子,即d

38、a且d

39、b.注意到,r=aqb,由性质可得d

40、r.从而,d

41、b且d

42、r,即d也是b与r的公因子.反之一样,设d是b与r的公因子,即d

43、b且d

44、r.注意到,a=qb+r,故有d

45、a.从而,d

46、a且d

47、b,即d也是a与b的公因子.欧几里得算法-辗转相除法最大公因数的求法：辗转相除法例5：求gcd(15,36)gcd(54,30)36=152+654=30+2415=62+330=24+66=32+024=46+0因此，gcd(15,36)=3g

48、cd(54,30)=6原理：gcd(a,b)=gcd(b,r)这里，gcd(36,15)=gcd(6,15)=gcd(6,3)=3欧几里得算法-辗转相除法intgcd(intx，inty){intg;if(x<0)x=-x;if(y<0)y=-y;if(x+y==0)printf("Error!");g=y；while(x>0){g=x；x=y%x;y=g;}returng;}试跟踪求gcd(