第一章 整除 信安数学.ppt

1、巫玲 W,第一章 整除 Divisibility of integers,学习目标 掌握整除、最大公约数、唯一分解定理、素数 掌握欧几里德定理的计算与编程实现 能够解数学建模等领域的相关题目 课程内容的设置 整除、最大公约数、最小公倍数 欧几里得算法 算术基本定理 素数,1.1 整数的基本性质与余数定理,定义1 设 a,b为整数，b0. 若有一整数去 使得 a = bq, 则称 b整除a或a能被b整除, 记为b|a，b叫做a的因数，a叫做b的倍数 若b不能整除a，记为b | a. 注意与/的区别 2|4 4/2=2,1.1 整数的基本性质与余数定理,显然有 对所有a, 1|a. 对所有a, a

2、|0. 对所有 a, a|a. 若a|b, 则对任意的c, 有ac|bc. 若ac|bc且c0, 则a|b,反之亦然 问题：若a|bc, a|b则a|c成立？,1.1 整数的基本性质与余数定理,性质1 （1）a|b且b|c =a|c （2）a|b且b|a =a=b （3）a|b且a|c任意t,sZ，a|tb+sc （=）: tb+sc=taq1+saq2 （=）:t=1,s=0和t=0,s=1分别有a|b和a|c,1.1 整数的基本性质与余数定理,例1 设n为整数，证：若3|n，4|n，则12|n 3|n = n=3m 4|3m,4|4m =4|4m-3m=m =m=4k =n=3m=12k

3、作业(1)：P16 第2、4题,1.1 整数的基本性质与余数定理,证:利用性质（3），m|sa+tb=1 =m=1 a|n =ab|nb，同理ab|na n=n(sa+tb)=sk.ba+tq.ba =ab|n,1.1 整数的基本性质与余数定理,例3 ： m奇， p+q|pm +qm ；p - q|pm - qm,归纳法： (1) m=1, p+q|p+q (2) 设m=2k-1时，p+q|p2k-1+q2k-1 (3) 当m=2k+1时，p2k+1+q2k+1=p2(p2k-1+q2k-1)- q2k-1(p2 - q2) 所以 p+q|p2k+1+q2k+1 所以m奇， p+q|pm +q

4、m 进一步：m为偶数时p - q|pm - qm 但一般p+q | pm +qm,思考,11112 (n个1)是质数还是合数 10012 (n个0)呢？,1.1 整数的基本性质与余数定理,定义2 素数 一个大于1且只能被1和它本身整除的整数, 称为素数; 否则, 称为合数. 整数集合可分三类: 素数、合数和0,1,-1. 正整数集合可分三类: 素数、合数和1. 素数常用p或p1, p2,来表示. 如没有特别说明都是指正的 第4节再讲,1.1 整数的基本性质与余数定理,定义3 设xR， x表示不超过x的最大整数，称作x的整数部分 x表示x-x，称作x的小数部分 如：3.14=3，3.14=0.1

5、4 注意：-3.14=-4，3.14=0.86,1.1 整数的基本性质与余数定理,不是任意两个数都有整除关系 定理7 带余除法，欧几里德除法 若a为是二个整数,b0, 则唯一存在二个整数q和r, 使得下式成立: a=bq+r, 0r|b|.,1.1 整数的基本性质与余数定理,1.1 整数的基本性质与余数定理,显然，若a=bq+r，0r r=0,1.1 整数的基本性质与余数定理,证明：若m为奇数，m=2q+1,m2=4q2+4q+1=4q(q+1)+1 ，q、q+1必有1个偶，除8余1； 若m为偶数，m=2q,m2=4q2 q奇，除8余4；q偶，除8余0； m2-n2除8余0、1、3、4、5、7

6、，都不为2 用第二章的同余表达更清晰,1.1 整数的基本性质与余数定理,整数的表示 不同进制？,1.1 整数的基本性质与余数定理,整数的表示,1.1 整数的基本性质与余数定理,1.1 整数的基本性质与余数定理,1.1 整数的基本性质与余数定理,因此 则： 但,1.1 整数的基本性质与余数定理,1.1 整数的基本性质与余数定理,1.2 最大公因数和最小公倍数,定义3 最大公因数 gcd(a,b),1.2 最大公因数和最小公倍数,在个数不少于3个的互素正整数中, 不一定是每二个正整数都是互素的. 例: (6,10,15)= 1, 但(6,10)=2, (6,15)=3, (10,15)=5.,1.

7、2 最大公因数和最小公倍数,定义4 最小公倍数 lcm(a,b) a,b,1.2 最大公因数和最小公倍数,性质2 （补充） （1）若a|b，则（a,b）=|a|,a,b=|b| （补充）对任意整数x，(a,b)=(a,ax+b) 若d=(a,b)，D=(a,b+ax) 则d|a,d|b, 所以d|b+ax，所以dD 同理D|a，D|b+ax，所以D|b+ax-ax=b 所以D d 所以d=D 推论：（2）若c=ax+b，则(a,c)=(a,b) 因为(a,c)=(a,ax+b)=(a,b),1.2 最大公因数和最小公倍数,性质2 （3） (a,b)|ax+by 根据 d|b,d|a，则d|ax

8、+by，关键x,y可以任意整数 推论：若存在ax+by=1，则(a,b)=1 思考：若(a,b)1，方程ax+by=1有整数解吗?,1.2 最大公因数和最小公倍数,如何计算一条线段上整数点的个数 线段可平移使得两个端点为(0,0),(x,y)（x,y整数），记gcd(x,y)表示最大公约数，则(x/gcd(x,y),y/gcd(x,y)一定在线段上，并且线段上的所有整点都可以表示为k*(x/gcd(x,y),y/gcd(x,y)，其中k=0,1,2, gcd(x,y)，所以包括端点的整点个数为gcd(x,y)+1个,1.2 最大公因数和最小公倍数,性质3 （补充）a|c,b|c a,b|c 证

9、：: L=a,b， 设c=qL+r, 0 r d|(a,b) 证：:设di为a,b的全体公约数，1in L=d1,d2,dn，所以L|a,L|b而|di| L。 所以L=(a,b)，所以若d|a,d|b，则d|L,1.2 最大公因数和最小公倍数,例1-11,例1-11 证明:设(a+b,a-b)=d,所以d|(a+b)+(a-b),即d|2a 同理d|2b 所以d|(2a,2b)=2(a,b)=2 所以d=1或2,1.2 最大公因数和最小公倍数,推论 (a,b,c)=(a,b),c) ; a,b,c=a,b,c 证明：若d=(a,b,c), D=(a,b),c) d|a,d|b，则d|(a,b

10、) 因d|c，则d|(a,b),c)=D D|(a,b) 所以D|a,D|b，因D|c，因此D|d 所以d=D,1.2 最大公因数和最小公倍数,性质3（2） 证明：(b,c)=(b(a,c),c)=(ba,bc,c)=(ba,(b,1)c)=(ba,c) 为什么要b，c不同时为0？ 若c|ab,则(ab,c)=c,所以(b,c)=c，所以c|b,1.2 最大公因数和最小公倍数,性质3(3-6) 作业(2)：P16 第8题,一个有趣的小问题,最短路径问题： 左上角的T到右下角的S,走迷宫,Euclid算法,辗转相除法，更相减损数（九章算术） 反复用带余除法求公约数,Euclid算法,定理 因为,

11、Euclid算法,Euclid算法,Euclid算法,Euclid算法,解 因此,Euclid算法,Euclid 算法 int gcd ( int a, int b ) int mod;while ( mod = a % b ) a = b, b = mod;return b; / a % b =a - a/b*b；注意这里面必须a,b都为正数，否则要加其他判断语句,Euclid算法,也可递归 int gcd ( int a, int b ) if (b=0) return a;else return gcd(b, a%b); ,Euclid算法,Extended-Euclid 算法: 同时求

12、出 v, u 使 gcd ( a, b ) = u * a + v * b,扩展欧几里得算法,法一：(定理1-8)依次把a,b代入 a-bq1=r1 b-r1q2=r2 b-(a-bq1)q2= a(-q2)+b(1+q1 q2) =r2 r1-r2q3=r3 (a-bq1)-(a(-q2)+b(1+q1 q2)q3 = a(1-(-q2 ) q3)+b(-q1 ( 1+q1 q2)q3 )=r3,1 -q1 -q2 1- (-q1)*q2 1-(-q2 ) q3 -q1 ( 1+q1 q2) q3 ,扩展欧几里得算法,如 a=27 b=11,所以：27*(-2)+11*5=1,27-2*11

13、=5 11-2*5 =1 5 -1*5 =0,扩展欧几里得算法,法二： 注意到对于gcd(a0,b0) = d 我们对(a0, b0)用欧几里德辗转相除会最终得到(d, 0) 此时对于把an=d, bn= 0 带入a*x + b*y = d，显然x = 1，y可以为任意值 这里y可以为任意值就意味着解会有无数个。我们可以用a = d, b = 0的情况逆推出来任何gcd(a, b) = d 满足a*x + b*y = d的解。,扩展欧几里得算法,如果x0, y0是b*x + (a%b)*y = d 的解，那么对于a*x + b*y = d的解呢？ 因为 b*x0 + (a - a/b*b)*y

14、 0= a*y 0+ b*(x0 - a/b*y0) 所以a*x + b*y = d的解x1 = y0， y1 = x0 - a/b*y0 这样我们可以程序迭代了。,扩展欧几里得算法,如 a=27 b=11,27=11*2+5 11=5*2+1 5=1*5+0 d=1,1=1 *1 + 0 1=5 *0 + 1 * (1-5/1*0=1) 1=11 *1 + 5 * (0-11/5*1=-2) 1=27*(-2) +11* (1-27/11(-2)=5),x1 = y0， y1 = x0 - a/b*y0,所以：27*(-2)+11*5=1,扩展欧几里得算法,viod Euclid (int

15、a, int b, inty=0； else int i,j,d； Euclid(b,a%b,d,i,j)； gcd=d；x=i；y=i - n/m*j； ,Euclid算法,有了 GCD, LCM 就好办了 LCM ( a, b ) = a * b / GCD ( a, b ) 实际上最好写成a/GCD(a,b)*b 作业(3) p17 第13(1)(2)题，要求写出sa+tb=(a,b)的式子,1.2 最大公因数和最小公倍数,定理 设a,b为不全为零的整数，则 (a,b)=mins: s=ax+by, x,yZ,s0 证明：关键:最小的s0=ax+by, (a,b)|s0 存在a=q1s0

16、+r1 , b=q2s0+r2 0 r1,r2s0, 所以r1 =a-q1 (ax+by)=(1-q1x)a-bq1y 所以r1,r2 S，因为s0最小正整数，矛盾，所以r1,r2 =0 所以a= q1s0, b=q2s0所以s0 |(a,b) ,所以s0 =(a,b) 推论：S由(a,b)的倍数构成,1.2 最大公因数和最小公倍数,定理 设a,b为不全为零的整数，则 方程ax+by=c有整数解 c s: s=ax+by, x,yZ,s0 (a,b)|c 特别的(a,b)=1 存在整数x和y，使得ax+by=1,1.2 最大公因数和最小公倍数,求方程243x+198y=909的一组整数解 解：

17、先求出线性表达式，则先作系数的辗转相除法 243=198+45 9=(243-198)*9-198*2=243*9-198*11 198=45*4+18 9=45-(198-45*4)*2=45*9-198*2 45=18*2+9 9=45-18*2 18=9*2 反推： 因为(243,198)=9|909 因此方程有解 因此243*9-198*11=9 因此 243*9*101-198*11*101=101*9 因此 x0=101*9=909；y0=-11*101=-1111 因此 x=909+22t；y=-1111+27t tZ,1.2 最大公因数和最小公倍数,例：求解12x+6y-5z=

18、13,解：设u=2x+y，则6u-5z=13 (6,5)=1|13，所以有解 13=6*3-5*1，所以u=3+5t,z=1+6t 对于2x+y=3， x=1+s y=1-2s 所以 x=1+6t y=1-7t z=1+6t 作业(4)： 求解312x+753y=345,1.2 最大公因数和最小公倍数,程序实现nx+my=k的求解 Void solve_linear(int n, int m, int k) int s,i,j,d; Euclid(m,n,d,i,j); /前面的扩展Euclid算法，也可用书上的实现 if (k%d=0) for (s=0;s=d-1;s+) cout j*k

19、/d+i*n/d; ,1.3 算术基本定理,更常称为：整数唯一分解定理 整除理论的中心内容,1.3 算术基本定理,预备定理 若p为素数, 则a不能被p整除当且仅当: (p,a)=1 证明 因p为素数, 故p只有二个正因数, 即1和p. 若(p,a)1, 则只有(p,a)=p. 反之, 若(p,1)=1, 则p和a是互素的, 故p|a.,1.3 算术基本定理,1.3 算术基本定理,定理1-11,1.3 算术基本定理,1.3 算术基本定理,1.3 算术基本定理,1.3 算术基本定理,1.3 算术基本定理,1.3 算术基本定理,1.3 算术基本定理,1.3 算术基本定理,推论,1.3 算术基本定理,

20、例1-13 n|ab,n|cd,n|(ac+bd), 证:n|ac,n|bd 证:n= piai,n|ab,n|cd,则n2|abcd,从而 pi2ai|abcd 所以任意i，piai|ac或piai|bd，由于n|(ac+bd) 所以piai|ac和piai|bd同时成立 所以n|ac,n|bd,1.3 算术基本定理,1.3 算术基本定理,1.4 素数,1.4 素数,例：形如4n+1的素数有无穷多个,反证：设mi=4ki+1是形如4n+1的有限i个素数，而p=1+4mi=1+4(4ki+1)=4x+1 由于mi|p-1,所以(mi,p)=1，所以p的所有素因子都不在mi中，所以素数不止i个，

21、矛盾,问题：p的素因子，可能不是4n+1型的,原因：4n+1和4n-1都可能是素数,(4n-1)(4m-1)=4x+1,1.4 素数,例：形如4n-1的素数有无穷多个,反证：设mi=4ki-1是形如4n-1的有限i个素数，而 p=4mi 1 =4(4ki-1)-1=4x-1 由于mi|p-1,所以(mi,p)=1，所以p的素因子都不是mi的一个 再证p素因子中有形如4n-1的。因为素数只能4n1的形式，不可能全为4n+1的，否则p只能是4n+1形式 思考：如何证形如4n+1的素数有无穷多呢？ 提示：构造p时让p只有4n+1形式的素因子 一种方法：利用m!偶，(m!)2+1为4n+1形式，引入奇

22、素数p| (m!)2+1时，证明p只能是4n+1的形式，否则p| (m!)p1；而pm，得证 需要用到后面的费马定理,1.4 素数,换一种写法,1.4 素数,例：证明191是素数,因为 132=169,142=196 所以：若素数p|191，则p13 而2，3，5，7，11，13均不整除191 所以191是素数,1.4 素数,1）pN存储不大于n的所有的素数，二重循环，用已经求出的不大于平方根的所有素数试除 for(i=2;in;i+) for(j=0;jm ,1.4 素数,厄拉托塞师（Eratosthenes）筛法,1.4 素数,1.4 素数,1.4 素数,1.4 素数,1.4 素数,1.4

23、 素数,Eratosthenes的算法,2）增加布尔型数组bN记录是否为素数，初始化所有值=1，从头开始遍历，如果bi=1，则i是素数，将所有的i的倍数j均修改为bj=0 for(i=2;in;+i) 如果bi=1则添加到素数列表p，然后利用循环for(j=i;jn;j+=i) bj=0将i的所有倍数删掉 思考：试与前面1)比较两种方法效率,1.4 素数构造素数,试想一下：2+n！，3+n！，4+n！，n+n! 的连续数列 这时，数列中的第一项n！2 则可被2 整除；第二项n！3 可被3 整除；第三项n！+4 可被4 整除；等等。在这个数列中有n-1个数，没有一个是素数。 通过任意选择n 的大

24、小，你可以得出你想要的无素数的连续整数数列。,1.4 素数构造素数,梦想发明能够计算出素数的公式 欧拉公式：诱人的简单 n2n41 生成：41,47,53 但可能生成合数，How? 后来出现了素性检测，另章介绍,1.4 素数构造素数,思考：n(n+1)+41 n=1,n=3,n=40，41| n2n41 在1，00O 万以下的所有素数中，该公式可得出占总素数的475。而当n 值较低时，该公式工作得更有成效。当n 值小于2，398时，得素数的机会一半对一半。而当n 值小于100 时，该公式得出86 个素数，合成数只有14 个。,1.4 素数构造素数,类似公式4n2170n1,847 计算出1,0

25、00万以下素数的成功率为46.6，并得出760个欧拉公式所不能推出的素数 公式4n24n59 成功率为437，同时得出大约1，500 个不能由其他两个公式推出的素数。 其他还有x!1等,1.4 素数构造素数,证明若2m+1为素数，则m=2n,设p|m，若m2，p为奇素，则 2m/p+1|2m+1，由于2m/p +13，所以2m+1为合数，矛盾 故p只能为2 推论：费马数 如3,5,17,257 任意2个费马数互素 提示：F(j)|F(i)-2 (jI时),1.4 素数构造素数,了解：欧拉关于 不是质数的证明 a=27,b=5 ，a-b3=3 ，1+ab-b4=1+3b=24 所以 232+1=(28)4+1=(2a)4+1=24a4+1 =