证明:辗转相除法与更相减损术

辗转相除法与更相减损术的证明 前言

这两种方法都是用来求两个数的最大公约数,但是从时间复杂度的角度来讲,辗转相除法的效率会高于更相减损术,尤其是在两数相差比较大的时候。

两者证明方法类似,但因为更相减损术的证明更为简单,并且有了其基础也能更快地去理解辗转相除法,故先证明更相减损术。

更相减损术的证明:

更相减损术是出自《九章算术》的一种求最大公约数的算法,它原本是为约分而设计的,但它适用于任何需要求最大公约数的场合。——百度百科

Description:

\[\forall a,b\in \mathbb{N},a\geq b\:\Rightarrow gcd(a,b)=gcd(b,a-b)=gcd(a,a-b) \]

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zyxwzp.html