1、巫玲 W,第一章 整除 Divisibility of integers,學(xué)習(xí)目標(biāo) 掌握整除、最大公約數(shù)、唯一分解定理、素?cái)?shù) 掌握歐幾里德定理的計(jì)算與編程實(shí)現(xiàn) 能夠解數(shù)學(xué)建模等領(lǐng)域的相關(guān)題目 課程內(nèi)容的設(shè)置 整除、最大公約數(shù)、最小公倍數(shù) 歐幾里得算法 算術(shù)基本定理 素?cái)?shù),1.1 整數(shù)的基本性質(zhì)與余數(shù)定理,定義1 設(shè) a,b為整數(shù)，b0. 若有一整數(shù)去 使得 a = bq, 則稱 b整除a或a能被b整除, 記為b|a，b叫做a的因數(shù)，a叫做b的倍數(shù) 若b不能整除a，記為b | a. 注意與/的區(qū)別 2|4 4/2=2,1.1 整數(shù)的基本性質(zhì)與余數(shù)定理,顯然有 對所有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 整數(shù)的基本性質(zhì)與余數(shù)定理,性質(zhì)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 整數(shù)的基本性質(zhì)與余數(shù)定理,例1 設(shè)n為整數(shù)，證：若3|n，4|n，則12|n 3|n = n=3m 4|3m,4|4m =4|4m-3m=m =m=4k =n=3m=12k

3、作業(yè)(1)：P16 第2、4題,1.1 整數(shù)的基本性質(zhì)與余數(shù)定理,證:利用性質(zhì)（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 整數(shù)的基本性質(zhì)與余數(shù)定理,例3 ： m奇， p+q|pm +qm ；p - q|pm - qm,歸納法： (1) m=1, p+q|p+q (2) 設(shè)m=2k-1時(shí)，p+q|p2k-1+q2k-1 (3) 當(dāng)m=2k+1時(shí)，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 進(jìn)一步：m為偶數(shù)時(shí)p - q|pm - qm 但一般p+q | pm +qm,思考,11112 (n個(gè)1)是質(zhì)數(shù)還是合數(shù) 10012 (n個(gè)0)呢？,1.1 整數(shù)的基本性質(zhì)與余數(shù)定理,定義2 素?cái)?shù) 一個(gè)大于1且只能被1和它本身整除的整數(shù), 稱為素?cái)?shù); 否則, 稱為合數(shù). 整數(shù)集合可分三類: 素?cái)?shù)、合數(shù)和0,1,-1. 正整數(shù)集合可分三類: 素?cái)?shù)、合數(shù)和1. 素?cái)?shù)常用p或p1, p2,來表示. 如沒有特別說明都是指正的 第4節(jié)再講,1.1 整數(shù)的基本性質(zhì)與余數(shù)定理,定義3 設(shè)xR， x表示不超過x的最大整數(shù)，稱作x的整數(shù)部分 x表示x-x，稱作x的小數(shù)部分 如：3.14=3，3.14=0.1

5、4 注意：-3.14=-4，3.14=0.86,1.1 整數(shù)的基本性質(zhì)與余數(shù)定理,不是任意兩個(gè)數(shù)都有整除關(guān)系 定理7 帶余除法，歐幾里德除法 若a為是二個(gè)整數(shù),b0, 則唯一存在二個(gè)整數(shù)q和r, 使得下式成立: a=bq+r, 0r|b|.,1.1 整數(shù)的基本性質(zhì)與余數(shù)定理,1.1 整數(shù)的基本性質(zhì)與余數(shù)定理,顯然，若a=bq+r，0r r=0,1.1 整數(shù)的基本性質(zhì)與余數(shù)定理,證明：若m為奇數(shù)，m=2q+1,m2=4q2+4q+1=4q(q+1)+1 ，q、q+1必有1個(gè)偶，除8余1； 若m為偶數(shù)，m=2q,m2=4q2 q奇，除8余4；q偶，除8余0； m2-n2除8余0、1、3、4、5、7

6、，都不為2 用第二章的同余表達(dá)更清晰,1.1 整數(shù)的基本性質(zhì)與余數(shù)定理,整數(shù)的表示 不同進(jìn)制？,1.1 整數(shù)的基本性質(zhì)與余數(shù)定理,整數(shù)的表示,1.1 整數(shù)的基本性質(zhì)與余數(shù)定理,1.1 整數(shù)的基本性質(zhì)與余數(shù)定理,1.1 整數(shù)的基本性質(zhì)與余數(shù)定理,因此 則： 但,1.1 整數(shù)的基本性質(zhì)與余數(shù)定理,1.1 整數(shù)的基本性質(zhì)與余數(shù)定理,1.2 最大公因數(shù)和最小公倍數(shù),定義3 最大公因數(shù) gcd(a,b),1.2 最大公因數(shù)和最小公倍數(shù),在個(gè)數(shù)不少于3個(gè)的互素正整數(shù)中, 不一定是每二個(gè)正整數(shù)都是互素的. 例: (6,10,15)= 1, 但(6,10)=2, (6,15)=3, (10,15)=5.,1.

7、2 最大公因數(shù)和最小公倍數(shù),定義4 最小公倍數(shù) lcm(a,b) a,b,1.2 最大公因數(shù)和最小公倍數(shù),性質(zhì)2 （補(bǔ)充） （1）若a|b，則（a,b）=|a|,a,b=|b| （補(bǔ)充）對任意整數(shù)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) 因?yàn)?a,c)=(a,ax+b)=(a,b),1.2 最大公因數(shù)和最小公倍數(shù),性質(zhì)2 （3） (a,b)|ax+by 根據(jù) d|b,d|a，則d|ax

8、+by，關(guān)鍵x,y可以任意整數(shù) 推論：若存在ax+by=1，則(a,b)=1 思考：若(a,b)1，方程ax+by=1有整數(shù)解嗎?,1.2 最大公因數(shù)和最小公倍數(shù),如何計(jì)算一條線段上整數(shù)點(diǎn)的個(gè)數(shù) 線段可平移使得兩個(gè)端點(diǎn)為(0,0),(x,y)（x,y整數(shù)），記gcd(x,y)表示最大公約數(shù)，則(x/gcd(x,y),y/gcd(x,y)一定在線段上，并且線段上的所有整點(diǎn)都可以表示為k*(x/gcd(x,y),y/gcd(x,y)，其中k=0,1,2, gcd(x,y)，所以包括端點(diǎn)的整點(diǎn)個(gè)數(shù)為gcd(x,y)+1個(gè),1.2 最大公因數(shù)和最小公倍數(shù),性質(zhì)3 （補(bǔ)充）a|c,b|c a,b|c 證

9、：: L=a,b， 設(shè)c=qL+r, 0 r d|(a,b) 證：:設(shè)di為a,b的全體公約數(shù)，1in L=d1,d2,dn，所以L|a,L|b而|di| L。 所以L=(a,b)，所以若d|a,d|b，則d|L,1.2 最大公因數(shù)和最小公倍數(shù),例1-11,例1-11 證明:設(shè)(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 最大公因數(shù)和最小公倍數(shù),推論 (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 最大公因數(shù)和最小公倍數(shù),性質(zhì)3（2） 證明：(b,c)=(b(a,c),c)=(ba,bc,c)=(ba,(b,1)c)=(ba,c) 為什么要b，c不同時(shí)為0？ 若c|ab,則(ab,c)=c,所以(b,c)=c，所以c|b,1.2 最大公因數(shù)和最小公倍數(shù),性質(zhì)3(3-6) 作業(yè)(2)：P16 第8題,一個(gè)有趣的小問題,最短路徑問題： 左上角的T到右下角的S,走迷宮,Euclid算法,輾轉(zhuǎn)相除法，更相減損數(shù)（九章算術(shù)） 反復(fù)用帶余除法求公約數(shù),Euclid算法,定理 因?yàn)?

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都為正數(shù)，否則要加其他判斷語句,Euclid算法,也可遞歸 int gcd ( int a, int b ) if (b=0) return a;else return gcd(b, a%b); ,Euclid算法,Extended-Euclid 算法: 同時(shí)求

12、出 v, u 使 gcd ( a, b ) = u * a + v * b,擴(kuò)展歐幾里得算法,法一：(定理1-8)依次把a(bǔ),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 ,擴(kuò)展歐幾里得算法,如 a=27 b=11,所以：27*(-2)+11*5=1,27-2*11

13、=5 11-2*5 =1 5 -1*5 =0,擴(kuò)展歐幾里得算法,法二： 注意到對于gcd(a0,b0) = d 我們對(a0, b0)用歐幾里德輾轉(zhuǎn)相除會(huì)最終得到(d, 0) 此時(shí)對于把a(bǔ)n=d, bn= 0 帶入a*x + b*y = d，顯然x = 1，y可以為任意值 這里y可以為任意值就意味著解會(huì)有無數(shù)個(gè)。我們可以用a = d, b = 0的情況逆推出來任何gcd(a, b) = d 滿足a*x + b*y = d的解。,擴(kuò)展歐幾里得算法,如果x0, y0是b*x + (a%b)*y = d 的解，那么對于a*x + b*y = d的解呢？ 因?yàn)?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 這樣我們可以程序迭代了。,擴(kuò)展歐幾里得算法,如 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,擴(kuò)展歐幾里得算法,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 ) 實(shí)際上最好寫成a/GCD(a,b)*b 作業(yè)(3) p17 第13(1)(2)題，要求寫出sa+tb=(a,b)的式子,1.2 最大公因數(shù)和最小公倍數(shù),定理 設(shè)a,b為不全為零的整數(shù)，則 (a,b)=mins: s=ax+by, x,yZ,s0 證明：關(guān)鍵:最小的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，因?yàn)閟0最小正整數(shù)，矛盾，所以r1,r2 =0 所以a= q1s0, b=q2s0所以s0 |(a,b) ,所以s0 =(a,b) 推論：S由(a,b)的倍數(shù)構(gòu)成,1.2 最大公因數(shù)和最小公倍數(shù),定理 設(shè)a,b為不全為零的整數(shù)，則 方程ax+by=c有整數(shù)解 c s: s=ax+by, x,yZ,s0 (a,b)|c 特別的(a,b)=1 存在整數(shù)x和y，使得ax+by=1,1.2 最大公因數(shù)和最小公倍數(shù),求方程243x+198y=909的一組整數(shù)解 解：

17、先求出線性表達(dá)式，則先作系數(shù)的輾轉(zhuǎn)相除法 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 反推： 因?yàn)?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 最大公因數(shù)和最小公倍數(shù),例：求解12x+6y-5z=

18、13,解：設(shè)u=2x+y，則6u-5z=13 (6,5)=1|13，所以有解 13=6*3-5*1，所以u(píng)=3+5t,z=1+6t 對于2x+y=3， x=1+s y=1-2s 所以 x=1+6t y=1-7t z=1+6t 作業(yè)(4)： 求解312x+753y=345,1.2 最大公因數(shù)和最小公倍數(shù),程序?qū)崿F(xiàn)nx+my=k的求解 Void solve_linear(int n, int m, int k) int s,i,j,d; Euclid(m,n,d,i,j); /前面的擴(kuò)展Euclid算法，也可用書上的實(shí)現(xiàn) if (k%d=0) for (s=0;s=d-1;s+) cout j*k

19、/d+i*n/d; ,1.3 算術(shù)基本定理,更常稱為：整數(shù)唯一分解定理 整除理論的中心內(nèi)容,1.3 算術(shù)基本定理,預(yù)備定理 若p為素?cái)?shù), 則a不能被p整除當(dāng)且僅當(dāng): (p,a)=1 證明 因p為素?cái)?shù), 故p只有二個(gè)正因數(shù), 即1和p. 若(p,a)1, 則只有(p,a)=p. 反之, 若(p,1)=1, 則p和a是互素的, 故p|a.,1.3 算術(shù)基本定理,1.3 算術(shù)基本定理,定理1-11,1.3 算術(shù)基本定理,1.3 算術(shù)基本定理,1.3 算術(shù)基本定理,1.3 算術(shù)基本定理,1.3 算術(shù)基本定理,1.3 算術(shù)基本定理,1.3 算術(shù)基本定理,1.3 算術(shù)基本定理,推論,1.3 算術(shù)基本定理,

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同時(shí)成立 所以n|ac,n|bd,1.3 算術(shù)基本定理,1.3 算術(shù)基本定理,1.4 素?cái)?shù),1.4 素?cái)?shù),例：形如4n+1的素?cái)?shù)有無窮多個(gè),反證：設(shè)mi=4ki+1是形如4n+1的有限i個(gè)素?cái)?shù)，而p=1+4mi=1+4(4ki+1)=4x+1 由于mi|p-1,所以(mi,p)=1，所以p的所有素因子都不在mi中，所以素?cái)?shù)不止i個(gè)，

21、矛盾,問題：p的素因子，可能不是4n+1型的,原因：4n+1和4n-1都可能是素?cái)?shù),(4n-1)(4m-1)=4x+1,1.4 素?cái)?shù),例：形如4n-1的素?cái)?shù)有無窮多個(gè),反證：設(shè)mi=4ki-1是形如4n-1的有限i個(gè)素?cái)?shù)，而 p=4mi 1 =4(4ki-1)-1=4x-1 由于mi|p-1,所以(mi,p)=1，所以p的素因子都不是mi的一個(gè) 再證p素因子中有形如4n-1的。因?yàn)樗財(cái)?shù)只能4n1的形式，不可能全為4n+1的，否則p只能是4n+1形式 思考：如何證形如4n+1的素?cái)?shù)有無窮多呢？ 提示：構(gòu)造p時(shí)讓p只有4n+1形式的素因子 一種方法：利用m!偶，(m!)2+1為4n+1形式，引入奇

22、素?cái)?shù)p| (m!)2+1時(shí)，證明p只能是4n+1的形式，否則p| (m!)p1；而pm，得證 需要用到后面的費(fèi)馬定理,1.4 素?cái)?shù),換一種寫法,1.4 素?cái)?shù),例：證明191是素?cái)?shù),因?yàn)?132=169,142=196 所以：若素?cái)?shù)p|191，則p13 而2，3，5，7，11，13均不整除191 所以191是素?cái)?shù),1.4 素?cái)?shù),1）pN存儲(chǔ)不大于n的所有的素?cái)?shù)，二重循環(huán)，用已經(jīng)求出的不大于平方根的所有素?cái)?shù)試除 for(i=2;in;i+) for(j=0;jm ,1.4 素?cái)?shù),厄拉托塞師（Eratosthenes）篩法,1.4 素?cái)?shù),1.4 素?cái)?shù),1.4 素?cái)?shù),1.4 素?cái)?shù),1.4 素?cái)?shù),1.4

23、 素?cái)?shù),Eratosthenes的算法,2）增加布爾型數(shù)組bN記錄是否為素?cái)?shù)，初始化所有值=1，從頭開始遍歷，如果bi=1，則i是素?cái)?shù)，將所有的i的倍數(shù)j均修改為bj=0 for(i=2;in;+i) 如果bi=1則添加到素?cái)?shù)列表p，然后利用循環(huán)for(j=i;jn;j+=i) bj=0將i的所有倍數(shù)刪掉 思考：試與前面1)比較兩種方法效率,1.4 素?cái)?shù)構(gòu)造素?cái)?shù),試想一下：2+n！，3+n！，4+n！，n+n! 的連續(xù)數(shù)列 這時(shí)，數(shù)列中的第一項(xiàng)n！2 則可被2 整除；第二項(xiàng)n！3 可被3 整除；第三項(xiàng)n！+4 可被4 整除；等等。在這個(gè)數(shù)列中有n-1個(gè)數(shù)，沒有一個(gè)是素?cái)?shù)。 通過任意選擇n 的大

24、小，你可以得出你想要的無素?cái)?shù)的連續(xù)整數(shù)數(shù)列。,1.4 素?cái)?shù)構(gòu)造素?cái)?shù),夢想發(fā)明能夠計(jì)算出素?cái)?shù)的公式 歐拉公式：誘人的簡單 n2n41 生成：41,47,53 但可能生成合數(shù)，How? 后來出現(xiàn)了素性檢測，另章介紹,1.4 素?cái)?shù)構(gòu)造素?cái)?shù),思考：n(n+1)+41 n=1,n=3,n=40，41| n2n41 在1，00O 萬以下的所有素?cái)?shù)中，該公式可得出占總素?cái)?shù)的475。而當(dāng)n 值較低時(shí)，該公式工作得更有成效。當(dāng)n 值小于2，398時(shí)，得素?cái)?shù)的機(jī)會(huì)一半對一半。而當(dāng)n 值小于100 時(shí)，該公式得出86 個(gè)素?cái)?shù)，合成數(shù)只有14 個(gè)。,1.4 素?cái)?shù)構(gòu)造素?cái)?shù),類似公式4n2170n1,847 計(jì)算出1,0

25、00萬以下素?cái)?shù)的成功率為46.6，并得出760個(gè)歐拉公式所不能推出的素?cái)?shù) 公式4n24n59 成功率為437，同時(shí)得出大約1，500 個(gè)不能由其他兩個(gè)公式推出的素?cái)?shù)。 其他還有x!1等,1.4 素?cái)?shù)構(gòu)造素?cái)?shù),證明若2m+1為素?cái)?shù)，則m=2n,設(shè)p|m，若m2，p為奇素，則 2m/p+1|2m+1，由于2m/p +13，所以2m+1為合數(shù)，矛盾 故p只能為2 推論：費(fèi)馬數(shù) 如3,5,17,257 任意2個(gè)費(fèi)馬數(shù)互素 提示：F(j)|F(i)-2 (jI時(shí)),1.4 素?cái)?shù)構(gòu)造素?cái)?shù),了解：歐拉關(guān)于 不是質(zhì)數(shù)的證明 a=27,b=5 ，a-b3=3 ，1+ab-b4=1+3b=24 所以 232+1=(28)4+1=(2a)4+1=24a4+1 =