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

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

歐幾裡得算法是數學中用來求解最大公約數的一種最普遍算法。在了解歐幾裡得算法的證明過程之前，建議大家先來了解一下求解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\),也就是我們将其分解成為了商乘以除數加餘數的形式。