在數論和密碼學中，歐幾里得算法（Euclidean Algorithm）是一個古老而重要的算法，用于計算兩個整數的最大公約數（GCD）。

歐幾里得算法（更相減損法）

歐幾里得算法基于以下原理：兩個整數的最大公約數等于其中較小的數和兩數相除余數的最大公約數。用數學公式表示為：

當余數為0時，此時的除數就是最大公約數。

1. 用較大數除以較小數，得到余數
2. 用較小數除以余數，再次得到新的余數
3. 重復這個過程，直到余數為0
4. 此時的除數就是最大公約數

// 遞歸實現
int gcd_recursive(int a, int b) {
    if (b == 0) return a;
    return gcd_recursive(b, a % b);
}

// 迭代實現
int gcd_iterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

中國古代的更相減損術是中國古代數學著作《九章算術》中記載的一種求最大公約數的方法，成書于東漢時期（約公元1世紀）。《九章算術》的"方田"章中記載：

"約分術曰：可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。"

更相減損術的核心思想是：兩個數的最大公約數等于較小數與兩數差的最大公約數。用現代數學符號表示為：

當兩數相等時，這個相等的數就是最大公約數。減法實際上可以替換為除法取余（減到不能再減），這樣就接近現代使用的歐幾里得算法了。

歐幾里得算法的時間復雜度

其時間復雜度為 \(O(\log(\min(a, b)))\)。

可以使用數學知識證明（有難度），歐幾里得算法在計算 \(\gcd(a, b)\) 時，最多執行 \(2 \cdot \lfloor \log_2 b \rfloor + 1\) 次除法操作（最壞情況為當輸入為連續的斐波那契數時）。平均除法的次數是 \(\frac{12 \ln 2}{\pi^2} \ln n \approx 0.843 \ln n\)。

擴展歐幾里得算法

擴展歐幾里得算法不僅計算 \(\gcd(a, b)\)，還找到整數 \(x\) 和 \(y\)，使得滿足貝祖等式：

即讓 \(a\) 和 \(b\) "拼出" 其最大公約數。

在歐幾里得算法的每一步中，我們有：

• \(a = bq + r\)，其中 \(q\) 是商，\(r\) 是余數
• \(\gcd(a, b) = \gcd(b, r)\)

我們可以將余數 \(r\) 表示為：

• \(r = a - bq\)

在遞歸的返回過程中，我們利用這個關系來構造 \(x\) 和 \(y\)。

int extended_gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    
    int x1, y1;
    int gcd = extended_gcd(b, a % b, x1, y1);
    
    x = y1;
    y = x1 - (a / b) * y1;
    
    return gcd;
}

擴展歐幾里得算法可以用于求解形如 \(ax \equiv b \pmod{m}\) 的線性同余方程（也包括求解乘法逆元）。