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

欧几里得算法是数学中用来求解最大公约数的一种最普遍算法。在了解欧几里得算法的证明过程之前，建议大家先来了解一下求解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\),也就是我们将其分解成为了商乘以除数加余数的形式。

注意！我们在证明很多带有取模运算的定理的时候，将模运算的被模数化成这种形式都是相当管用的，一定要积累这种方法！

分解为商乘以除数加余数的形式后，对于\(a,b\)的任何一个公约数\(d\)，都会有\(d|a,d|x\times b\)，所以就会有\(d|(a-x\times b)\)（这个位置的证明是显然的，大家好好想一想就能明白）

那么，因为\(a=x\times b+y,d|(a-x\times b)\)，有\(d|y\)。根据模运算的定义，有\(a\%b=y\)，那么，欧几里得算法就证明完毕了。