C# 實作輾轉相除法 (歐幾里得算法) 及擴展算法：求最大公約數與貝茲係數

輾轉相除法 (標準 GCD)

求兩正整數 a, b 最大公約數 (GCD)。核心遞推：gcd(a, b) = gcd(b, a % b)，直到餘數為 0。

C# 實作

public static int Gcd(int a, int b)
{
    a = Math.Abs(a);
    b = Math.Abs(b);
    while (b != 0)
    {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

// 遞歸版本
public static int GcdRecursive(int a, int b) => b == 0 ? Math.Abs(a) : GcdRecursive(b, a % b);

擴展歐幾里得算法 (Extended GCD)

除求 GCD 外，並求出整數 x, y 使 a*x + b*y = gcd(a, b) (貝茲等式)。應用於模逆元、中國剩餘定理、RSA 金鑰生成。

C# 實作 (迭代版，避免遞歸堆疊溢位)

public static int ExtendedGcd(int a, int b, out int x, out int y)
{
    // 初始係數
    int x0 = 1, y0 = 0; // a*1 + b*0 = a
    int x1 = 0, y1 = 1; // a*0 + b*1 = b

    while (b != 0)
    {
        int q = a / b;
        int r = a % b;

        // 更新係數
        int x2 = x0 - q * x1;
        int y2 = y0 - q * y1;

        // 滾動變數
        a = b; b = r;
        x0 = x1; y0 = y1;
        x1 = x2; y1 = y2;
    }

    x = x0;
    y = y0;
    return a; // 此時 a 為 gcd
}

驗證範例

int x, y;
int gcd = ExtendedGcd(1769, 551, out x, out y);
// 1769 * x + 551 * y = gcd
Console.WriteLine($"{x} * 1769 + {y} * 551 = {x * 1769 + y * 551} (gcd = {gcd})");
// 輸出: -31 * 1769 + 100 * 551 = 29 (gcd = 29)

應用：模逆元

若 gcd(a, m) = 1，則 x 為 a 模 m 的逆元 (即 a * x ≡ 1 (mod m))。

public static int ModInverse(int a, int m)
{
    int x, y;
    int g = ExtendedGcd(a, m, out x, out y);
    if (g != 1) throw new ArgumentException("模逆元不存在 (不互質)");
    return (x % m + m) % m; // 確保正數
}

效能與邊界測試

※ 表格中手算係數僅供參考，請以程式碼實測為準。

結語

輾轉相除法 O(log min(a,b)) 極快，擴展算法同樣複雜度下額外獲得貝茲係數，是數論、密碼學、演算法競賽的基石工具。C# 實作時注意 out 參數傳回係數、處理負數輸入、避免遞歸深度過大 (迭代版更安全)。