GCD_如何证明gcd(a，b，c)=gcd(gcd(a，b)，c)[数学]

精选知识

gcd(a,b,c)是a,b,c的公约数,故gcd(a,b,c)能分别整除a,b,c,由gcd(a,b,c)能整除a,b,且gcd(a,b)是a,b的最大公约数,于是gcd(a,b,c)能整除gcd(a,b),并能整除c,故gcd(a,b,c)是gcd(a,b)和c的公约数,gcd(gcd(a,b),c)是gcd(a,b)和c的最大公约数.故gcd(a,b,c)能整除gcd(gcd(a,b),c).

gcd(gcd(a,b),c)是gcd(a,b),c的公约数,故gcd(gcd(a,b),c)能整除gcd(a,b),并能整除c,于是gcd(gcd(a,b),c)能整除a,b和c,gcd(a,b,c)是a,b,c的最大公约数,故gcd(gcd(a,b),c)能整除gcd(a,b,c).

由gcd(a,b,c)能整除gcd(gcd(a,b),c),gcd(gcd(a,b),c)能整除gcd(a,b,c).故得gcd(a,b,c)=gcd(gcd(a,b),c).

其他回答

首先证明引理1:

若k是a,b的公因子,m是a,b的最大公因子

则k必整除m

证明过程:

将a,b分解为素数之积:

a=a1*a2*a3...*an*c1*c2*c3...*cn

b=b1*b2*b3...*bm*c1*c2*c3...*cn

其中c1到cn表示a,b中相同的因子

那么m=c1*c2*c3...*cn

而k是c...

其他类似问题

问题1：b==0?a:gcd(b,a%b)在C＋＋里什么意思[数学科目]

：是一组.用法如下segment1 segment2 ：segment3(segment1,2,3是三个语句)意思是判断segment1是否是True如果是True,则执行segment2如果是False,则执行segment3

在这句代码中,意思就是

判断b等于0的真假

如果是真,则返回a如果是假,则返回gcd(b,a%b) （目测是求最大公约数吧）

问题2：如何证明gcd(a,b) = gcd(a+b,lcm(a,b))[数学科目]

设a=r1k,b=r2k,r1,r2互质,则k=gcd(a,b)

a+b=(r1+r2)k,lcm(a,b)=r1r2k

因为r1,r2互质,所以

gcd[(r1+r2)k,r1r2k]=k

所以gcd(a,b) = gcd(a+b,lcm(a,b))

问题3：gcd(ac,bc) = c* gcd(a,b)[数学科目]

gcd表示最大公约数

1) 首先证明c*gcd(a,b)是ac、bc的一个公约数

因为c | c,gcd(a,b) | a,所以c*gcd(a,b) | ac

因为c | c,gcd(a,b) | b,所以c*gcd(a,b) | bc

于是c*gcd(a,b)是ac、bc的一个公约数

2) 其次证明c*gcd(a,b)是ac、bc的最大公约数

最大公约数的性质是,两个数的最大公约数可以整除这两个数的其他公约数

于是c*gcd(a,b) | gcd(ac,bc),假设gcd(ac,bc)=k*c*gcd(a,b),k>=1

因为k*c*gcd(a,b) | ac,所以k*gcd(a,b) | a

因为k*c*gcd(a,b) | bc,所以k*gcd(a,b) | b

于是k*gcd(a,b)是a、b的一个公约数,根据最大公约的性质,k*gcd(a,b) | gcd(a,b),于是k=1

从而gcd(ac,bc)=c*gcd(a,b)

问题4：如何证明gcd(a,b)=gcd(a,a+b)如题a和b是正整数[数学科目]

设gcd(a,b)=c,

那么存在互质m,n,使得a=mc,b=nc.

a+b=(m+n)c

因为m,n互质,没有同一个大于1的整数能除m和n,所以m+n,和m也是互质,由此gcd(a,a+b)=c=gcd(a,b)

问题5：如果gcd(a b)=1 ,证明gcd(ab,c)=gcd(a,c)*gcd(b,c) 怎么证阿如题回答对的话可以追加悬赏[数学科目]

设x=gcd(ab,c),y=gcd(a,c),z=gcd(b,c)

则x|ab 且x|c 因gcd(a,b)=1 所以x|a或x|b

若x|a且x|c 则x|gcd(a,c) 即x|y

若x|b且x|c 则x|gcd(b,c) 即x|z

所以x|yz

又y|a且 y|c z|b且 z|c

由y|a且 y|c 可得到y|ab 且y|c 那么y|gcd(ab,c)

同理 z|gcd(ab,c) 所以lcm(y,z)|gcd(ab.c)

注意到y|a ,z|b 而gcd(a,b)=1 所以gcd(y,z)=1 有 lcm(y,z)=yz

注lcm最小公倍数

所以yz|gcd(ab,c)

所以x|yz yz|x

x=yz