毕业论文-带余除法及其应用研究.doc

学校代码: 11059 学 号:1107011032 Hefei University 毕业论文（设计）BACHELOR DISSERTATION 论文题目: 带余除法及其应用研究 学位类别: 理学学士 学科专业: 信息与计算科学 作者姓名: 孟飞飞 导师姓名: 余海峰 完成时间: 2015年05月03日 带余除法及其应用研究摘要本文的主旨思想是带余除法的简单介绍以及带余除法在日常生活中的应用，整片论文都围绕带余除法来展开论述，先是介绍带余除法的来源及课题意义，然后通过整数的带余除法和多项式的带余除法让大家对带余除法的应用有一个更深的认识。最后通过实例来展现其在应用研究中所起到的作用。本文的正文是介绍整数和多项式的带余除法，从这二个层面可以认识到带余除法是一种普遍应用于生活中的思想。可以这样说多项式的带余除法是整数带余除法的推广，所以有必要对整数带余除法进行介绍，多项式的带余除法中将涉及辗转相除法的介绍，整除的基本概念与基本性质、最大公因式、公共根、重根以及一元多项式矩阵的相关性质。下面就开始进入本文的正题吧!关键词：一元多项式 带余除法 辗转相除法 最大公因式 一元多项式矩阵With more than division and its application researchabstractPurpose of this article is more than 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 division 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 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 involve 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 The greatest common factor is one yuan polynomial matrix目录第一章 前言51.1 研究背景51.2 课题意义7第二章 整数的带余除法82.1 整数带余除法的解释及证明82.2 整数带余除法的一些性质92.3最大公约数与辗转相除法92.4 整除的进一步性质与最小公倍数10第三章多项式的带余除法123.1多项式带余除法的定理及其证明123.2 带余除法的二种计算格式133.2.1 普通除法（长除法）133.2.2 竖式除法133.2.3 综合除法14第四章 带余除法在解题中的应用154.1 有关两个多项式除法与整除关系问题154.2 辗转相除法是带余除法的特殊应用164.2.1 辗转相除法计算两个多项式的最大公因式及它们与最大公因式的组合关系164.2.2 求两个多项式的公共根184.2.3 解有关多项式的重根，重因式问题184.3 求函数值f(a)184.4 解有关有理数域上的因式分解及有理根194.5 带余除法在矩阵多项式中的应用204,5.1 关于矩阵多形式可逆的判定204.5.2 有关矩阵最小多项式的问题21参考文献23致 谢24第一章 前言1.1 研究背景 带余除法（也称为欧几里德除法）是数学中的一种基本算术计算方式。给定一个被除数a和一个除数b，带余除法给出一个整数q和一个介于一定范围的余数r，使得该等式成立：a = bq + r。一般限定余数的范围在0与b之间，也有限定在-b/2与b/2之间。这样的限定都是为了使得满足等式的q有且仅有一个。这时候的q称为带余除法的商。带余除法一般表示为：a / b=q r 。表达为：“a除以b等于q，余r”。最常见的带余除法是整数与整数的带余除法（被除数a和除数b都是整数），但实数与整数乃至实数与实数的带余除法也有应用。对一般的抽象代数系统，能够进行带余除法的都是具有欧几里德性质的系统。如果余数为零，则称b整除a。一般约定除数b不能为0.带余除法的计算有长久的历史，有各种计算工具和计算方法。最常用的是长除法（竖式除法）。带余除法在数论中有不少用途，比如说辗转相除法的基本步骤就是带余除法。 在数学中，辗转相除法，又称欧几里得算法，是求最大公约数的算法。辗转相除法首次出现于欧几里得的几何原本（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的九章算术。两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（252=2112；105=215）；因为252105=21 (125) =147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如21=5105+ (2)252。这个重要的结论叫做裴蜀定理。辗转相除法最早出现在欧几里得的几何原本中（大约公元前300年），所以它是现行的算法中历史最悠久的。这个算法原先只用来处理自然数和几何长度（相当于正实数），但在19世纪，辗转相除法被推广至其他类型的数学对象，如高斯整数和一元多项式。由此，引申出欧几里得整环等等的一些现代抽象代数概念。后来，辗转相除法又扩展至其他数学领域，如纽结理论和多元多项式。辗转相除法有很多应用，它甚至可以用来生成全世界不同文化中的传统音乐节奏。在现代密码学方面，它是RSA算法（一种在电子商务中广泛使用的公钥加密算法）的重要部分。它还被用来解丢番图方程，比如寻找满足中国剩余定理的数，或者求有限域中元素的逆。辗转相除法还可以用来构造连分数，在施图姆定理和一些整数分解算法中也有应用。辗转相除法是现代数论中的基本工具。 辗转相除法处理大数时非常高效，如果用除法而不是减法实现，它需要的步骤不会超过较小数的位数（十进制下）的五倍。拉梅于1844年证明了这点，同时这也标志着计算复杂性理论的开端。 辗转相除法是目前仍然在使用的历史最悠久的算法之一。它首次出现于几何原本（卷7命题12、卷10命题23）（大约公元前300年）。在卷7中用于整数，在卷10中用于线段的长度（以现代的观点看，线段的长度可视为正实数，也就是说辗转相除法实际可用于实数上，但是当时未有实数的概念）。卷10中出现的算法是几何的，两段线段a和b的最大公约数是a和b的公度中的最大值。这个算法可能并非欧几里得发明，因为他也有将先前其他数学家的一些成果编进他的几何原本。数学家、历史学家范德瓦尔登（英语：BartelLeendertvanderWaerden）认为卷7的内容可能来自毕达哥拉斯学院出身的数学家写的关于数论的教科书。辗转相除法在当时很可能已为尤得塞斯（大约公元前375年）所知，甚至可能更早之前就已经存在，因为欧几里得和亚里士多德的著作中都出现了一词（意为“辗转相减”）。几个世纪之后，辗转相除法又分别被中国人和印度人独立发现，主要用来解天文学中用到的丢番图方程以及制定准确的历法。5世纪末，印度数学家、天文学家阿里亚哈塔曾称辗转相除法为“粉碎机”，这可能是因为它在解丢番图方程时很有效。在中国，九章算术中提到了一种类似辗转相减法的“更相减损术”。孙子算经中则出现了中国剩余定理的一个特例，但是直到1247年秦九韶才于其数学九章中解答了该定理的一般情况，当中用到了他发明的大衍求一术。此法的其中一部分实际上便是辗转相除的原理，秦九韶在书中对此有明确表述。在欧洲，辗转相除法首次出现于克劳德巴希特（英语：ClaudeGaspardBachetdeMziriac）的著作愉悦讨喜的问题（Problmesplaisantsetdlectables）的第二版在欧洲，辗转相除法被用于丢番图方程和构建连分数。后来，英国数学家桑德森（英语：NicholasSaunderson）在其著作中收编了扩展欧几里得算法，作为一个有效计算连分数的方法。他将此法的来源归名于罗杰科茨（英语：RogerCotes）。 19世纪，辗转相除法促成了新数系的建立，如高斯整数和艾森斯坦整数。1815年，高斯用辗转相除法证明高斯整数的分解是惟一的，尽管他的研究到了1832年才首度发表。高斯在他的算数研究（出版于1801年）中实际上也有援引这个算法，但仅是以连分数方法的形式叙述。约翰狄利克雷是第一个将辗转相除法作为数论的基础的数学家。来源请求狄利克雷提出，数论中的很多结论，如分解的惟一性，在任何使辗转相除法适用的数系中均有效。狄利克雷的数论讲义后来经理查德戴德金编辑和推广，戴德金也有以辗转相除法来研究代数整数。比如，他是第一个用高斯整数的分解惟一性证明费马平方和定理的数学家。戴德金还率先定义了欧几里得整环的概念。19世纪末，戴德金所定义的理想概念使得数论的重心不必建基于辗转相除法，从而促进了理论的发展。 辗转相除法的其他应用发展于19世纪。1829年，施图姆将辗转相除法用于施图姆序列（用于确定多项式的不同实根的个数的方法）。辗转相除法是历史上第一个整数关系算法（英语：integerrelationalgorithm），即寻找两个可通约实数的整数关系的算法。近年来，出现了一些新颖的整数关系算法，如埃拉曼弗格森（英语：HelamanFerguson）和福尔卡德于1979年发表的弗格森-福尔卡德算法（FergusonForcadealgorithm）、以及与它相关的LLL算法（英语：LenstraLenstraLovszlatticebasisreductionalgorithm）、HJLS算法以及PSLQ算法。1969年，科尔（Cole）和戴维（Davie）基于辗转相除法创造了一种二人游戏，叫做“欧几里得游戏”。这个游戏有最优策略。游戏开始于两列分别为a和b个棋子组成的序列，玩家轮流从较长一列中取走较短一列棋子数量的m倍的棋子。如果两列棋子p和q分别由x和y个棋子组成，其中x大于y，那么玩家可以将序列p的棋子数量减少为自然数xmy。最后率先将一列棋子清空的玩家胜出。 1.2 课题意义带余除法，数学术语，广泛应用于数学之中。辗转相除法的基本步骤就是带余除法，辗转相除法又称欧几里得算法。带余除法是小学到大学一直沿用的转化方法，也是研究整数与多项式的一个基本方法，在有关整数和多项式的其他问题中还有更广泛的应用，虽然它的内容简单，但它里面蕴含的意义却很深刻，只有对它的意思彻底了解，才能引申出在不同场合下的用法，在高中的数学学习中，许多知识点都会用到带余除法，掌握了带余除法，就多了种解决问题的方法，也是多了条通往成功的途径。第二章 整数的带余除法整除是初等数论这一科目的基础概念，而带余数除法是所有除法的一般形式，所以深度了解这种理论的该念、性质和应用是十分必要的。接下来我会通过整数的带余除法来浅谈带余除法在数论这一科目的重要性，使我们能掌握带余除法的精华，有助于以后的解题。2.1 整数带余除法的解释及证明对任意整数a，b且b0，存在唯一的数对q，r，使a=bq+r，其中0r|b|。这个事实称为带余除法定理，是整除理论的基础。若c|a，c|b，则称c是a，b的公因数。若d是a，b的公因数，d0，且d可被a，b的任意公因数整除，则称d是a，b的最大公因数。若a，b的最大公因数等于1，则称a，b互素。累次利用带余除法可以求出a，b的最大公因数，这种方法常称为辗转相除法。又称欧几里得算法。 【存在性】设集合S=，a-3b，a-2b，a-b，0，a+b，a+2b，a+3b，=a+bk:k是整数记T为S和自然数集的交集，T非空，由自然数集的良序性，知T中有一最小元素t。设t=a-bq，q为整数。则a-bq0。现假设a-bq|b|，但这样便有a-b(q1)0成立（b为正数时取加号，负数时取减号），且a-b(q1)a-bq。这违反了t是最小元素这一事实，於是a-bq|b|。令r=a-qb，即证存在性。【唯一性】设q1、r1是满足a=bq+r，0r|b|的另一对整数，因为bq1+r1=bq+r，于是b(q-q1)=r1-r故|b|q-q1|=|r1-r|由于r及r1都是小于b的非负整数，所以上式右边是小于|b|的。如果qq1，则上式左边|b|，这是不可能的。所以q=q1，r=r1，即证唯一性。 2.2 整数带余除法的一些性质() ba b a；() c b，ba ca；() bai，i = 1, 2, , n ba1q1 + a2q2 + + anqn，此处qi（i = 1, 2, L, n）是任意的整数；() ba bcac，此处c是任意的非零整数；() ba，a 0 |b|a|；ba且|a|b| a = 0。2.3最大公约数与辗转相除法一、有关概念 1、公因数及个数，总和； 2、最大公约数； 3、互质数； 4、两两互质；二、辗转相除法 定理1：设a，b，c是不全为0的整数，且a=bq+c，q为整数 则（1）a，b与b，c有相同的公因数； （2）(a，b)=(b，c) 定理2：设为正整数，则 推论：的公因数与的因数相同。三、最大公因数的性质 1、为正整数2、为的公因数3、4、设， ， 则2.4 整除的进一步性质与最小公倍数一、整除的进一步性质定理1：设为任意的正整数，则 其中， 推论：设为任意两个不全为0的整数，则存在两个整数使得 成立，反之不成立。例如 有定理2： 存在整数使得推论1：设为整数，且，则 （1）与有相同的公因数； （2）推论2：若，且则推论3：若是两组任意的整数，且， 则（）=1二、最小公倍数1、定义： 2、说明： ； ； 关系：公倍数与最小公倍数的关系； 最小公倍数与最大公因数的关系； 例如 1 当时，则 2 若都是正整数，且，则 3 ， 4 若，则3、多个整数的最小公倍数的求法如何？ ， ， 则第三章 多项式的带余除法 带余除法是高等代数最基本的概念之一，通过查找相关资料了解到整数和一元多项式的带余除法有着相同的思想。即在进行整数和多项式的除法运算是少不了要使用辗转相除法，而辗转相除法的基本步骤就是带余除法。本章将讨论多项式带余除法定理的证明和应用,因为多项式的带余除法是整数带余除法的推广，所以多项式的带余除法中将涉及辗转相除法的介绍，整除的基本概念与基本性质、最大公因式、公共根、重根以及一元多项式矩阵的相关性质。3.1多项式带余除法的定理及其证明（见文1）定理：则存在唯一的，使其中或。我们称和分别为用去除所得的商和余式。证明：存在性 设如果，则取即可。下面假定。对的次数做数学归纳法：如果=0或，则令即满足要求。设，命题正确，则当时，有（这里），令若，则取。否则，因，按归纳假设，存在，使得这里或。现令则显然有唯一性 设也满足命题要求，那么比较两边的次数，即可知3.2 带余除法的二种计算格式（见文2）用多项式除多项式所得的商和余式可以通过如下两种格式进行3.2.1 普通除法（长除法） 3.2.2 竖式除法 或 3.2.3 综合除法第四章 带余除法在解题中的应用4.1 有关两个多项式除法与整除关系问题例1、用除，求商与余式 解：所以 （见文3）例2、如果,求a,b.解：令 = =， 因为，则0即 解得4.2 辗转相除法是带余除法的特殊应用 （见文1）给定，做带余除法：不难得。现在做辗转相除法如下：因，故必有而，即，于是=（使为首一多项式）。这就把求出来了4.2.1 辗转相除法计算两个多项式的最大公因式及它们与最大公因式的组合关系例3、已知，求与的最大公因式解：因为所以 例4、：，解：因为 所以 再由 解得 于是 4.2.2 求两个多项式的公共根定理:用辗转相除法计算两个多项式的最大公因式，在求其公因式的根例5、求下列多项式的公共根，解：由辗转相除法，可求得所以它们的公共根为34.2.3 解有关多项式的重根，重因式问题定理：辗转相除法求得与的最大公因式，观察最大公因式，即可得出答案例6、判断多项式有无重因式3解： 用辗转相除法求得： 所以由的三重因式4.3 求函数值f(a)定理：用带带余除法求得，为常数，则f(a)= . 若，则例7、若，求解：用带余除法 所以=327例8、已知是方程的一个根，解此方程。解：由于实系数方程的复根市成对出现，是方程的根，从而也是他的一个根，故多项式可被整除，用去除得商，它的根为，故原方程的四个根为4.4 解有关有理数域上的因式分解及有理根设是一个整系数多形式，而是它的一个有理根，其中互素，则必有。特别地，如果的首项系数，则的有理根都是整数根，而且是的因子。例9、求多项式的有理根解：由于是首项系数为1的整系数多项式，如果有有理根，必为整数根，且为常数项-14的因数为： 由带余除法可得：所以在有理数域上只有2是它的根。例10：多项式在有理数域上是否可约？解：常数项1的因式为： 由带余除法可得： 所以其在有理数域上不可约4.5 带余除法在矩阵多项式中的应用4,5.1 关于矩阵多形式可逆的判定在关于矩阵多项式可逆判别中，这里提出了用多项式的带余除法来解决：“已知，证明可逆且求其逆”这一类问题得方法.定理：用除，若，其中是次数低于的一个非零多项式，则用除，如此下去，求出与的最大公因式；若，则有多项式使，由于，从而有，故可逆，且例11、设n阶矩阵A满足，证明：可逆，并求其逆。 证明：设则由带余除法： 得： 由定义，可逆且 例12、设，已知，证明可逆且求的逆。 证明：由带余除法有： （1） (2) 由（1）式，代入（2）式，整理得： 又， 可逆，且4.5.2 有关矩阵最小多项式的问题（见文3）例13、设是方阵A的最小多项式。若是A的零化多项式（即），则整除 证：用去除，可设 其中，以A代上式，得 于是，即整除例14、设是对角块矩阵，是子方阵，证明A的最小多项式等于这些的最小多项式的最小公倍式。证：令，显然 从例13知反过来，因 即对每个，再从例13知，从而，这就表明参考文献1 王萼芳 石生明.高等代数M.北京市：高等教育出版社，2003.7：8-9，13-152 徐仲 陆全 张凯院 吕全义 陈芳 袁志杰.高等代数导教导学导考M.西安:西北工业大学出版社,2004.3:3-823 刘丁西.高等代数习题精解M.合肥:中国科技技术大学出版社,2004.9:7-244 王成 饶从军.矩阵初等变换的应用研究J.高等数学研究，2007.1(4):3-105 宋玉霞 王文省.用矩阵的初等变换求商和余式J.大学数学，2005,21(1): 1-26 黄朝军.矩阵初等变换的一个应用J.黔东南民族师范高等专科学校学报，2004,22(6):4-67 北京大学数学系几何代数教研室.高等代数M.北京：人民教育出版社.1978.2-48 郑新东.高等代数学习指南M.广州：华南理工大学出版社.1-69 张禾瑞，郝鈵新.高等代数（第四版）M.北京：高等教育出版社，1999.3-2.10 北京大学数学系几何与代数教研室代数小组.高等代数（第二版）M.北京：高等教育出版社，1988.7-411 程云鹏，张凯院，徐仲.矩阵论（第二版）M.西安：西北工业大学出版社，2003.4-2致 谢本论文是在余海峰导师的悉心指导之下完成的。四年来，导师渊博的专业知识，严谨的治学态度，精益求精的工作作风，诲人不倦的高尚师德，朴实无华、平易近人的人格魅力对我影响深远。导师不仅授我以文，而且教我做人，虽历时四载，却赋予我终生受益无穷之道。本论文从选题到完成，几易其稿，每一步都是在导师的指导下完成的，倾注了导师大量的心血，在此我向我的导师余海峰表示深切的谢意与祝福！本论文的完成也离不开其他各位老师、同学和朋友的关心与帮助。在此也要感谢谢敏芳等各位老师在论文开题、初稿、定稿期间所提出的宝贵意见。回想整个论文的写作过程，虽有不易，却让我除却浮躁，经历了思考和启示，也更加深切地体会了数学的精髓和意义，因此倍感珍惜。书到用时方恨少，在这篇论文的写作过程中，我深感自己的水平还非常的欠缺。生命不息，学习不止，人生就是一个不断学习和完善的过程。孟飞飞2015年05月3日于合肥学院