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

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