如何證明輾轉相除法（歐幾裡得算法）

歐幾裡得算法是數學中用來求解最大公約數的一種最普遍算法。在了解歐幾裡得算法的證明過程之前，建議大家先來了解一下求解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\)，那麼，歐幾裡得算法就證明完畢了。