【輾轉相除法原理】在數學中，輾轉相除法（又稱歐幾里得算法）是一種用于求解兩個正整數最大公約數（GCD）的高效方法。該算法以古希臘數學家歐幾里得的名字命名，因其在《幾何原本》中的記載而聞名。其核心思想是通過反復用較小的數去除較大的數，直到余數為零，此時的除數即為兩數的最大公約數。
一、基本原理
輾轉相除法的基本原理基于以下數學定理：
> 設 $ a $ 和 $ b $ 是兩個正整數，且 $ a > b $，則：
>
> $$
> \gcd(a, b) = \gcd(b, a \mod b)
> $$
也就是說，兩個數的最大公約數等于其中較小的數與較大數除以較小數的余數的最大公約數。這一過程不斷重復，直到余數為零，此時的除數就是這兩個數的最大公約數。
二、算法步驟
1. 給定兩個正整數 $ a $ 和 $ b $，假設 $ a > b $。
2. 用 $ a $ 除以 $ b $，得到余數 $ r $。
3. 將 $ b $ 作為新的被除數，$ r $ 作為新的除數，重復步驟2。
4. 當余數為0時，當前的除數即為最大公約數。
三、示例說明
以 $ a = 48 $，$ b = 18 $ 為例，計算它們的最大公約數：
| 步驟 | 被除數 | 除數 | 商 | 余數 |
| 1 | 48 | 18 | 2 | 12 |
| 2 | 18 | 12 | 1 | 6 |
| 3 | 12 | 6 | 2 | 0 |
最終余數為0，因此最大公約數為 6。
四、總結對比
| 項目 | 內容說明 |
| 名稱 | 輾轉相除法 / 歐幾里得算法 |
| 用途 | 求兩個正整數的最大公約數（GCD） |
| 基本原理 | $ \gcd(a, b) = \gcd(b, a \mod b) $ |
| 算法步驟 | 反復用較小數去除較大數，直到余數為0 |
| 特點 | 高效、簡單、適用于所有正整數 |
| 應用場景 | 數論、密碼學、分數化簡、編程算法等 |
五、注意事項
- 該算法僅適用于正整數。
- 若其中一個數為0，則另一個數即為最大公約數。
- 在實際應用中，可以使用遞歸或循環實現該算法。
通過以上內容可以看出，輾轉相除法不僅在理論上有重要意義，在實際計算中也具有極高的實用價值。它簡潔明了，邏輯清晰，是數學和計算機科學中一個經典而重要的算法。
