您的位置:首页 >综合要闻 >正文

辗转相除法的数学原理(辗转相除法原理)

摘要 大家好,飞飞今天来为大家解答以下的问题,关于辗转相除法的数学原理,辗转相除法原理这个很多人还不知道,那么下面让我带着大家一起来看看吧...

大家好,飞飞今天来为大家解答以下的问题,关于辗转相除法的数学原理,辗转相除法原理这个很多人还不知道,那么下面让我带着大家一起来看看吧!

1、你好!!!不知道你是否能看懂,反正我是看不懂。

2、欧几里得原理(辗转相除法)以及c语言的实现~!2006-07-14 11:26定义一 任给两个整数a,b,其中b≠0, 如果存在一个整数q使得等式 a=bq 成立,则称b整除a,记作b|a 。

3、此时称b为a的约数,a为b的倍数。

4、定理二 设a,b是两个整数,其中b>0,则存在唯一的整数q及r,使得a=bq+r,0≤r

5、定义三 设a1,a2,…,an 是n个不全为零的整数,若整数d是它们之中每一个数的约数,那么d就叫a1,a2,…,an一个公约数,整数a1,a2,…,an的公约数中最大的一个叫最大公约数,记作(a1,a2,…,an ),若(a1,a2,…,an )=1,则称a1,a2,…,an 互素。

6、定理四 若a|bc,(a,b)=1,则a|c.定理五 (a1,a2,…,an )=((a1,a2,…,an-1 )an).例: 在中国古代就有一个很好的算法来计算a,b的最大公约数(a,b),称为辗转相除法,在西方称为Euclid(欧几里得)算法。

7、下面通过计算(1397,2413)来阐述这一算法。

8、 首先,我们用这两个数1397和2413中两个数中小的去除大的,得商为1,余数为1016。

9、将原来两个数中大的2413扔掉,将1397作为大数,将余数1016作为新的小数。

10、重复上面的过程:用1016去除1397,得商为1,余数为381。

11、扔掉1397,将381作为除数,1016作为被除数。

12、用381去除1016,得商为2余数为254,扔掉1016,用254 去除381,得商为1 ,余数为127,再扔掉381,用127去除254,发现能整除,于是127就是最大公约数。

13、整个计算过程为: 2413=1397*1……1016,1397=1016*1……381, 1016=381*2……254,381=254*1……127,254=127*2……0,所以(1397,2413)=127。

14、 为什么这样求出是就是最大公约数呢?下面对a,b为正整数(a>b)的情形给出说明。

15、根据定理二,商q和余r数满足 a=bq+r,且0≤r ≤b-1.若r=0,显然(a,b)=b;若r≠0,由于a=bq+r,每个能整除b,r的整数都能整除a,当然能同时整除a,b,所以(b,r)|(a,b);另一方面,r=a-bq,每个能整除a,b的整数都能整除r, 当然能同时整除b,r, 所以(a,b)|(b,r).因此(a,b)=(b,r). 辗转相除法进行一步后,b 取代原来的a,用r取代原来的b,最大公约数保持不变,因此我们的算法可以一直进行下去:a=bq1+r1,b=r1q2+r2,r1=r2q3+r3,…rk-3=rk-2qk-1+rk-1,rk-2=rk-1qk.一旦出现rk-2=rk-1qk(即rk=0),则有rk-1=(rk-2,rk-1)=…=(r1,r2)=(b,r1)=(a,b).这个算法用c语言来实现源代码如下:#include void main(){ int a,b,m,n,temp,c,d; printf("请输入两个数字"); scanf("%d%d",&m,&n); d=m*n; while (temp) { a=m>n?m:n; b=m<=n?m:n; temp=a%b; m=temp; n=b; } printf("这两个数的最大公约数是%d",b); c=d/b; printf("这两个数的最小公倍数是%d",c);}(两个数的成积除以两个数的最大公约数就是这两个数的最小公倍数)还有什么不明白的地方再问我。

16、 谢谢!!!。

本文分享完毕,希望对大家有所帮助哦。

版权声明:本文由用户上传,如有侵权请联系删除!