《孟飞飞的毕业论文 带余除法及其应用研究》由会员分享,可在线阅读,更多相关《孟飞飞的毕业论文 带余除法及其应用研究(23页珍藏版)》请在金锄头文库上搜索。
1、 学校代码: 11059 学 号:1107011032 Hefei University 毕业论文(设计)BACHELOR DISSERTATION 论文题目: 带余除法及其应用研究 学位类别: 理学学士 学科专业: 信息与计算科学 作者姓名: 孟飞飞 导师姓名: 余海峰 完成时间: 2015年05月03日 带余除法及其应用研究摘要本文的主旨思想是带余除法的简单介绍以及带余除法在日常生活中的应用,整片论文都围绕带余除法来展开论述,先是介绍带余除法的来源及课题意义,然后通过整数的带余除法和多项式的带余除法让大家对带余除法的应用有一个更深的认识。最后通过实例来展现其在应用研究中所起到的作用。本文的
2、正文是介绍整数和多项式的带余除法,从这二个层面可以认识到带余除法是一种普遍应用于生活中的思想。可以这样说多项式的带余除法是整数带余除法的推广,所以有必要对整数带余除法进行介绍,多项式的带余除法中将涉及辗转相除法的介绍,整除的基本概念与基本性质、最大公因式、公共根、重根以及一元多项式矩阵的相关性质。下面就开始进入本文的正题吧!关键词:一元多项式 带余除法 辗转相除法 最大公因式 一元多项式矩阵With more than division and its application researchabstractPurpose of this article is more than with d
3、ivision 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 divisio
4、n 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 aspec
5、ts 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 di
6、vision 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 gr
7、eatest 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 辗转相除法是带余除法
8、的特殊应用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
9、。一般限定余数的范围在0与b之间,也有限定在-b/2与b/2之间。这样的限定都是为了使得满足等式的q有且仅有一个。这时候的q称为带余除法的商。带余除法一般表示为:a / b=q r 。表达为:“a除以b等于q,余r”。最常见的带余除法是整数与整数的带余除法(被除数a和除数b都是整数),但实数与整数乃至实数与实数的带余除法也有应用。对一般的抽象代数系统,能够进行带余除法的都是具有欧几里德性质的系统。如果余数为零,则称b整除a。一般约定除数b不能为0.带余除法的计算有长久的历史,有各种计算工具和计算方法。最常用的是长除法(竖式除法)。带余除法在数论中有不少用途,比如说辗转相除法的基本步骤就是带余除
10、法。 在数学中,辗转相除法,又称欧几里得算法,是求最大公约数的算法。辗转相除法首次出现于欧几里得的几何原本(第VII卷,命题i和ii)中,而在中国则可以追溯至东汉出现的九章算术。两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如,252和105的最大公约数是21(252=2112;105=215);因为252105=21 (125) =147,所以147和105的最大公约数也是21。在这个过程中,较大的数缩小了,所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时,所剩下的还没有变成零的数
11、就是两数的最大公约数。由辗转相除法也可以推出,两数的最大公约数可以用两数的整数倍相加来表示,如21=5105+ (2)252。这个重要的结论叫做裴蜀定理。辗转相除法最早出现在欧几里得的几何原本中(大约公元前300年),所以它是现行的算法中历史最悠久的。这个算法原先只用来处理自然数和几何长度(相当于正实数),但在19世纪,辗转相除法被推广至其他类型的数学对象,如高斯整数和一元多项式。由此,引申出欧几里得整环等等的一些现代抽象代数概念。后来,辗转相除法又扩展至其他数学领域,如纽结理论和多元多项式。辗转相除法有很多应用,它甚至可以用来生成全世界不同文化中的传统音乐节奏。在现代密码学方面,它是RSA算
12、法(一种在电子商务中广泛使用的公钥加密算法)的重要部分。它还被用来解丢番图方程,比如寻找满足中国剩余定理的数,或者求有限域中元素的逆。辗转相除法还可以用来构造连分数,在施图姆定理和一些整数分解算法中也有应用。辗转相除法是现代数论中的基本工具。 辗转相除法处理大数时非常高效,如果用除法而不是减法实现,它需要的步骤不会超过较小数的位数(十进制下)的五倍。拉梅于1844年证明了这点,同时这也标志着计算复杂性理论的开端。 辗转相除法是目前仍然在使用的历史最悠久的算法之一。它首次出现于几何原本(卷7命题12、卷10命题23)(大约公元前300年)。在卷7中用于整数,在卷10中用于线段的长度(以现代的观点
13、看,线段的长度可视为正实数,也就是说辗转相除法实际可用于实数上,但是当时未有实数的概念)。卷10中出现的算法是几何的,两段线段a和b的最大公约数是a和b的公度中的最大值。这个算法可能并非欧几里得发明,因为他也有将先前其他数学家的一些成果编进他的几何原本。数学家、历史学家范德瓦尔登(英语:BartelLeendertvanderWaerden)认为卷7的内容可能来自毕达哥拉斯学院出身的数学家写的关于数论的教科书。辗转相除法在当时很可能已为尤得塞斯(大约公元前375年)所知,甚至可能更早之前就已经存在,因为欧几里得和亚里士多德的著作中都出现了一词(意为“辗转相减”)。几个世纪之后,辗转相除法又分别
14、被中国人和印度人独立发现,主要用来解天文学中用到的丢番图方程以及制定准确的历法。5世纪末,印度数学家、天文学家阿里亚哈塔曾称辗转相除法为“粉碎机”,这可能是因为它在解丢番图方程时很有效。在中国,九章算术中提到了一种类似辗转相减法的“更相减损术”。孙子算经中则出现了中国剩余定理的一个特例,但是直到1247年秦九韶才于其数学九章中解答了该定理的一般情况,当中用到了他发明的大衍求一术。此法的其中一部分实际上便是辗转相除的原理,秦九韶在书中对此有明确表述。在欧洲,辗转相除法首次出现于克劳德巴希特(英语:ClaudeGaspardBachetdeMziriac)的著作愉悦讨喜的问题(Problmesplaisantsetdlectables)的第二版在欧洲,辗转相除法被用于丢番图方程和构建连分数。后来,英国数学家桑德森(英语:NicholasSaunderson)在其著作中收编了扩展欧几里得算法,作为一个有效计算连分数的方法。他将此法的来源归名于罗杰科茨(英语:RogerCotes)。 19世纪,辗转相除法促成了新数系的建立,如高斯整数和艾森斯坦整数。1815年,高斯用辗转相除法证明高斯整数的分解是惟一的,尽管他的研究到了