初等数论1-整除理论.ppt

整 除 理 论,1、素数 (1)、素因子 (2)、素数分布 (3)、素数搜寻 (4)、素性判定 2、GCD和LCM,定义 若整数a 0，1，并且只有约数 1和 a，则称a是素数（或质数）； 否则称a为合数。 定理 任何大于1的整数a都至少有一个素约数。 推论 任何大于1的合数a必有一个不超过a1/2的素约数。 定理 (算术基本定理) 任何大于1的整数n可以唯一地表示成(标准分解式) 其中p1 , p2, , pk 是素数，p1 p2 pk，1, 2, , k是正整数。 哥德巴赫猜想：“每个大于2的偶数均可表成为两个素数之和” 陈景润： “每一个充分大的偶数都可表为一个素数及一个不超过两个素数乘积之和”,素因子,素数分布,1)、任意两个相邻的正整数n和nl (n3)中必有一个不是素数。 相邻两整数均为素数只有 2和 3。 2)、n和n2均为素数的有很多, 这样一对素数称为孪生素数。 在100以内有七对孪生素数: (3,5),(5,7),(11,13),(29,31),(41,43),(59,61)和(71,73)。,自然(2013.5.14)：新罕布什尔大学（Lecturer）（University of New Hampshire，UNH）张益唐（数学年刊（Annals of Mathematics）存在无穷多对素数，其差小于7000万。,素数分布,1)、任意两个相邻的正整数n和nl (n3)中必有一个不是素数。 相邻两整数均为素数只有 2和 3。 2)、n和n2均为素数的有很多, 这样一对素数称为孪生素数。 在100以内有七对孪生素数: (3,5),(5,7),(11,13),(29,31),(41,43),(59,61)和(71,73)。 3)、 p为素数，2p-1称为Mersenne数；素数2p-1称为Mersenne素数。 p=2,3,5,7时，2p-1都是素数；p=11时， 2p-1 =2047=2389不是素数 。 已发现最大梅森素数是p43,112,609的情形，一个12,978,189位数。 若an-1(a1)是素数，则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的整数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)的多项式级算法) 随机算法 费马测试 利用费马小定理来测试。 若存在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)。 由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数。 如果(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 的正公倍数中最小的一个叫做a1, a2, , ak 的最小公倍数，记为a1, a2, , ak。,GCD和LCM,n的标准分解式： 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，xiZ，1 i n 中的最小正数，则 对于任何yA， y0y； 特别地， y0ai，1 i n。 证明： 设y0 = a1x1 anxn， 对任意的y = a1x1 anxnA，存在q, r0Z，使得 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，即y0y。 显然aiA（1 i n），所以y0整除每个ai（1 i n）。,GCD和LCM,定理 设a1, a2, , ak Z，记 A = y：y = ，xiZ， i k 。 如果y0是集合A中最小的正数，则y0 = (a1, a2, , ak)。 推论 设d是a1, a2, , ak的一个公约数，则d(a1, a2, , ak)。 最大公约数不但是公约数中的最大的，而且是所有公约数的倍数。 定理 记d = (a1, a2, , ak)，则 (a1/d, a2/d, , ak/d)=1。 特别地, (a/(a,b), b/(a,b)=1 。 定理 (a1, a2, , ak) = 1的充要条件是存在整数x1, x2, , xk，使得 a1x1 a2x2 akxk = 1。 定理 对于任意的整数a，b，c，下面的结论成立： () 由bac及(a, b) = 1可以推出bc； () 由bc，ac及(a, b) = 1可以推出abc。 推论 若p是素数，则下述结论成立： () pab pa或pb； () pa2 pa。,GCD和LCM,推论 若 (a, b) = 1，则(a, bc) = (a, c)。 （备注1） 推论 若 (a, bi) = 1，1 i n，则(a, b1b2bn) = 1。 定理 对于任意的n个整数a1, a2, , an ，记 （备注2） (a1, a2) = d2， (d2, a3) = d3， ， (dn-2, an-1) = dn-1， (dn-1, an) = dn， 则 dn = (a1, a2, , an)。,GCD和LCM,定理 下面的等式成立： () a, 1 = |a|，a, a = |a|； () a, b = b, a； () a1, a2, , ak = |a1|, |a2| , |ak|； () 若ab，则a, b = |b|。 推论 由a,b=ab/(a,b)有：两个整数的任何公倍数可以被它们的最小公倍数整除。 定理 对于任意的n个整数a1, a2, , an ，记 a1, a2 = m2， m2, a3 = m3， ， mn2, an1 = mn1， mn1, an = mn，则 a1, a2, , an = mn。 推论 若m是a1, a2, , an的公倍数，则a1, a2, , an | m。,GCD和LCM,定理 整数a1, a2, , an 两两互素，即(ai, aj) = 1，1 i, j n，i j的充要条件是 a1, a2, , an = a1 a2 an 。 如果m1, m2, , mk是两两互素的整数， 那么 要证明m = m1m2mk整除某个整数Q， 只需证明对于每个i，1 i k，都有miQ。 这一点在实际计算中是很有用的。 对于多项式f(x)，要验证命题“mf(n)，nZ”是否成立， 可以验证“mf(r)，r = 0, 1, , m 1”是否成立。 这需要做m次除法。 但是，若分别验证“mif(ri)，ri = 0, 1, , mi 1，1 i k”是否成立， 则总共需要做m1 m2 mk次除法，显然远远少于m1m2mk = m。,GCD和LCM,辗转相除法/Euclid算法 设a与b是两个整数，b 0，依次做带余数除法： a = bq1 r1， 0 r1 r2 ，所以式(1)中只包含有限个等式。,GCD和LCM,辗转相除法/Euclid算法 引理 用下面的方式定义Fibonacci数列Fn： F1 = F2 = 1，Fn = Fn 1 Fn 2，n 3， 那么对于任意的整数n 3，有 Fn n 2， (2) 其中 =(1+51/2)/2。 定理(Lame) 设a, bN，a b，使用在式(1)中的记号，则 n 5log10b。 定理 使用式(1)中的记号，记 P0 = 1，P1 = q1，Pk = qkPk 1 Pk 2，k 2， Q0 = 0，Q1 = 1，Qk = qkQk 1 Qk 2，k 2， 则 aQk bPk = (1)k 1rk，k = 1, 2, , n 。 (3) 利用辗转相除法可以求出整数x，y，使得 ax by = (a, b) 。 (4) 为此所需要的除法次数是O(log10b)。,GCD和LCM,辗转相除法/Euclid算法 但是，如果只需要计算(a, b)而不需要求出使式(4)成立的整数x与y，则 所需要的除法次数还可更少一些。 设a和b是正整数，基于下面的四个基本事实，只使用被2除的除法运算和减法运算就可以计算出(a, b)。 () 若ab，则(a, b