孟飛飛的畢業(yè)論文 (1)

1、 學(xué)校代碼: 11059 學(xué) 號:1107011032 Hefei University 畢業(yè)論文（設(shè)計）BACHELOR DISSERTATION 論文題目: 帶余除法及其應(yīng)用研究 學(xué)位類別: 理學(xué)學(xué)士 學(xué)科專業(yè): 信息與計算科學(xué) 作者姓名: 孟飛飛 導(dǎo)師姓名: 余海峰 完成時間: 2015年05月03日 帶余除法及其應(yīng)用研究摘要本文的主旨思想是帶余除法的簡單介紹以及帶余除法在日常生活中的應(yīng)用，整片論文都圍繞帶余除法來展開論述，先是介紹帶余除法的來源及課題意義，然后通過整數(shù)的帶余除法和多項式的帶余除法讓大家對帶余除法的應(yīng)用有一個更深的認(rèn)識。最后通過實(shí)例來展現(xiàn)其在應(yīng)用研究中所起到的作用。本文的

2、正文是介紹整數(shù)和多項式的帶余除法，從這二個層面可以認(rèn)識到帶余除法是一種普遍應(yīng)用于生活中的思想?？梢赃@樣說多項式的帶余除法是整數(shù)帶余除法的推廣，所以有必要對整數(shù)帶余除法進(jìn)行介紹，多項式的帶余除法中將涉及輾轉(zhuǎn)相除法的介紹，整除的基本概念與基本性質(zhì)、最大公因式、公共根、重根以及一元多項式矩陣的相關(guān)性質(zhì)。下面就開始進(jìn)入本文的正題吧!關(guān)鍵詞：一元多項式 帶余除法 輾轉(zhuǎn)相除法 最大公因式 一元多項式矩陣With more than division and its application research abstractPurpose of this article is more than

3、with division of simple introduction, and with the application of the division in the daily life, the whole piece of paper around with yu to discourse upon the division, first introduced more than with the source of the division and the topic significance, and then through more than more than with d

4、ivision and polynomial with integer division let everybody to take over the application of the division has a deeper understanding. Finally by an example to show its application in play a role in the study.The body of this paper is to introduce more than integer and polynomial division, from the two

5、 aspects can be realized with residual division is a common used in the life of thought. More than can say this polynomial with division is the development of more than integer with division, so it is necessary to carry out more than integer with division, polynomial with residual division will invo

6、lve division algorithm is introduced, the basic concept of divisible and basic properties, the biggest common factor, public root, root and the characters of one yuan polynomial matrix. The following began to get into this business!Keywords: more than one yuan polynomial division Division algorithm

7、The greatest common factor is one yuan polynomial matrix目錄第一章 前言51.1 研究背景51.2 課題意義7第二章 整數(shù)的帶余除法82.1 整數(shù)帶余除法的解釋及證明82.2 整數(shù)帶余除法的一些性質(zhì)92.3最大公約數(shù)與輾轉(zhuǎn)相除法92.4 整除的進(jìn)一步性質(zhì)與最小公倍數(shù)10第三章多項式的帶余除法123.1多項式帶余除法的定理及其證明123.2 帶余除法的二種計算格式133.2.1 普通除法（長除法）133.2.2 豎式除法133.2.3 綜合除法14第四章 帶余除法在解題中的應(yīng)用154.1 有關(guān)兩個多項式除法與整除關(guān)系問題154.2 輾轉(zhuǎn)相除

8、法是帶余除法的特殊應(yīng)用164.2.1 輾轉(zhuǎn)相除法計算兩個多項式的最大公因式及它們與最大公因式的組合關(guān)系164.2.2 求兩個多項式的公共根184.2.3 解有關(guān)多項式的重根，重因式問題184.3 求函數(shù)值f(a)184.4 解有關(guān)有理數(shù)域上的因式分解及有理根194.5 帶余除法在矩陣多項式中的應(yīng)用204,5.1 關(guān)于矩陣多形式可逆的判定204.5.2 有關(guān)矩陣最小多項式的問題21參考文獻(xiàn)23致 謝24第一章 前言1.1 研究背景 帶余除法（也稱為歐幾里德除法）是數(shù)學(xué)中的一種基本算術(shù)計算方式。給定一個被除數(shù)a和一個除數(shù)b，帶余除法給出一個整數(shù)q和一個介于一定范圍的余數(shù)r，使得該等式成立：a =

9、bq + r。一般限定余數(shù)的范圍在0與b之間，也有限定在-b/2與b/2之間。這樣的限定都是為了使得滿足等式的q有且僅有一個。這時候的q稱為帶余除法的商。帶余除法一般表示為：a / b=q r 。表達(dá)為：“a除以b等于q，余r”。最常見的帶余除法是整數(shù)與整數(shù)的帶余除法（被除數(shù)a和除數(shù)b都是整數(shù)），但實(shí)數(shù)與整數(shù)乃至實(shí)數(shù)與實(shí)數(shù)的帶余除法也有應(yīng)用。對一般的抽象代數(shù)系統(tǒng)，能夠進(jìn)行帶余除法的都是具有歐幾里德性質(zhì)的系統(tǒng)。如果余數(shù)為零，則稱b整除a。一般約定除數(shù)b不能為0.帶余除法的計算有長久的歷史，有各種計算工具和計算方法。最常用的是長除法（豎式除法）。帶余除法在數(shù)論中有不少用途，比如說輾轉(zhuǎn)相除法的基本步

10、驟就是帶余除法。 在數(shù)學(xué)中，輾轉(zhuǎn)相除法，又稱歐幾里得算法，是求最大公約數(shù)的算法。輾轉(zhuǎn)相除法首次出現(xiàn)于歐幾里得的幾何原本（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現(xiàn)的九章算術(shù)。兩個整數(shù)的最大公約數(shù)是能夠同時整除它們的最大的正整數(shù)。輾轉(zhuǎn)相除法基于如下原理：兩個整數(shù)的最大公約數(shù)等于其中較小的數(shù)和兩數(shù)的差的最大公約數(shù)。例如，252和105的最大公約數(shù)是21（252=21×12；105=21×5）；因為252105=21× (125) =147，所以147和105的最大公約數(shù)也是21。在這個過程中，較大的數(shù)縮小了，所以繼續(xù)進(jìn)行同樣的計算可以不斷縮小這兩個數(shù)直

11、至其中一個變成零。這時，所剩下的還沒有變成零的數(shù)就是兩數(shù)的最大公約數(shù)。由輾轉(zhuǎn)相除法也可以推出，兩數(shù)的最大公約數(shù)可以用兩數(shù)的整數(shù)倍相加來表示，如21=5×105+ (2)×252。這個重要的結(jié)論叫做裴蜀定理。輾轉(zhuǎn)相除法最早出現(xiàn)在歐幾里得的幾何原本中（大約公元前300年），所以它是現(xiàn)行的算法中歷史最悠久的。這個算法原先只用來處理自然數(shù)和幾何長度（相當(dāng)于正實(shí)數(shù)），但在19世紀(jì)，輾轉(zhuǎn)相除法被推廣至其他類型的數(shù)學(xué)對象，如高斯整數(shù)和一元多項式。由此，引申出歐幾里得整環(huán)等等的一些現(xiàn)代抽象代數(shù)概念。后來，輾轉(zhuǎn)相除法又?jǐn)U展至其他數(shù)學(xué)領(lǐng)域，如紐結(jié)理論和多元多項式。輾轉(zhuǎn)相除法有很多應(yīng)用，它甚至可

12、以用來生成全世界不同文化中的傳統(tǒng)音樂節(jié)奏。在現(xiàn)代密碼學(xué)方面，它是RSA算法（一種在電子商務(wù)中廣泛使用的公鑰加密算法）的重要部分。它還被用來解丟番圖方程，比如尋找滿足中國剩余定理的數(shù)，或者求有限域中元素的逆。輾轉(zhuǎn)相除法還可以用來構(gòu)造連分?jǐn)?shù)，在施圖姆定理和一些整數(shù)分解算法中也有應(yīng)用。輾轉(zhuǎn)相除法是現(xiàn)代數(shù)論中的基本工具。 輾轉(zhuǎn)相除法處理大數(shù)時非常高效，如果用除法而不是減法實(shí)現(xiàn)，它需要的步驟不會超過較小數(shù)的位數(shù)（十進(jìn)制下）的五倍。拉梅于1844年證明了這點(diǎn)，同時這也標(biāo)志著計算復(fù)雜性理論的開端。 輾轉(zhuǎn)相除法是目前仍然在使用的歷史最悠久的算法之一。它首次出現(xiàn)于幾何原本（卷7命題12、卷10命題23）（大約公

13、元前300年）。在卷7中用于整數(shù)，在卷10中用于線段的長度（以現(xiàn)代的觀點(diǎn)看，線段的長度可視為正實(shí)數(shù)，也就是說輾轉(zhuǎn)相除法實(shí)際可用于實(shí)數(shù)上，但是當(dāng)時未有實(shí)數(shù)的概念）。卷10中出現(xiàn)的算法是幾何的，兩段線段a和b的最大公約數(shù)是a和b的公度中的最大值。這個算法可能并非歐幾里得發(fā)明，因為他也有將先前其他數(shù)學(xué)家的一些成果編進(jìn)他的幾何原本。數(shù)學(xué)家、歷史學(xué)家范德瓦爾登（英語：Bartel Leendert van der Waerden）認(rèn)為卷7的內(nèi)容可能來自畢達(dá)哥拉斯學(xué)院出身的數(shù)學(xué)家寫的關(guān)于數(shù)論的教科書。輾轉(zhuǎn)相除法在當(dāng)時很可能已為尤得塞斯（大約公元前375年）所知

14、60;，甚至可能更早之前就已經(jīng)存在，因為歐幾里得和亞里士多德的著作中都出現(xiàn)了一詞（意為“輾轉(zhuǎn)相減”）。幾個世紀(jì)之后，輾轉(zhuǎn)相除法又分別被中國人和印度人獨(dú)立發(fā)現(xiàn)，主要用來解天文學(xué)中用到的丟番圖方程以及制定準(zhǔn)確的歷法。5世紀(jì)末，印度數(shù)學(xué)家、天文學(xué)家阿里亞哈塔曾稱輾轉(zhuǎn)相除法為“粉碎機(jī)”，這可能是因為它在解丟番圖方程時很有效。在中國，九章算術(shù)中提到了一種類似輾轉(zhuǎn)相減法的“更相減損術(shù)”。孫子算經(jīng)中則出現(xiàn)了中國剩余定理的一個特例，但是直到1247年秦九韶才于其數(shù)學(xué)九章中解答了該定理的一般情況，當(dāng)中用到了他發(fā)明的大衍求一術(shù)。此法的其中一部分實(shí)際上便是輾轉(zhuǎn)相除的原理，秦九韶在書中對此有明確表述。在歐洲，輾轉(zhuǎn)相除

15、法首次出現(xiàn)于克勞德·巴希特（英語：Claude Gaspard Bachet de Méziriac）的著作愉悅討喜的問題（Problèmes plaisants et délectables）的第二版在歐洲，輾轉(zhuǎn)相除法被用于丟番圖方程和構(gòu)建連分?jǐn)?shù)。后來，英國數(shù)學(xué)家桑德森（英語：Nicholas Saunderson）在其著作中收編了擴(kuò)展歐幾里得算法，作為一個有效計算連分?jǐn)?shù)的方法。他將此法的來源歸名于羅杰·科茨（英語：Roger Cotes）。 19世紀(jì)，

16、輾轉(zhuǎn)相除法促成了新數(shù)系的建立，如高斯整數(shù)和艾森斯坦整數(shù)。1815年，高斯用輾轉(zhuǎn)相除法證明高斯整數(shù)的分解是惟一的，盡管他的研究到了1832年才首度發(fā)表。高斯在他的算數(shù)研究（出版于1801年）中實(shí)際上也有援引這個算法，但僅是以連分?jǐn)?shù)方法的形式敘述。約翰·狄利克雷是第一個將輾轉(zhuǎn)相除法作為數(shù)論的基礎(chǔ)的數(shù)學(xué)家。來源請求狄利克雷提出，數(shù)論中的很多結(jié)論，如分解的惟一性，在任何使輾轉(zhuǎn)相除法適用的數(shù)系中均有效。狄利克雷的數(shù)論講義后來經(jīng)理查德·戴德金編輯和推廣，戴德金也有以輾轉(zhuǎn)相除法來研究代數(shù)整數(shù)。比如，他是第一個用高斯整數(shù)的分解惟一性證明費(fèi)馬平方和定理的數(shù)學(xué)家。戴德金還率先定義了歐幾里得整環(huán)

17、的概念。19世紀(jì)末，戴德金所定義的理想概念使得數(shù)論的重心不必建基于輾轉(zhuǎn)相除法，從而促進(jìn)了理論的發(fā)展。 輾轉(zhuǎn)相除法的其他應(yīng)用發(fā)展于19世紀(jì)。1829年，施圖姆將輾轉(zhuǎn)相除法用于施圖姆序列（用于確定多項式的不同實(shí)根的個數(shù)的方法）。輾轉(zhuǎn)相除法是歷史上第一個整數(shù)關(guān)系算法（英語：integer relation algorithm），即尋找兩個可通約實(shí)數(shù)的整數(shù)關(guān)系的算法。近年來，出現(xiàn)了一些新穎的整數(shù)關(guān)系算法，如埃拉曼·弗格森（英語：Helaman Ferguson）和福爾卡德于1979年發(fā)表的弗格森-福爾卡德算法（FergusonForcade algor

18、ithm） 、以及與它相關(guān)的LLL算法（英語：LenstraLenstraLovász lattice basis reduction algorithm）、HJLS算法以及PSLQ算法。1969年，科爾（Cole）和戴維（Davie）基于輾轉(zhuǎn)相除法創(chuàng)造了一種二人游戲，叫做“歐幾里得游戲”。這個游戲有最優(yōu)策略。游戲開始于兩列分別為a和b個棋子組成的序列，玩家輪流從較長一列中取走較短一列棋子數(shù)量的m倍的棋子。如果兩列棋子p和q分別由x和y個棋子組成，其中x大于y，那么玩家可以將序列p的棋子數(shù)量減少為自然數(shù)x  my。

19、最后率先將一列棋子清空的玩家勝出。 1.2 課題意義帶余除法，數(shù)學(xué)術(shù)語，廣泛應(yīng)用于數(shù)學(xué)之中。輾轉(zhuǎn)相除法的基本步驟就是帶余除法，輾轉(zhuǎn)相除法又稱歐幾里得算法。帶余除法是小學(xué)到大學(xué)一直沿用的轉(zhuǎn)化方法，也是研究整數(shù)與多項式的一個基本方法，在有關(guān)整數(shù)和多項式的其他問題中還有更廣泛的應(yīng)用，雖然它的內(nèi)容簡單，但它里面蘊(yùn)含的意義卻很深刻，只有對它的意思徹底了解，才能引申出在不同場合下的用法，在高中的數(shù)學(xué)學(xué)習(xí)中，許多知識點(diǎn)都會用到帶余除法，掌握了帶余除法，就多了種解決問題的方法，也是多了條通往成功的途徑。第二章 整數(shù)的帶余除法整除是初等數(shù)論這一科目的基礎(chǔ)概念，而帶余數(shù)除法是所有除法的一般形式，所以深度了解這種理

20、論的該念、性質(zhì)和應(yīng)用是十分必要的。接下來我會通過整數(shù)的帶余除法來淺談帶余除法在數(shù)論這一科目的重要性，使我們能掌握帶余除法的精華，有助于以后的解題。2.1 整數(shù)帶余除法的解釋及證明對任意整數(shù)a，b且b0，存在唯一的數(shù)對q，r，使a=bq+r，其中0r|b|。這個事實(shí)稱為帶余除法定理，是整除理論的基礎(chǔ)。若c|a，c|b，則稱c是a，b的公因數(shù)。若d是a，b的公因數(shù)，d0，且d可被a，b的任意公因數(shù)整除，則稱d是a，b的最大公因數(shù)。若a，b的最大公因數(shù)等于1，則稱a，b互素。累次利用帶余除法可以求出a，b的最大公因數(shù)，這種方法常稱為輾轉(zhuǎn)相除法。又稱歐幾里得算法。 【存在性】設(shè)集合S=，a-3b，a-

21、2b，a-b，0，a+b，a+2b，a+3b，=a+bk: k是整數(shù)記T為S和自然數(shù)集的交集，T非空，由自然數(shù)集的良序性，知T中有一最小元素t。設(shè)t=a-bq，q為整數(shù)。則a-bq0。現(xiàn)假設(shè)a-bq|b|，但這樣便有a-b(q±1)0成立（b為正數(shù)時取加號，負(fù)數(shù)時取減號），且a-b(q±1)a-bq。這違反了t是最小元素這一事實(shí)，於是a-bq<|b|。令r=a-qb，即證存在性?！疚ㄒ恍浴吭O(shè)q1、r1是滿足a=bq+r，0r<|b|的另一對整數(shù)，因為bq1+r1=bq+r，于是b(q-q1)=r1-r故|b|q-q1|=|r1-r|由于r及r1都是小于

22、b的非負(fù)整數(shù)，所以上式右邊是小于|b|的。如果qq1，則上式左邊|b|，這是不可能的。所以q=q1， r=r1，即證唯一性。 2.2 整數(shù)帶余除法的一些性質(zhì)() b½a Û ±b ½±a；() c ½b，b½a Þ c½a；() b½ai，i = 1, 2, , n Þ b½a1q1 + a2q2 + + anqn，此處qi（i = 1, 2, L, n）是任意的整數(shù)；() b½a Þ bc½ac，此處c是任意的非零整數(shù)；() b

23、89;a，a ¹ 0 Þ|b|£|a|；b½a且|a|<|b|Þ a = 0。2.3最大公約數(shù)與輾轉(zhuǎn)相除法一、有關(guān)概念 1、公因數(shù)及個數(shù)，總和； 2、最大公約數(shù)； 3、互質(zhì)數(shù)； 4、兩兩互質(zhì)；二、輾轉(zhuǎn)相除法 定理1：設(shè)a，b，c是不全為0的整數(shù)，且a=bq+c，q為整數(shù) 則（1）a，b與b，c有相同的公因數(shù)； （2）(a，b)=(b，c) 定理2：設(shè)為正整數(shù)，則 推論：的公因數(shù)與的因數(shù)相同。三、最大公因數(shù)的性質(zhì) 1、為正整數(shù)2、為的公因數(shù)3、4、設(shè)， ， 則2.4 整除的進(jìn)一步性質(zhì)與最小公倍數(shù)一、整除的進(jìn)一步性質(zhì)定理1：設(shè)為任意的正整數(shù)，

24、則 其中， 推論：設(shè)為任意兩個不全為0的整數(shù)，則存在兩個整數(shù)使得 成立，反之不成立。例如 有定理2： 存在整數(shù)使得推論1：設(shè)為整數(shù)，且，則 （1）與有相同的公因數(shù)； （2）推論2：若，且則推論3：若是兩組任意的整數(shù)，且， 則（）=1二、最小公倍數(shù)1、定義： 2、說明： ； ； 關(guān)系：公倍數(shù)與最小公倍數(shù)的關(guān)系； 最小公倍數(shù)與最大公因數(shù)的關(guān)系； 例如 1 當(dāng)時，則 2 若都是正整數(shù)，且，則 3 ， 4 若，則3、多個整數(shù)的最小公倍數(shù)的求法如何？ ， ， 則第三章 多項式的帶余除法 帶余除法是高等代數(shù)最基本的概念之一，通過查找相關(guān)資料了解到整數(shù)和一元多項式的帶余除法有著相同的思想。即在進(jìn)行整數(shù)和多項

25、式的除法運(yùn)算是少不了要使用輾轉(zhuǎn)相除法，而輾轉(zhuǎn)相除法的基本步驟就是帶余除法。本章將討論多項式帶余除法定理的證明和應(yīng)用,因為多項式的帶余除法是整數(shù)帶余除法的推廣，所以多項式的帶余除法中將涉及輾轉(zhuǎn)相除法的介紹，整除的基本概念與基本性質(zhì)、最大公因式、公共根、重根以及一元多項式矩陣的相關(guān)性質(zhì)。3.1多項式帶余除法的定理及其證明（見文1）定理：則存在唯一的，使其中或。我們稱和分別為用去除所得的商和余式。證明：存在性 設(shè)如果，則取即可。下面假定。對的次數(shù)做數(shù)學(xué)歸納法：如果=0或，則令即滿足要求。設(shè)，命題正確，則當(dāng)時，有（這里），令若，則取。否則，因，按歸納假設(shè)，存在，使得這里或。現(xiàn)令則顯然有唯一性 設(shè)也滿足

26、命題要求，那么比較兩邊的次數(shù)，即可知3.2 帶余除法的二種計算格式（見文2）用多項式除多項式所得的商和余式可以通過如下兩種格式進(jìn)行3.2.1 普通除法（長除法） 3.2.2 豎式除法 或 3.2.3 綜合除法第四章 帶余除法在解題中的應(yīng)用4.1 有關(guān)兩個多項式除法與整除關(guān)系問題例1、用除，求商與余式 解：所以 （見文3）例2、如果,求a,b.解：令 = =， 因為，則0即 解得4.2 輾轉(zhuǎn)相除法是帶余除法的特殊應(yīng)用 （見文1）給定，做帶余除法：不難得。現(xiàn)在做輾轉(zhuǎn)相除法如下：因，故必有而，即，于是=（使為首一多項式）。這就把求出來了4.2.1 輾轉(zhuǎn)相除法計算兩個多項式的最大公因式及它們與最大公因

27、式的組合關(guān)系例3、已知，求與的最大公因式解：因為所以 例4、：，解：因為 所以 再由 解得 于是 4.2.2 求兩個多項式的公共根定理:用輾轉(zhuǎn)相除法計算兩個多項式的最大公因式，在求其公因式的根例5、求下列多項式的公共根，解：由輾轉(zhuǎn)相除法，可求得所以它們的公共根為34.2.3 解有關(guān)多項式的重根，重因式問題定理：輾轉(zhuǎn)相除法求得與的最大公因式，觀察最大公因式，即可得出答案例6、判斷多項式有無重因式3解： 用輾轉(zhuǎn)相除法求得： 所以由的三重因式4.3 求函數(shù)值f(a)定理：用帶帶余除法求得，為常數(shù)，則f(a)= . 若，則例7、若，求解：用帶余除法 所以=327例8、已知是方程的一個根，解此方程。解：

28、由于實(shí)系數(shù)方程的復(fù)根市成對出現(xiàn)，是方程的根，從而也是他的一個根，故多項式可被整除，用去除得商，它的根為，故原方程的四個根為4.4 解有關(guān)有理數(shù)域上的因式分解及有理根設(shè)是一個整系數(shù)多形式，而是它的一個有理根，其中互素，則必有。特別地，如果的首項系數(shù)，則的有理根都是整數(shù)根，而且是的因子。例9、求多項式的有理根解：由于是首項系數(shù)為1的整系數(shù)多項式，如果有有理根，必為整數(shù)根，且為常數(shù)項-14的因數(shù)為： 由帶余除法可得：所以在有理數(shù)域上只有2是它的根。例10：多項式在有理數(shù)域上是否可約？解：常數(shù)項1的因式為： 由帶余除法可得： 所以其在有理數(shù)域上不可約4.5 帶余除法在矩陣多項式中的應(yīng)用4,5.1 關(guān)于

29、矩陣多形式可逆的判定在關(guān)于矩陣多項式可逆判別中，這里提出了用多項式的帶余除法來解決：“已知，證明可逆且求其逆”這一類問題得方法.定理：用除，若，其中是次數(shù)低于的一個非零多項式，則用除，如此下去，求出與的最大公因式；若，則有多項式使，由于，從而有，故可逆，且例11、設(shè)n階矩陣A滿足，證明：可逆，并求其逆。 證明：設(shè)則由帶余除法： 得： 由定義，可逆且 例12、設(shè)，已知，證明可逆且求的逆。 證明：由帶余除法有： （1） (2) 由（1）式，代入（2）式，整理得： 又， 可逆，且4.5.2 有關(guān)矩陣最小多項式的問題（見文3）例13、設(shè)是方陣A的最小多項式。若是A的零化多項式（即），則整除 證：用去除，可設(shè) 其中，以A代上式，得 于是，即整除例14、設(shè)是對角塊矩陣，是子方陣，證明A的最小多項式等