这两种方法都是用来求两个数的最大公约数,但是从时间复杂度的角度来讲,辗转相除法的效率会高于更相减损术,尤其是在两数相差比较大的时候。
两者证明方法类似,但因为更相减损术的证明更为简单,并且有了其基础也能更快地去理解辗转相除法,故先证明更相减损术。
更相减损术的证明:更相减损术是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。——百度百科
Description:
\[\forall a,b\in \mathbb{N},a\geq b\:\Rightarrow gcd(a,b)=gcd(b,a-b)=gcd(a,a-b) \]