【數學】輾轉相除法

輾轉相除法 又名 歐幾裡德算法，是求兩個數的 \(\gcd\) 的一種辦法。

\[若整數 a\ge 整數 b,則 \gcd(a,b)=\gcd(b,a\bmod b).\]

證明： \(\because a\ge b\) \(\therefore a\) 可表示為 \(a=bq+r\)（其中 \(q\) 是整數，\(r<b\)）. 觀察這個等式： \(\because \gcd(a,b)\mid a, \gcd(a,b)\mid b\) \(\therefore \gcd(a,b)\mid r\) \(\therefore \gcd(a,b)\mid b,\gcd(a,b)\mid r\) \(\therefore \gcd(b,r)\ge\gcd(a,b)\) 同理有 \(\gcd(b,r)\mid a\)，是以 \(\gcd(a,b)\ge \gcd(b,r).\) \(\therefore \gcd(a,b)=\gcd(b,r).\) 證畢。

展現在代碼中就是可以遞歸求解。

邊界：當 \(b=0\) 時，說明上一步的 \(b\mid a\)，則上一步的 \(\gcd(a,b)=b\)，即目前這一步的 \(a\).

\(\text{Code}\)