【正文】 ......................................................... 17 求函數(shù)值 f(a) .................................................................................................. 17 解有關(guān)有理數(shù)域上的因式分解及有理根 ............................................................ 18 帶余除法在矩陣多項(xiàng)式中的 應(yīng)用 ....................................................................... 19 4, 關(guān)于矩陣多形式可逆的判定 ................................................................... 19 有關(guān)矩陣最小多項(xiàng)式的問題 ................................................................... 20 參考文獻(xiàn) ........................................................................................................................ 22 致 謝 ........................................................................................................................... 23 第一章 前言 研究 背景 帶余除法（也稱為歐幾里德除法）是數(shù)學(xué)中的一種基本算術(shù)計(jì)算方式。 本文 的正文是介紹整數(shù)和多項(xiàng)式的帶余除法，從這二個(gè)層面可以認(rèn)識到帶余除法是一種普遍應(yīng)用于生活中的思想。 學(xué)校代碼 : 11059 學(xué) 號 :1107011032 Hefei University 畢業(yè)論文（設(shè)計(jì)） B A C HE L OR D I SSE RTAT I ON 論文題目 : 帶余除法及其應(yīng)用研究 學(xué)位類別 : 理學(xué)學(xué)士 學(xué)科專業(yè) : 信息與計(jì)算科學(xué) 作者姓名 : 孟飛飛 導(dǎo)師姓名 : 余海峰 完成時(shí)間 : 2021年 05 月 03日 帶余除法及其應(yīng)用研究 摘要 本文 的主旨思想是 帶余除法的簡單介紹以及 帶余除法在日常生活中的應(yīng)用，整片論文都圍繞帶余除法來展開論述， 先是介紹帶余除法的來源及課題意義，然后通過整數(shù)的帶余除法和多項(xiàng)式的帶余除法讓大家對帶余除法的應(yīng)用有一個(gè)更深的認(rèn)識。 最后通過實(shí)例來展現(xiàn)其在應(yīng)用研究中所起到的作用。 可以這樣說多項(xiàng)式的帶余除法是整數(shù)帶余除法的推廣，所以有必要對整數(shù)帶余除法進(jìn)行介紹，多項(xiàng)式的帶余除法中將涉及輾轉(zhuǎn)相除法的介紹， 整除的基本概念與基本性質(zhì)、最大公因式、公共根、重根以及一元多項(xiàng)式矩陣的相關(guān)性質(zhì)。給定一個(gè)被除數(shù) a 和一個(gè)除數(shù) b，帶余除法給出一個(gè)整數(shù) q 和一個(gè)介于一定范圍的余數(shù) r，使得該等式成立： a = bq + r。這樣的限定都是為了使得滿 足等式的 q 有且僅有一個(gè)。帶余除法一般表示為： a / b=q … r 。最常見的帶余除法是整數(shù)與整數(shù)的帶余除法（被除數(shù) a 和除數(shù) b 都是整數(shù)），但實(shí)數(shù)與整數(shù)乃至實(shí)數(shù)與實(shí)數(shù)的帶余除法也有應(yīng)用。如果余數(shù)為零，則稱 b 整除 a。最常用的是長除法（豎式除法）。 在數(shù)學(xué)中，輾轉(zhuǎn)相除法，又稱歐幾里得算法，是求最大公約數(shù)的算法。 兩個(gè)整數(shù)的最大公約數(shù)是能夠同時(shí)整除它們的最大的正整數(shù)。例如， 252 和 105 的最大公約數(shù)是 21（ 252=2112； 105=215）；因?yàn)?52?105=21 (12?5) =147，所以 147 和 105 的最大公約數(shù)也是 21。這時(shí)，所剩下的還沒有變成零的數(shù)就是兩數(shù)的最大公約數(shù)。這個(gè)重要的結(jié)論叫做裴蜀定理。這個(gè)算法原先只用來處理自然數(shù)和幾何長度（相當(dāng)于正實(shí)數(shù)），但在 19 世紀(jì)，輾轉(zhuǎn)相除法被推廣至其他類型的數(shù)學(xué)對象，如高斯整數(shù)和一元多項(xiàng)式。后來，輾轉(zhuǎn)相除法又?jǐn)U展至其他數(shù)學(xué)領(lǐng)域，如紐結(jié)理論和多元多項(xiàng)式。在現(xiàn)代密碼學(xué)方面，它是 RSA 算法（一種在電子商務(wù)中廣泛使用的公鑰加密算法）的重要部分。輾轉(zhuǎn)相除法還可以用來構(gòu)造連分?jǐn)?shù)，在施圖姆定理和一些整數(shù)分解算法中也有應(yīng)用。 輾轉(zhuǎn)相除法處理大數(shù)時(shí)非常高效，如果用除法而不是減法 實(shí)現(xiàn)，它需要的步驟不會超過較小數(shù)的位數(shù)（十進(jìn)制下）的五倍。 輾轉(zhuǎn)相除法是目前仍然在使用的歷史最悠久的算法之一。在卷 7 中用于整數(shù)，在卷 10 中用于線段的長度（以現(xiàn)代的觀點(diǎn)看，線段的長度可視為正實(shí)數(shù)，也就是說輾轉(zhuǎn)相除法實(shí)際可用于實(shí)數(shù)上，但是當(dāng)時(shí)未有實(shí)數(shù)的概念）。 這個(gè)算法可能并非歐幾里得 發(fā)明，因?yàn)樗灿袑⑾惹捌渌麛?shù)學(xué)家的一些成果編進(jìn)他的《幾何原本》。輾轉(zhuǎn)相除法在當(dāng)時(shí)很可能已為尤得塞斯（大約公元前 375 年）所知 ，甚至可能更早之前就已經(jīng)存在，因?yàn)闅W幾里得和亞里士多德的著作中都出現(xiàn)了 ?νθσφα?ρεσι?一詞（意為 “輾轉(zhuǎn)相減 ”）。 5 世紀(jì)末，印度數(shù)學(xué)家、天文學(xué)家阿里亞哈塔曾稱輾轉(zhuǎn)相除法為 “粉碎機(jī) ”，這可能是因?yàn)樗诮鈦G番圖方程時(shí)很有效?！秾O子算經(jīng)》中則出現(xiàn)了中國剩余定理的一個(gè)特例，但是直到 1247 年秦九韶才于其《數(shù)學(xué)九章》中解答了該定理的一般情況，當(dāng)中用到了他發(fā)明的大衍求一術(shù)。在歐洲，輾轉(zhuǎn)相除法首次出現(xiàn)于克勞德 ziriac）的著作《愉悅討喜的問題》（ Probl232。lectables）的第二版在歐洲，輾轉(zhuǎn)相除法被用于丟番圖方程和構(gòu)建連分?jǐn)?shù)。他將此法的來源歸名于羅杰 19 世紀(jì)，輾轉(zhuǎn)相除法促成了新數(shù)系的建立，如高斯整數(shù)和艾森斯坦整數(shù)。高斯在他的《算數(shù)研究》（出版于 1801 年）中實(shí)際上也有援引這個(gè)算法，但僅是以連分?jǐn)?shù)方法的形式敘述。狄利克雷是第一個(gè)將輾轉(zhuǎn)相除法作為數(shù)論的基礎(chǔ)的數(shù)學(xué)家。狄利克雷的數(shù)論講義后來經(jīng)理查德 比如，他是第一個(gè)用高斯整數(shù)的分解惟一性證明費(fèi)馬平方和定理的數(shù)學(xué)家。 19 世紀(jì)末，戴德金所定義的理想概念使得數(shù)論的重心不必建基于輾 轉(zhuǎn)相除法，從而促進(jìn)了理論的發(fā)展。 1829 年，施圖姆將輾轉(zhuǎn)相除法用于施圖姆序列（用于確定多項(xiàng)式的不同實(shí)根的個(gè)數(shù)的方法）。近年來，出現(xiàn)了一些新穎的整數(shù)關(guān)系算法，如埃拉曼 sz lattice basis reduction algorithm）、 HJLS 算法以及 PSLQ 算法。這個(gè)游戲有最優(yōu)策略。如果兩列棋子 p 和 q 分別由 x 和 y 個(gè)棋子組成，其中 x 大于 y，那么玩家可以將序列 p 的棋子數(shù)量減少為自然數(shù) x ? my。 課題意義 帶余除法，數(shù)學(xué)術(shù)語，廣泛應(yīng)用于數(shù)學(xué)之中。 帶余除法是小學(xué)到大學(xué)一直沿用的轉(zhuǎn)化方法，也是研究 整數(shù)與 多項(xiàng)式的一個(gè)基本方法，在有關(guān) 整數(shù)和 多項(xiàng)式的其他問題中還有更廣泛的應(yīng)用，雖然它的內(nèi)容簡單，但它里面蘊(yùn)含的意義卻很深刻，只有對它的意思徹底了解，才能引申出在不同場合下的用法，在高中的數(shù)學(xué)學(xué)習(xí)中，許多知識點(diǎn)都會用到帶余除法，掌握了帶余除法，就多了種解決問題的方法，也是多了條通往成功的途徑。接 下來 我會 通過整數(shù)的帶余除法來淺談帶余除法在數(shù)論這一科目的重要性， 使我們能掌握 帶余除法的精華 ，有助于以后的解題。這個(gè)事實(shí)稱為帶余除法定理，是整除理論的基礎(chǔ)。若 d 是 a， b 的公因數(shù)， d≥0，且 d 可被 a， b 的任意 公因數(shù)整除，則稱 d是 a， b 的最大公因數(shù)。累次利用帶余除法可以求出 a， b 的最大公因數(shù)，這種方法常稱為輾轉(zhuǎn)相除法。 【存在性】設(shè)集合 S={… ， a3b， a2b， ab， 0， a+b， a+2b， a+3b， …}={a+bk: k是整數(shù) }記 T 為 S 和自然數(shù)集的交集， T 非空，由自然數(shù)集的良序性，知 T 中有一最小元素 t。則 abq≥0。1)≥0成立（ b 為正數(shù)時(shí)取加號，負(fù)數(shù)時(shí)取減號），且 ab(q177。這違反了 t 是最小元素這一事實(shí)，於是 abq|b|。 【唯一性】設(shè) q r1 是滿足 a=bq+r， 0≤r|b|的另一對整數(shù)，因?yàn)?bq1+r1=bq+r，于是 b(qq1)=r1r 故 |b||qq1|=|r1r|由于 r 及 r1 都是小于 b 的非負(fù)整數(shù)，所以上式右邊是小于 |b|的。所以 q=q1， r=r1，即證唯一性。 一、有關(guān)概念 公因數(shù)及個(gè)數(shù)，總和； 最大公約數(shù)； 互質(zhì)數(shù)； 兩兩互質(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è) ,ab為正整數(shù)，則 ? ?, nab r? 推論： ,ab的公因數(shù)與 ? ?,a