请用欧几里德算法,一步一步写出求36,90的最大公约数的过程.

dd小望2022-10-04 11:39:541条回答

请用欧几里德算法,一步一步写出求36,90的最大公约数的过程.
如题.具体的过程.

已提交，审核后显示！提交回复

wxwy_4_2 共回答了22个问题 | 采纳率100%: 辗转相除法（欧几里得算法）
#include
int aa(int m,int n)
{
int r;
r=m%n;
while(r)
{
m=n;n=r;r=m%n;
}
return n;
}
void main()
{
int a,b,k;
printf("请输入任意两个数：n");
scanf("%d%d",&a,&b);
k=aa(a,b);
printf("最大公约数为%d：n",k);
}
//输入36 90 最大公约数为18; 1年前

欧几里德算法证明中,为什么已知d|a且d|b且a=kb+r时,就得到d|r? zc8379661年前1: fannydanny 共回答了14个问题 | 采纳率92.9%

由d|a知存在整数m1使得a = m1*d；由d|b知存在整数m2使得b = m2 * d.
r = a - k*b = m1*d - k * m2 * d = (m1 - k * m2) * d,m1-k*m2为整数,则d|r.

1年前查看全部

欧几里德算法计算49910和103569的最大公约数 独孤依人小王1年前1: 衫杉仔共回答了17个问题 | 采纳率88.2%

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

1年前查看全部

欧几里德算法(辗转辗转相除法)所求的公约数为什么是最大公约数 欧几里德算法(辗转辗转相除法)所求的公约数为什么是最大公约数 RT,我只知道最后的得数一定是两者的公约数,但根据什么证明该公约数必是两者的最大公约数. gaobetty1年前1: zzxx企共回答了13个问题 | 采纳率84.6%

这个不难,去翻翻《近世代数》,《数论》,这种书上都有的,我在此稍微写一下,：
首先给定两个数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）.
定理得证.
欧几里德算法就是对照这个定理来做的,每一次辗转相除其实就是用了一次上面的定理,一步一步递推得到最后结果.

1年前查看全部

编一个程序,用递归函数 gcd(a,b)实现求两个整数 a,b 最大公因子的欧几里德算法.输入任意整数a,b,调用递 honh481年前5: 呆鸟-kk 共回答了27个问题 | 采纳率92.6%

#include
int Gcd(int M,int N )
{
int Rem;
while( N > 0 )
{
Rem = M % N;
M = N;
N = Rem;
}
return M;
}
void main()
{
int a,b;
scanf("%d",&a);
scanf("%d",&b);
printf("%dn",Gcd(a,b));
}

1年前查看全部