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

学校代码: 11059
学 号:1107011032

Hefei University
毕业论文（设计）
BACHELOR DISSERTATION

论文题目: 带余除法及其应用研究
学位类别: 理学学士
学科专业: 信息与计算科学
作者姓名: 孟飞飞
导师姓名: 余海峰
完成时间: 2015年05月03日

带余除法及其应用研究
摘要
本文的主旨思想是带余除法的简单介绍以及带余除法在日常生活中的应用，整片论文都围绕带余除法来展开论述，先是介绍带余除法的来源及课题意义，然后通过整数的带余除法和多项式的带余除法让大家对带余除法的应用有一个更深的认识。最后通过实例来展现其在应用研究中所起到的作用。
本文的正文是介绍整数和多项式的带余除法，从这二个层面可以认识到带余除法是一种普遍应用于生活中的思想。可以这样说多项式的带余除法是整数带余除法的推广，所以有必要对整数带余除法进行介绍，多项式的带余除法中将涉及辗转相除法的介绍，整除的基本概念与基本性质、最大公因式、公共根、重根以及一元多项式矩阵的相关性质。下面就开始进入本文的正题吧!
关键词：一元多项式 带余除法 辗转相除法 最大公因式 一元多项式矩阵

With more than division and its application research
 abstract
Purpose 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

目录
第一章 前言 5
1.1 研究背景 5
1.2 课题意义 7
第二章 整数的带余除法 8
2.1 整数带余除法的解释及证明 8
2.2 整数带余除法的一些性质 9
2.3最大公约数与辗转相除法 9
2.4 整除的进一步性质与最小公倍数 10
第三章 多项式的带余除法 12
3.1多项式带余除法的定理及其证明 12
3.2 带余除法的二种计算格式 13
3.2.1 普通除法（长除法） 13
3.2.2 竖式除法 13
3.2.3 综合除法 14
第四章 带余除法在解题中的应用 15
4.1 有关两个多项式除法与整除关系问题 15
4.2 辗转相除法是带余除法的特殊应用 16
4.2.1 辗转相除法计算两个多项式的最大公因式及它们与最大公因式的组合关系 16
4.2.2 求两个多项式的公共根 18
4.2.3 解有关多项式的重根，重因式问题 18
4.3 求函数值f(a) 18
4.4 解有关有理数域上的因式分解及有理根 19
4.5 带余除法在矩阵多项式中的应用 20
4,5.1 关于矩阵多形式可逆的判定 20
4.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=21×12；105=21×5）；因为252−105=21× (12−5) =147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出，两数的最大公约数可以用两数的整数倍相加来表示，如21=5×105+ (−2)×252。这个重要的结论叫做裴蜀定理。
辗转相除法最早出现在欧几里得的《几何原本》中（大约公元前300年），所以它是现行的算法中历史最悠久的。这个算法原先只用来处理自然数和几何长度（相当于正实数），但在19世纪，辗转相除法被推广至其他类型的数学对象，如高斯整数和一元多项式。由此，引申出欧几里得整环等等的一些现代抽象代数概念。后来，辗转相除法又扩展至其他数学领域，如纽结理论和多元多项式。
辗转相除法有很多应用，它甚至可以用来生成全世界不同文化中的传统音乐节奏。在现代密码学方面，它是RSA算法（一种在电子商务中广泛使用的公钥加密算法）的重要部分。它还被用来解丢番图方程，比如寻找满足中国剩余定理的数，或者求有限域中元素的逆。辗转相除法还可以用来构造连分数，在施图姆定理和一些整数分解算法中也有应用。辗转相除法是现代数论中的基本工具。
辗转相除法处理大数时非常高效，如果用除法而不是减法实现，它需要的步骤不会超过较小数的位数（十进制下）的五倍。拉梅于1844年证明了这点，同时这也标志着计算复杂性理论的开端。
辗转相除法是目前仍然在使用的历史最悠久的算法之一。它首次出现于《几何原本》（卷7命题1–2、卷10命题2–3）（大约公元前300年）。在卷7中用于整数，在卷10中用于线段的长度（以现代的观点看，线段的长度可视为正实数，也就是说辗转相除法实际可用于实数上，但是当时未有实数的概念）。卷10中出现的算法是几何的，两段线段a和b的最大公约数是a和b的公度中的最大值。
这个算法可能并非欧几里得发明，因为他也有将先前其他数学家的一些成果编进他的《几何原本》。数学家、历史学家范德瓦尔登（英语：Bartel Leendert van der Waerden）认为卷7的内容可能来自毕达哥拉斯学院出身的数学家写的关于数论的教科书。辗转相除法在当时很可能已为尤得塞斯（大约公元前375年）所知 ，甚至可能更早之前就已经存在，因为欧几里得和亚里士多德的著作中都出现了ἀνθυφαίρεσις一词（意为“辗转相减”）。
几个世纪之后，辗转相除法又分别被中国人和印度人独立发现，主要用来解天文学中用到的丢番图方程以及制定准确的历法。5世纪末，印度数学家、天文学家阿里亚哈塔曾称辗转相除法为“粉碎机”，这可能是因为它在解丢番图方程时很有效。在中国，《九章算术》中提到了一种类似辗转相减法的“更相减损术”。《孙子算经》中则出现了中国剩余定理的一个特例，但是直到1247年秦九韶才于其《数学九章》中解答了该定理的一般情况，当中用到了他发明的大衍求一术。此法的其中一部分实际上便是辗转相除的原理，秦九韶在书中对此有明确表述。在欧洲，辗转相除法首次出现于克劳德·巴希特（英语：Claude Gaspard Bachet de Méziriac）的著作《愉悦讨喜的问题》（Problèmes plaisants et délectables）的第二版在欧洲，辗转相除法被用于丢番图方程和构建连分数。后来，英国数学家桑德森（英语：Nicholas Saunderson）在其著作中收编了扩展欧几里得算法，作为一个有效计算连分数的方法。他将此法的来源归名于罗杰·科茨（英语：Roger Cotes）。
19世纪，辗转相除法促成了新数系的建立，如高斯整数和艾森斯坦整数。1815年，高斯用辗转相除法证明高斯整数的分解是惟一的，尽管他的研究到了1832年才首度发表。高斯在他的《算数研究》（出版于1801年）中实际上也有援引这个算法，但仅是以连分数方法的形式叙述。约翰·狄利克雷是第一个将辗转相除法作为数论的基础的数学家。[来源请求]狄利克雷提出，数论中的很多结论，如分解的惟一性，在任何使辗转相除法适用的数系中均有效。狄利克雷的数论讲义后来经理查德·戴德金编辑和推广，戴德金也有以辗转相除法来研究代数整数。比如，他是第一个用高斯整数的分解惟一性证明费马平方和定理的数学家。戴德金还率先定义了欧几里得整环的概念。19世纪末，戴德金所定义的理想概念使得数论的重心不必建基于辗转相除法，从而促进了理论的发展。
辗转相除法的其他应用发展于19世纪。1829年，施图姆将辗转相除法用于施图姆序列（用于确定多项式的不同实根的个数的方法）。
辗转相除法是历史上第一个整数关系算法（英语：integer relation algorithm），即寻找两个可通约实数的整数关系的算法。近年来，出现了一些新颖的整数关系算法，如埃拉曼·弗格森（英语：Helaman Ferguson）和福尔卡德于1979年发表的弗格森-福尔卡德算法（Ferguson–Forcade algorithm） 、以及与它相关的LLL算法（英语：Lenstra–Lenstra–Lovász lattice basis reduction algorithm）、HJLS算法以及PSLQ算法。
1969年，科尔（Cole）和戴维（Davie）基于辗转相除法创造了一种二人游戏，叫做“欧几里得游戏”。这个游戏有最优策略。游戏开始于两列分别为a和b个棋子组成的序列，玩家轮流从较长一列中取走较短一列棋子数量的m倍的棋子。如果两列棋子p和q分别由x和y个棋子组成，其中x大于y，那么玩家可以将序列p的棋子数量减少为自然数x − my。最后率先将一列棋子清空的玩家胜出。
1.2 课题意义
带余除法，数学术语，广泛应用于数学之中。辗转相除法的基本步骤就是带余除法，辗转相除法又称欧几里得算法。带余除法是小学到大学一直沿用的转化方法，也是研究整数与多项式的一个基本方法，在有关整数和多项式的其他问题中还有更广泛的应用，虽然它的内容简单，但它里面蕴含的意义却很深刻，只有对它的意思彻底了解，才能引申出在不同场合下的用法，在高中的数学学习中，许多知识点都会用到带余除法，掌握了带余除法，就多了种解决问题的方法，也是多了条通往成功的途径。

第二章 整数的带余除法
整除是初等数论这一科目的基础概念，而带余数除法是所有除法的一般形式，所以深度了解这种理论的该念、性质和应用是十分必要的。接下来我会通过整数的带余除法来浅谈带余除法在数论这一科目的重要性，使我们能掌握带余除法的精华，有助于以后的解题。
2.1 整数带余除法的解释及证明
对任意整数a，b且b≠0，存在唯一的数对q，r，使a=bq+r，其中0≤r|b|。这个事实称为带余除法定理，是整除理论的基础。若c|a，c|b，则称c是a，b的公因数。若d是a，b的公因数，d≥0，且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-bq≥0。现假设a-bq≥|b|，但这样便有a-b(q±1)≥0成立（b为正数时取加号，负数时取减号），且a-b(q±1)≤a-bq。这违反了t是最小元素这一事实，於是a-bq<|b|。令r=a-qb，即证存在性。
【唯一性】设q1、r1是满足a=bq+r，0≤r<|b|的另一对整数，因为bq1+r1=bq+r，于是b(q-q1)=r1-r故|b||q-q1|=|r1-r|由于r及r1都是小于b的非负整数，所以上式右边是小于|b|的。如果q≠q1，则上式左边≥|b|，这是不可能的。所以q=q1， r=r1，即证唯一性。
2.2 整数带余除法的一些性质
(ⅰ) 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）是任意的整数；
(ⅳ) b½a Þ bc½ac，此处c是任意的非零整数；
(ⅴ) b½a，a ¹ 0 Þ|b|£|a|；b½a且|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、求下列多项式的公共根
　，
解：由辗转相除法，可求得

所以它们的公共根为[3]
4.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-15
[2] 徐仲 陆全 张凯院 吕全义 陈芳 袁志杰.高等代数导教导学导考[M].西安:西北工业大学出版社,2004.3:3-82
[3] 刘丁西.高等代数习题精解[M].合肥:中国科技技术大学出版社,2004.9:7-24
[4] 王成 饶从军.矩阵初等变换的应用研究[J].高等数学研究，2007.1(4):3-10
[5] 宋玉霞 王文省.用矩阵的初等变换求商和余式[J].大学数学，2005,21(1): 1-2
[6] 黄朝军.矩阵初等变换的一个应用[J].黔东南民族师范高等专科学校学报，2004,22(6):4-6
[7] 北京大学数学系几何代数教研室.高等代数[M].北京：人民教育出版社.1978.2-4
[8] 郑新东.高等代数学习指南[M].广州：华南理工大学出版社.1-6
[9] 张禾瑞，郝鈵新.高等代数（第四版）[M].北京：高等教育出版社，1999.3-2.
[10] 北京大学数学系几何与代数教研室代数小组.高等代数（第二版）[M].北京：高等教育出版社，1988.7-4
[11] 程云鹏，张凯院，徐仲.矩阵论（第二版）[M].西安：西北工业大学出版社，2003.4-2

致 谢
本论文是在余海峰导师的悉心指导之下完成的。四年来，导师渊博的专业知识，严谨的治学态度，精益求精的工作作风，诲人不倦的高尚师德，朴实无华、平易近人的人格魅力对我影响深远。导师不仅授我以文，而且教我做人，虽历时四载，却赋予我终生受益无穷之道。本论文从选题到完成，几易其稿，每一步都是在导师的指导下完成的，倾注了导师大量的心血，在此我向我的导师余海峰表示深切的谢意与祝福！     
本论文的完成也离不开其他各位老师、同学和朋友的关心与帮助。在此也要感谢谢敏芳等各位老师在论文开题、初稿、定稿期间所提出的宝贵意见。回想整个论文的写作过程，虽有不易，却让我除却浮躁，经历了思考和启示，也更加深切地体会了数学的精髓和意义，因此倍感珍惜。书到用时方恨少，在这篇论文的写作过程中，我深感自己的水平还非常的欠缺。生命不息，学习不止，人生就是一个不断学习和完善的过程。

孟飞飞
2015年05月3日于合肥学院