如何证明gcd(a,b)=gcd(a,a+b)如题a和b是正-查字典问答网

来自钱乐秋的问题

　　如何证明gcd(a,b)=gcd(a,a+b)如题a和b是正整数

　　如何证明gcd(a,b)=gcd(a,a+b)

　　如题

　　a和b是正整数

1回答

2020-08-06 19:59

我要回答

请先登录

罗麦丰

　　设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)

2020-08-06 20:02:50

猜你喜欢