《數(shù)論算法》教案1章(整數(shù)的可除性).doc

第 1 章 整數(shù)的可除性內(nèi)容1. 整除性2. 公因數(shù)、最大公因數(shù)3. 輾轉(zhuǎn)相除法（歐幾里得除法）4. 算術(shù)基本定理要點(diǎn)培養(yǎng)對(duì)數(shù)論問題的認(rèn)識(shí)及證明問題的思路數(shù)論從研究整數(shù)開始，叫“整數(shù)論”。經(jīng)進(jìn)一步發(fā)展，叫做“數(shù)論”。確切地說，數(shù)論是研究整數(shù)性質(zhì)的學(xué)科。自然數(shù)（正整數(shù)）負(fù)整數(shù)0（統(tǒng)稱整數(shù)）。算術(shù)運(yùn)算：加、減、乘、除（四則運(yùn)算）。加法、減法和乘法在整數(shù)范圍內(nèi)可以毫無(wú)阻礙地進(jìn)行。但整數(shù)之間的除法在整數(shù)范圍內(nèi)并不一定能夠無(wú)阻礙地進(jìn)行。數(shù)論算法主要從應(yīng)用角度出發(fā)，研究數(shù)論問題中實(shí)用的方法和技術(shù)。1.1 整除的概念 歐幾里得除法(一) 整除概念【定義1.1.1】 設(shè)a, bZ（整數(shù)集合），b0，如果存在qZ，使得abq，則稱b整除a或a可被b整除，記作ba，且稱a是b的倍數(shù)，b是a的因數(shù)（也可稱為除數(shù)、約數(shù)、因子）。否則，稱b不能整除a或a不能被b整除，記作ba。說明：（1） q也是a的因數(shù)，并將q寫為a/b或；（2） 當(dāng)b遍歷整數(shù)a的所有因數(shù)時(shí)，b也遍歷整數(shù)a的所有因數(shù)；（3） 當(dāng)b遍歷整數(shù)a的所有因數(shù)時(shí)，a/b也遍歷整數(shù)a的所有因數(shù)。例：設(shè) a6，則有（1） 當(dāng)b3時(shí)，q26/3（2） 當(dāng)b1, 2, 3, 6,1,2,3,6時(shí)有b1,2,3,6, 1, 2, 3, 6（3） 當(dāng)b1, 2, 3, 6, 1,2,3,6時(shí)有a/b6, 3, 2, 1, 6,3,2,1【特例】：（1） 0是任何非零整數(shù)的倍數(shù)；（2） 1是任何整數(shù)的因數(shù)；（3） 任何非零整數(shù)a是其自身的倍數(shù)，也是其自身的因數(shù)。(二) 性質(zhì)（1） 設(shè)，則 。（證） abq aq(b) 其余類推。【例1.1.1】30的所有因數(shù)：1，2，3，5，6，15，30（2） 傳遞性：，（證）且 bc，ab ac ca。（3） ，則（4） ，則對(duì)任意整數(shù)s、t，有推廣：（5） 若，則ab（證） ab ba a 1 1（6） （c0）（7） 若，則 (三) 例【例1.1.2】證明：若且，則。（證） 已知 。 。即m7q所以 n3(7q)21q 。【例1.1.3】設(shè)。若，則。（證） 又 (ann)ann，即（由a2t1知2ta1，從而2tnann）【例1.1.4】設(shè)a, b是兩個(gè)給定的非零整數(shù)，且有整數(shù)x, y，使得。證明：若且，則（證） 由且 。 n(axby)，即。注意到，由此也證明了例1.1.2?！纠?.1.5】設(shè)是整系數(shù)多項(xiàng)式。若，則（證）由及 （k1, 2, , n） 。應(yīng)用：若，那么。例：設(shè)，判斷7能否整除。因 7q4，故只需判斷：3082？答：不能(四) 素?cái)?shù)（1） 定義（素?cái)?shù)與合數(shù)）設(shè)整數(shù)p0, 1。如果它除了顯然約數(shù)1, p外沒有其它的約數(shù)，那么，就稱為素?cái)?shù)（或質(zhì)數(shù)、不可約數(shù)）。若a0, 1，且不是素?cái)?shù)，則稱為合數(shù)。約定：素?cái)?shù)一般指正整數(shù)。（2） 性質(zhì)（a） 最小正因數(shù)必是素?cái)?shù)（b） n是正整數(shù)，當(dāng)2p且pn，則n是素?cái)?shù)。（c） 素?cái)?shù)有無(wú)窮多。（證）（c）：用反證法。假設(shè)只有有限個(gè)素?cái)?shù)：。構(gòu)造則 且a（i1, 2, , k）。 a必是合數(shù) 存在素?cái)?shù)p，使得 。由假設(shè)知p等于某個(gè)一定整除但素?cái)?shù)，矛盾。因此，假設(shè)是錯(cuò)誤的，即素?cái)?shù)必有無(wú)窮多個(gè)。性質(zhì)（b）的應(yīng)用：快速判斷素?cái)?shù)。擴(kuò)展：設(shè)是全體素?cái)?shù)按大小順序排成的序列，以及。直接計(jì)算可得：， ， ， ， ， ， ， ，前五個(gè)是素?cái)?shù)，后五個(gè)是合數(shù)，但都有一個(gè)比更大的素因數(shù)。未解決的問題：至今還不知道是否有無(wú)窮多個(gè)k使是素?cái)?shù)，也不知道是否有無(wú)窮多個(gè)k使是合數(shù)。(五) 歐幾里德除法也叫帶余數(shù)除法、除法算法初等數(shù)論的證明中最重要、最基本、最常用的工具之一。（1） 歐幾里德除法：設(shè)a, b是兩個(gè)給定的整數(shù)，b0。那么，一定存在唯一的一對(duì)整數(shù)q與r，滿足, 約定：b0。上式可表為, （2）（2） 存在性當(dāng)時(shí)，可取，r0。當(dāng)ba時(shí)，考慮集合，3b，2b，b，0，b，2b，3b，將實(shí)數(shù)分為長(zhǎng)度為b的區(qū)間，a必落在某區(qū)間內(nèi)，即存在整數(shù)q，使得qba(q1)b令rabq，則有, （3） 唯一性設(shè)有也滿足（2）式，即 必有 當(dāng)q時(shí)有 b，矛盾，故必有，。（4） 推論：的充要條件是r0。當(dāng)aqbr時(shí), 有。當(dāng)滿足時(shí)，就有 r0。（5） 一般形式設(shè)a, b是兩個(gè)給定的整數(shù)，則對(duì)任意整數(shù)c，一定存在唯一的一對(duì)整數(shù)q與r，滿足, （3）此外，的充要條件是。例：a100，b30，c10，則10r40，即1003*3010若c35，則35r65，即1002*3040若c50，則50r20，即1005*30(50)(六) 不完全商和余數(shù)【定義1.1.2】設(shè)abqr（），稱q為a被b除所得的不完全商，稱r為a被b除所得的余數(shù)?！就普摗?ba的充要條件是a被b除所得的余數(shù)r0。余數(shù)的分類：1 最小非負(fù)余數(shù) c0，0rb2 最小正余數(shù) c1，1rb3 最大非正余數(shù) cb1，b1r04 最大負(fù)余數(shù) cb，br05 最小絕對(duì)余數(shù) b/2rb/2或b/2rb/2(七) 下整數(shù)與上整數(shù)【定義1.1.3】 設(shè)x是一個(gè)實(shí)數(shù)，稱為下整數(shù)函數(shù)，其值為不大于x的最大整數(shù)。即x滿足x1（原定義為：設(shè)x是一個(gè)實(shí)數(shù)，稱x的整數(shù)部分為小于或等于x的最大整數(shù)，記為）上整數(shù)函數(shù)：表示不小于x的最小整數(shù)。即1xx四舍五入函數(shù)：函數(shù)是將x四舍五入的結(jié)果。說明 當(dāng)aqbr（0r0故 必存在n，使得 （2） 結(jié)論【定理1.3.1】設(shè)整數(shù)ab0，則（a，b），其中是歐幾里得除法（1）中最后一個(gè)非零余數(shù)。（證）由性質(zhì)8，（a，b）（，）（，）（，）再由性質(zhì)7，（a，b） （3） 例【例1.3.9】利用展轉(zhuǎn)相除法求（46480，39423）。（1）取最小非負(fù)余數(shù)（直觀的方法）46480139423 70573943257057 41387057 14138 29194138 12919 12192919 21219 4811219 2481 257481 1257 224257 1224 33224 633 2633 126 726 37 57 15 25 22 12 21所以 （46480，39423）1（2）取最小絕對(duì)余數(shù)（運(yùn)算量較少的方法）46480139423 70573943267057 29197075 22919 12192919 21219 4811219 3481 224481 2224 33224 733 733 57 27 32 12 21(四) 求（a，b）的歐幾里得算法（1） 理論依據(jù)：性質(zhì)8（2） 思路：a) 利用性質(zhì)6，將求兩個(gè)整數(shù)的最大公因數(shù)轉(zhuǎn)化為求兩個(gè)非負(fù)整數(shù)的最大公因數(shù)。b) 運(yùn)用歐幾里得除法，并利用性質(zhì)8，將求兩個(gè)正整數(shù)的最大公因數(shù)轉(zhuǎn)化為求兩個(gè)較小的非負(fù)整數(shù)的最大公因數(shù)。c) 反復(fù)運(yùn)用歐幾里得除法（即廣義歐幾里得除法），將求兩個(gè)正整數(shù)的最大公因數(shù)轉(zhuǎn)化為求0與一個(gè)正整數(shù)的最大公因數(shù)。d) 利用性質(zhì)7，求出0與正整數(shù)的最大公因數(shù)，即為欲求的最大公因數(shù)。（3） 算法：已知ab0S1 求q及r，使 abqrS2 若r0。則 令db；輸出d；結(jié)束 否則 令ab；br；轉(zhuǎn)S1 （4） 算法的復(fù)雜度：設(shè)ab0，則求(a,b)過程中的除法次數(shù)0，輸出 d（a，b）S1 k0S2 若a、b均為偶數(shù)，則 令aa/2；bb/2；kk1；轉(zhuǎn)S2 否則轉(zhuǎn) S3S3 若b是偶數(shù)，則 ab否則轉(zhuǎn)S4S4 若a是偶數(shù)，則 令aa/2； 轉(zhuǎn)S4否則轉(zhuǎn)S5S5 若ab0，則ab否則轉(zhuǎn)S6S6 a(ab)/2S7 若a0，則 d；輸出d；結(jié)束 否則轉(zhuǎn)S4（3） 特點(diǎn)：只用到減法，沒有用到除法（除以2在二進(jìn)制數(shù)運(yùn)算中僅作移位操作）。減運(yùn)算無(wú)疑比除法容易得多。（4） 算法的復(fù)雜度：設(shè)ab0，則減法次數(shù)S（5） 例【例1.3.10】a18，b12算 法abkdS1 k018120S2 若a、b均為偶數(shù)，則 aa/2；bb/2；kk1；轉(zhuǎn)S2 ；否則轉(zhuǎn) S3961S3 若b是偶數(shù)，則 ab；否則轉(zhuǎn)S4691S4 若a是偶數(shù)，則 aa/2；，轉(zhuǎn)S4；否則轉(zhuǎn)S5391S5 若ab0，則ab；否則轉(zhuǎn)S6931S6 a(ab)/23311次減法S7 若a0，則 d；輸出d；結(jié)束 ；否則轉(zhuǎn)S4331S4331S5331S60311次減法S7031d6【例1.3.11】a28，b16算 法abkdS1 k028160S2 若a、b均為偶數(shù)，則 aa/2；bb/2；kk1；轉(zhuǎn)S2 ；否則轉(zhuǎn) S31481S2742S3 若b是偶數(shù)，則 ab；否則轉(zhuǎn)S4472S4 若a是偶數(shù)，則 aa/2；，轉(zhuǎn)S4；否則轉(zhuǎn)S5272S4172S5 若ab0，則ab；否則轉(zhuǎn)S6712S6 a(ab)/23121次減法S7 若a0，則 d；輸出d；結(jié)束 ；否則轉(zhuǎn)S4312S4312S5312S61121次減法S7112S4112S5112S60121次減法S7012d6(六) （a，b）與a、b的關(guān)系（1） 【定理1.3.2】設(shè)a、b為任意正整數(shù)，則存在整數(shù)s、t，使得（a，b）satb一般情形：對(duì)整數(shù)，存在整數(shù)，使得（證）直接由展轉(zhuǎn)相除法，反推回去，即得結(jié)論。（2） 例【例1.3.12】（3） 【定理1.3.3】整數(shù)a、b互素存在整數(shù)s、t，使得satb1（證）必要性：由定理1.3.2知成立。充分性：設(shè)d(a, b) 且有satb1 。da，dbdsatb1d1(七) 求s、t的算法（1）利用求（a，b）的過程反推【例1.3.13】利用展轉(zhuǎn)相除法求s、t。其中46480139423705729933942316720(46480139423)167204648019713394233943257057 4138175570752993(3942357057)2993394231672070757057 14138 2919123841381755(70574138 12919 121951729191238(413812919)2919 21219 4812041219517(291921219)1219 2481 257109481204(12192481)481 1257 224109481204(12192481)257 1224 331422495(2571224)224 633 26113314(224633)33 126 7322611(33126)26 37 5273(2637)3261177 15 252(715)27355 22 115222 21所以 116720464801971339423或 1（1672039423）46480（4468019713）3942322703464802676739423所以：s16720，t19713（2）取最小絕對(duì)余數(shù)2 217 321173233 57273（3357）224 733733314（224733）481 2224331422495（4812224）1219 348122495481204（12194813481）2919 212194812041219517（291921219）7075 22919121951729191238（705722919）39432670572919123870572993（3942367057）46480139423705729933942316720（46480139423）15720454801971339423所以 116720464801971339423或 1（1672039423）46480（4468019713）3942322703464802676739423所以：s22703，t26767（3）算法（4）基于展轉(zhuǎn)相除法：求d（a，b）和s、t，使得dsatbS1 1；0；0；1S2 做除法得 abqrS3 若r0，則db； s； t； 輸出d、s、t； 結(jié)束 S4 ab； br； t； q； t； t； q； t； 轉(zhuǎn)S2【例1.3.14】a132，b108算 法abqrS1 1；0；0；11321081001S2 做除法得 abqr1321081001124S3 若r0，則db；s；t；輸出d、s、t；結(jié)束 1321081001124S4 ab；br；t；x2q；t；t；q；t；轉(zhuǎn)S2108240111124S2108240111412S3 r0108240111412S424121415412S22412141520S3 r02412141520輸出 db12，s4，t5即 1241325108（5）基于斯泰因算法：S1 k0； F0；S2 若a、b均為偶數(shù)，則 aa/2； bb/2； kk1； 轉(zhuǎn)S2 否則轉(zhuǎn) S3S3 若b為偶數(shù)，則 ab； F1 否則轉(zhuǎn)S4S4 Aa； Bb； 1；0；0；1S5 若a是偶數(shù)，則 為偶數(shù)，轉(zhuǎn)S6；否則轉(zhuǎn)S7否則轉(zhuǎn)S8S6 aa/2； /2； /2； 轉(zhuǎn)S5 S7 若，則 ； ； 轉(zhuǎn)S6 否則 ； ； 轉(zhuǎn)S6 S8 若a0，有ta, bta, tb，從而有a，bd（i）am， bm ， （3） 設(shè)為整數(shù)，令，則。應(yīng)用：【例1.4.2】求最小公倍數(shù)120，150，210，35。（解）120，150600600，21042004200，354200故120，150，210，354200即 120，150，210，35120，150，210，35 600，210，354200，3542001.5 算術(shù)基本定理(一) 整數(shù)分解（1） 算術(shù)基本定理【定理1.5.1】（算術(shù)基本定理）任一整數(shù)n1都可以表示成素?cái)?shù)的乘積。且在不考慮乘積順序的情況下，該表達(dá)式是唯一的。即， （證）存在性：歸納法唯一性：【例1.5.1】寫出整數(shù)45，49，100，128的因數(shù)分解式（解）由定理1.5.1453354977100225512822222222（2） 標(biāo)準(zhǔn)分解式【定理1.5.2】任一整數(shù)n1都可以唯一地表示成， 0，i1,2,k其中 且均為素?cái)?shù)?！纠?.5.2】寫出整數(shù)45，49，100，128的標(biāo)準(zhǔn)分解式（解）由例1.5.145325， 4972， 1002252， 12827（3） 求素因數(shù)分解式的復(fù)雜度正整數(shù)的素因數(shù)分解是NP問題。(二) 公因數(shù)（1） 因數(shù)的條件【定理1.5.3】設(shè)整數(shù)n1有標(biāo)準(zhǔn)分解式， 0，i1,2,k則d是n的正因數(shù)， ，i1,2,k（2） 因數(shù)的個(gè)數(shù)【例1.5.3】設(shè)正整數(shù)有標(biāo)準(zhǔn)分解式， 0，i1,2,k則n的正因數(shù)的個(gè)數(shù)為 （證）由及（i1,2,k）的取值范圍即知。（3） 求最大公因數(shù)和最小公倍數(shù)的方法三【定理1.5.4】設(shè)正整數(shù)a、b的素因數(shù)分解式為， 0，i1,2,k， 0，i1,2,k令，則有(a，b)a，b【推論】設(shè)a，b是兩個(gè)正整數(shù)，則(a，b) a，bab