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

来源：学生作业帮编辑：大师作文网作业帮分类：数学作业时间：2024/11/18 12:04:02

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）.
定理得证.
欧几里德算法就是对照这个定理来做的,每一次辗转相除其实就是用了一次上面的定理,一步一步递推得到最后结果.

编一个程序,用递归函数 gcd(a,b)实现求两个整数 a,b 最大公因子的欧几里德算法.输入任意整数a,b,调用递 C语言编程用试探法（要求从大到小试探）实现函数gcd(m,n),其功能为求解正整数m、n的最大公约数. 编程用辗转相除法（不使用递归）实现函数gcd(m,n),其功能为求解正整数m、n的最大公约数. C语言编程用辗转相除法（不使用递归）实现函数gcd(m,n),其功能为求解正整数m、n的最大公约数. 用C#程序,求两数的最大公约数和最小公倍数.程序里不能带gcd函数. 能够返回最大公约数的函数gcd 、解答题(给出必要的文字说明和解答过程. RSA算法中,设p=9,q=23,计算加密密钥和解密密钥（要求写出详细计算过程和必要的说明）定位误差计算.务必给出必要的说明和解答 vb分别用子过程和子函数编写求两个数的最大公约数（算法用辗转相减法） gcd(a,a+b)=gcd(a,b) 证明 a 和 a+b 的最大公约数等于 a和b的最大公约数计算（写出必要的解题过程）