辗转相除法(共7页)

1、精选优质文档-倾情为你奉上 学院学 术 论 文题 目: 辗转相除法学号： 学校： 专业： 班级： 姓名： 指导老师： 时间： 摘要：求最大公约数是一个较为经典的问题。利用辗转相减算法，一次可以求出任意多个数的最大公约数，并编程序实现。其效率较传统的辗转相除算法有很大程度的提高。关键词：辗转相除法，辗转相减法，最大公约数，递归Subject: Euclidean algorithmAuthor: Science and technology in jiangxi normal college professional of math in class one ZengYanpingAbstrac

2、t: For companies is a relatively classic problems. Using Euclidean algorithm, can ask subtraction of more than a number of companies, and programming. The efficiency is the traditional Euclidean algorithm is XiangChu greatly improved.Keywords: euclidean algorithm euclidean subtraction companies recu

3、rsion正文：；定义：首先用较大数作为被除数，用较小数作除数进行除法运算，若余数不为0，再把上次的除数作为下次的被除数，把上次余数作为下次的除数，继续去除，知道余数为0为止，此时的除数即为两数的最大公约数。因此算法需连续多除法运算，故形象地命名为“辗转相除法”。 设a，b是任意两个正整数，由带余数除法，我们有下面的系列等式： a=，0<<b, b=+,0<<, =+,0<<, (1) =+,=0 因为每进行一次带余数除法，余数就至少减一，而b是有限的，所以我们最多进行b次带余数除法，总可以得到一个余数是零的等式，即=0 （1）式所指出的计算方法，叫作辗转相

4、除法。 ；定理：（1）若a，b是任意两个整数，则（a，b）就是（1）中最后一个不等于零的余数，即（a，b）= 证：由课本2,3定理即得 =(0, )=(,) =(,)= =(,b)=(a,b) 证完由于能够用辗转相除法直接算出，所以辗转相除法给出了求两整数的最大公因数的实际可行的算法.由定理2,3及（1）我们还可以得到 推论4.1 a，b的公因数与（a，b）的因数相同 （2）设a，b是任意两个不全为零的整数，（）若m是任意正整数，则（am，bm）=（a，b）m.（） 若是a，b的任一公因数，则（，）=，特别（，）=1 证：当a，b有一为零时，定理显然成立，今设a，b都不为零. （）由定理1，（

5、am，bm）=（m，m），（a，b）m=（，）m,因此不妨假定a，b都是正数,在（1）里，把各式两边同乘以m，即得 am=(bm) +m，0<m<bm， bm=(m) +m，0<m<m， m=（m）. 由定理4得（am，bm）=m=(a，b)m，因而（）获证. （）由（）及定理1， （，）=（，）=（，）=（a，b）， 故 （，）= 当 &=（a，b）时，上式即为（，）=1 证完 又若 （，）=，（，）=，（，）= （2） 于是我们有 （3） 若，是n个整数，则（，）= 证：由（2），但，故，由此类推，最后得到，即是，的一个公因数，又设d是，的任一公因数，则d，

6、d，由推论4.1， d，同样由推论4.1，d，由此类推，最后得d.因而d.故是，的最大公因数。：例题（1） a=-1859，b=1573，用辗转相除法求两数的最大公因数，即（-1859,1573） 解：1859=1*1573+286 1573=5*286+143 286=2*143所以（1859,1573）=143（2） 已知数列满足=1且816+2+5=0（n1），记=(n). 求， 的值； 求数列的通项公式及数列的前n项和解： =1，故=2；=，故=；=，故=4；=，故= 由816+2+5=0（n1）采用辗转相除法得： 816+2+5=（）. （816）+63=0 又=，=， 则（816）

7、+=0 又=+ 将代入式得（12）* +6=0即=2，=2（），=0是首项为，公比q=2的等比数列，故=*，即=*+（n1），由=得=，故+ =（+.+ ）+n = =(3)令F是有理数域，求Fx的多项式 f(x)= g(x)= 的最大公因式 对f(x)与g(x)施行辗转相除法。为了避免分数系数，在做除法时，可以用F的一个不等于零的数乘被除式或除式。而且不仅在每一次除法开始时可以这样做，就是在进行除法的过程中也可以这样做。这样商式自然会受到影响，但每次求得的余式与正确的余式只能差一个零因式。这对求最大公因式来说是没有什么关系的。把f(x)先乘以2，再用g(x)来除：（乘以2） 这样，得到第一余式把g(x)乘以3，再用去除： （乘以3） 约去公因子56后，得出第二余式 再以除，计算结果被整除； 所以就是f(x)与g(x)的最大公因式： （f(x)，g(x)）=x-