經典算法實現：擴展歐幾里得算法求模逆（C語言完整代碼）

作者：俠客行

算法原理

擴展歐幾里得算法求解 ax + by = gcd(a,b)，並可推導模逆：

• 若 gcd(a,n) = 1，則 ax ≡ 1 (mod n) 有解
• 方程化為 ax + ny = 1，求得 x 即為 a 模 n 的逆元

完整 C 語言實現

#include <stdio.h>

// 擴展歐幾里得算法：求解 ax + by = d
void exgcd(int a, int b, int &d, int &x, int &y) {
    if (b == 0) {           // 基例：b=0 時 a=d, x=1, y=0
        d = a; x = 1; y = 0;
        return;
    }
    exgcd(b, a % b, d, y, x);  // 遞歸：參數交換 x,y 利用回溯更新
    y -= x * (a / b);          // 回溯更新 y
}

// 求模逆：a * x ≡ 1 (mod n)
int modInverse(int a, int n) {
    int d, x, y;
    exgcd(a, n, d, x, y);
    if (d != 1) return -1;           // 不互質，無逆元
    x = x % n;
    if (x < 0) x += n;               // 確保正數結果
    return x;
}

int main() {
    int a, b;
    printf("輸入兩個正整數 (a < b):\n");
    scanf("%d%d", &a, &b);
    
    int inv = modInverse(a, b);
    if (inv == -1)
        printf("a 與 b 不互質，不存在模逆元\n");
    else
        printf("%d 模 %d 的逆元為：%d\n", a, b, inv);
    
    return 0;
}

關鍵點解析

1. 遞歸參數交換：`exgcd(b, a%b, d, y, x)` 將 x,y 位置互換，利用回溯自然更新係數
2. 回溯更新公式：`y -= x * (a/b)` 對應恆等式變換
3. 模逆存在性：僅當 gcd(a,n)=1 時存在
4. 結果正規化：`(x%n+n)%n` 確保輸出 [0, n-1] 範圍內最小正整數

運行示例

輸入 3 26 → 輸出 3 模 26 的逆元為 9（驗證：3×9=27≡1 mod 26）

應用場景

• RSA 加密私鑰生成
• 同餘方程求解
• 中國剩餘定理計算
• 有限域運算