辗转相除法（欧几里得算法）的证明

如何证明辗转相除法（欧几里得算法）

欧几里得算法是数学中用来求解最大公约数的一种最普遍算法。在了解欧几里得算法的证明过程之前，建议大家先来了解一下求解GCD（最大公约数）的两种方式，博客链接在下：

求解GCD问题的两种方式

于是我们知道了，所谓的欧几里得算法就是这么一个东西：

\[\forall a,b\in N,b\neq 0,\Longrightarrow \gcd(a,b)=\gcd(b,a\%b)

\]

下面我们要来证明这个定理。

这个定理的证明采用了数学归纳法和分类讨论思想（呵呵数学）。

首先，假如\(a<b\)，那么显然会有\(a\%b=a\)，也就会出现\(\gcd(a,b)=\gcd(b,a)\)，显然成立。

然后，在\(a\ge b\)的时候，我们设\(a=x\times b+y\),也就是我们将其分解成为了商乘以除数加余数的形式。