你好！！！不知道你是否能看懂，反正我是看不懂。

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

此时称b为a的约数，a为b的倍数。

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

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

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

下面通过计算（1397，2413）来阐述这一算法。

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

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

重复上面的过程：用1016去除1397，得商为1，余数为381。

扔掉1397，将381作为除数，1016作为被除数。

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

整个计算过程为： 2413=1397*1……1016，1397=1016*1……381， 1016=381*2……254，381=254*1……127，254=127*2……0，所以（1397，2413）=127。

为什么这样求出是就是最大公约数呢？下面对a,b为正整数（a>b）的情形给出说明。

根据定理二，商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);}(两个数的成积除以两个数的最大公约数就是这两个数的最小公倍数)还有什么不明白的地方再问我。

谢谢！！！。