证明等式gcd(m,n)=gcd(n mod m,m),对每对正整数m和n,m>0都成立.这是算法设计与分析上的题.求大神帮忙
问题描述：
证明等式gcd(m,n)=gcd(n mod m,m),对每对正整数m和n,m>0都成立.这是算法设计与分析上的题.求大神帮忙
答
这是用辗转相除法求两个数的最大公约数
原理：
如果 n=bm+r
则 (n,m)=(m,r)
gcd(m,n)求的是 m与n的最大公约数
n mod m是n除以m的余数
所以有 gcd(m,n)=gcd(n mod m,m)
如果还是不明白,请搜索“辗转相除法"