初等数论1 - 整除理论.ppt
《初等数论1 - 整除理论.ppt》由会员分享,可在线阅读,更多相关《初等数论1 - 整除理论.ppt(19页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、整整 除除 理理 论论v1、素数、素数 (1)、素因子、素因子 (2)、素数分布、素数分布 (3)、素数搜寻、素数搜寻 (4)、素性判定、素性判定v2、GCD和和LCM定义定义 若整数若整数a 0,1,并且只有约数,并且只有约数 1和和 a,则称,则称a是是素数素数(或(或质数质数););否则称否则称a为为合数合数。定理定理 任何大于任何大于1的整数的整数a都至少有一个素约数。都至少有一个素约数。推论推论 任何大于任何大于1的合数的合数a必有一个不超过必有一个不超过a1/2的素约数。的素约数。定理定理(算术基本定理算术基本定理)任何大于任何大于1的整数的整数n可以可以唯一唯一地表示成地表示成(
2、标准分解式标准分解式)其中其中p1,p2,pk 是素数,是素数,p1 p2 1)是素数,则是素数,则a=2,并且,并且n是素数。是素数。(3+k)ab-1 必非素数。必非素数。4)、形如、形如2(2n)+1(n=0,1,2,)的数称为的数称为Fermat数数。Fermat曾猜测是素数:曾猜测是素数:F0,F1,F2,F3,F4是素数,是素数,F5=641*6700417是合数。是合数。5)、形如形如4n 3的素数有无限多个。的素数有无限多个。6)、越往后越越往后越稀疏稀疏:在正整数序列中:在正整数序列中,有任意长的区间中不含有素数。有任意长的区间中不含有素数。对于大于等于对于大于等于2的整数的
3、整数n,连续,连续n-1个整数个整数n!2,n!3,n!n都不是素数。都不是素数。素数分布素数分布7)、素数大小粗糙的估计、素数大小粗糙的估计 pn p1p2pn-1 1,n 1。pn 22n。(n)(log2n)/2。8)、素数定理素数定理:素数搜寻素数搜寻寻找素数寻找素数的方法:的方法:Eratosthenes筛法筛法。素性判定素性判定确定型算法确定型算法试除法试除法 尝试从尝试从2到到N的整数是否整除的整数是否整除N。威廉斯方法、艾德利曼威廉斯方法、艾德利曼、鲁梅利法、鲁梅利法、马宁德拉马宁德拉.阿格拉瓦法阿格拉瓦法(log(n)的多项式级算法的多项式级算法)随机算法随机算法费马测试费马
4、测试 利用费马小定理来测试。利用费马小定理来测试。若存在若存在a,(a,n)=1,使得,使得a n 1 1 mod n成立,则称成立,则称n是关于基数是关于基数a的伪素数(的伪素数(Fermat伪素数,伪素数,Carmichael 数数)。)。米勒米勒-拉宾法、拉宾法、GCD和和LCM定义定义 整数整数a1,a2,ak的公共约数称为的公共约数称为a1,a2,ak 的的公约数公约数。不全为零的整数不全为零的整数a1,a2,ak 的公约数中最大一个叫做的公约数中最大一个叫做a1,a2,ak 的的最大公最大公约数约数(或(或最大公因数最大公因数),记为),记为(a1,a2,ak)。由于每个非零整数的
5、约数的个数是有限的,所以最大公约数是存在的,并且是正整数。由于每个非零整数的约数的个数是有限的,所以最大公约数是存在的,并且是正整数。如果如果(a1,a2,ak)=1,则称,则称a1,a2,ak 是是互素的互素的。如果如果(ai,aj)=1,1 i,j k,i j,则称,则称a1,a2,ak 是是两两互素的两两互素的。a1,a2,ak 两两互素可以推出两两互素可以推出(a1,a2,ak)=1,反之则不然。,反之则不然。定义定义 整数整数a1,a2,ak 的公共倍数称为的公共倍数称为a1,a2,ak 的的公倍数公倍数。整数整数a1,a2,ak 的正公倍数中最小的一个叫做的正公倍数中最小的一个叫做
6、a1,a2,ak 的的最小公倍数最小公倍数,记为记为a1,a2,ak。GCD和和LCMn的标准分解式:的标准分解式:n的正因数:的正因数:n的正倍数的正倍数:带余数除法带余数除法 设设a与与b是两个整数,是两个整数,b 0,则存在唯一的两个整数,则存在唯一的两个整数q和和r,使得,使得 a=bq r,0 r|b|。定理定理 若若a=bq r,则,则(a,b)=(b,r)。实际上给出一个求最大公因子的方法。实际上给出一个求最大公因子的方法。推论推论 设设a1,a2,an为不全为零的整数,以为不全为零的整数,以y0表示集合表示集合 A=y:y=a1x1 anxn,xi Z,1 i n 中的中的最小
7、正数最小正数,则,则 对于任何对于任何y A,y0 y;特别地,特别地,y0 ai,1 i n。证明:证明:设设y0=a1x1 anxn,对任意的对任意的y=a1x1 anxn A,存在,存在q,r0 Z,使得,使得 y=qy0 r0,0 r0 y0。因此因此 r0=y qy0=a1(x1 qx1)an(xn qxn)A。如果如果r0 0,那么,因为,那么,因为0 r0 y0,所以,所以r0是是A中比中比y0还小的正数,还小的正数,这与这与y0的定义矛盾。所以的定义矛盾。所以r0=0,即,即y0 y。显然显然ai A(1 i n),所以),所以y0整除每个整除每个ai(1 i n)。)。GCD
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 初等数论1 整除理论 初等 数论 整除 理论
限制150内