来源:学生作业帮 编辑:神马作文网作业帮 分类:数学作业 时间:2024/09/22 08:33:25
最大公约数的一个公式证明30分
gcd(a+mb ,b)=gcd(a,b)
谁证明下,
证明:
显然gcd(a,b)|gcd(a+mb,b)
只需证明gcd(a+mb,b)|gcd(a,b)
设q=gcd(a+mb,b),所以q|b,q|a+mb
所以q|a
所以q|gcd(a,b)
综上gcd(a,b)|gcd(a+mb,b)且gcd(a+mb,b)|gcd(a,b)
所以gcd(a+mb,b)=gcd(a,b)