搜搜做题作业网辗转相除法的证明
来源：学生作业帮 编辑：搜搜做题作业网作业帮 分类：数学作业 时间：2024/06/25 07:56:23
辗转相除法的证明
解题思路： 转化的原则
解题过程：
辗转相除法是用来计算两个数的最大公因数，在数值很大时尤其有用，而且应用在电脑程式上也十分简单。其理论如下:
如果 q 和 r 是 m 除以 n 的商及余数，即 m=nq+r，则 gcd(m,n)=gcd(n,r)。
证明是这样的: 设 a=gcd(m,n)，b=gcd(n,r)
证明：
∵a为m,n的最大公约数，
∴m能被a整除，且n也能被a整除，
∴由推论1得：qn也能被a整除，
∴ 由推论2得：m-qn也能被a整除，
又 ∵m-qn=r，
∴r也能被a整除，即a为n和r的公约数（注意：还不是最大公约数）
∵b为n和r的最大公约数，a为n和r的公约数
∴a≤b，
同理
∵b为n, r的最大公约数，
∴n能被b整除，且r也能被b整除，
∴由推论1得：qn也能被b整除，
∴由推论2得：qn+r也能被b整除，
又∵m=qn+r，
∴m也能被b整除，即b为m和n的公约数，（注意：还不是最大公约数）
∵a为m,n的最大公约数，b为m和n的公约数，
∴b≤a，
由以上可知：
a≤b与b≤a同时成立，
故可得
a=b，
证毕。
例如计算 gcd(546, 429)
gcd(546, 429) 546=1*429+117
=gcd(429, 117) 429=3*117+78
=gcd(117, 78) 117=1*78+39
=gcd(78, 39) 78=2*39
=39
最终答案：略
解题过程：
辗转相除法是用来计算两个数的最大公因数，在数值很大时尤其有用，而且应用在电脑程式上也十分简单。其理论如下:
如果 q 和 r 是 m 除以 n 的商及余数，即 m=nq+r，则 gcd(m,n)=gcd(n,r)。
证明是这样的: 设 a=gcd(m,n)，b=gcd(n,r)
证明：
∵a为m,n的最大公约数，
∴m能被a整除，且n也能被a整除，
∴由推论1得：qn也能被a整除，
∴ 由推论2得：m-qn也能被a整除，
又 ∵m-qn=r，
∴r也能被a整除，即a为n和r的公约数（注意：还不是最大公约数）
∵b为n和r的最大公约数，a为n和r的公约数
∴a≤b，
同理
∵b为n, r的最大公约数，
∴n能被b整除，且r也能被b整除，
∴由推论1得：qn也能被b整除，
∴由推论2得：qn+r也能被b整除，
又∵m=qn+r，
∴m也能被b整除，即b为m和n的公约数，（注意：还不是最大公约数）
∵a为m,n的最大公约数，b为m和n的公约数，
∴b≤a，
由以上可知：
a≤b与b≤a同时成立，
故可得
a=b，
证毕。
例如计算 gcd(546, 429)
gcd(546, 429) 546=1*429+117
=gcd(429, 117) 429=3*117+78
=gcd(117, 78) 117=1*78+39
=gcd(78, 39) 78=2*39
=39
最终答案：略