230问答网 > 用欧几里德算法计算49910 和103569的最大公约数：gcd（49910 , 103569），请给出必要的求解过程。

用欧几里德算法计算49910 和103569的最大公约数：gcd（49910 , 103569），请给出必要的求解过程。

2024-12-29 00:13:36

推荐回答（1个）

回答1：

int fun(int x,int y){
if(x%y==0)
return y;
else
return fun(y,x%y);
}

原理

首先给定两个数a,b（a>b）,则根据除法运算，a/b=q......r。q是商，r是余数。也可以表示为a=bq+r。这是小学就知道的。

下面给出一个定理：
若a=bq+r，则（a,b）=（b,r），即a,b的最大公约数等于b,r的最大公约数。

举个例子来说：
24=10*2+4，那么(24,10)=(10,4)=2

这个定理的证明也很简单。
设c是a和b的任意一个公约数,则c能同时整除a和b,即a=cx,b=cy，（x,y是整数）
将它们代入“a=bq+r”中：
cx=cyq+r
得到r=c(x-yq)，说明c也能整除r，即c也是b和r的公约数。
于是a和b的公约数就是b和r的公约数，那么a和b最大公约数就是b和r的最大公约数，（a,b）=（b,r）。
定理得证。

欧几里德算法就是对照这个定理来做的，每一次辗转相除其实就是用了一次上面的定理，一步一步递推得到最后结果。