C语言实现扩展欧几里得算法详解与代码

南乔

发布时间：2026-10-15| 6人浏览过

原创

扩展欧几里得算法不仅能计算两个整数的最大公约数（GCD），还能找到满足贝祖等式 $ax+by=gcd(a,b)$ 的整数解 $x$ 和 $y$。本文将深入解析该算法的数学原理，并提供标准的C语言实现代码，帮助开发者理解其在密码学、模运算等领域的关键作用。

问题描述与目标

给定两个整数 m 和 n（假设 m > n > 0），扩展欧几里得算法的目标是计算：

GCD(m, n)：m 和 n 的最大公约数，记为 d。
系数 a 和 b：使得 a*m + b*n = d 成立的整数对。

这个等式被称为 Bézout 恒等式。在计算机科学中，该算法常用于求解线性同余方程和计算模逆元，例如在 RSA 加密算法中求私钥。

算法原理推导

扩展欧几里得算法基于欧几里得算法的核心性质：GCD(m, n) = GCD(n, m % n)。我们通过递归或迭代的方式，逐步缩小问题的规模，并在回溯过程中计算出系数。

数学推导过程

基本情况：如果 n == 0，则 GCD(m, 0) = m。此时显然有 1 * m + 0 * 0 = m，即系数 a=1, b=0。
递归步骤：设 GCD(n, m % n) = d，且已求得满足 n * a' + (m % n) * b' = d 的系数 a' 和 b'。
代换整理：
- 我们知道 m % n = m - floor(m/n) * n。
- 代入原式：n * a' + (m - floor(m/n) * n) * b' = d。
- 展开重组：m * b' + n * (a' - floor(m/n) * b') = d。
对应关系：对比目标式 a * m + b * n = d，可得当前层的系数：
a = b'
b = a' - floor(m/n) * b'

执行流程说明

在非递归实现中，我们需要维护两组变量来追踪当前的系数变化，这相当于在模拟递归栈的回溯过程：

(a, b)：保存上一轮递归返回的系数。
(a', b')（文中称为 a1, b1）：当前正在计算的系数。
c, d：用于跟踪当前除数和余数的变量，初始化为 m, n。

C语言代码实现

以下提供两种实现方式：简洁的非递归版本和易于理解的递归版本。

第1步：非递归实现

非递归方法效率更高，避免了函数调用开销。通过不断更新余数和系数变量，最终当余数为0时停止。

复制代码代码如下:

void EGCD(int m, int n)
{
    int a, a1, b, b1, c, d, q, r, t;
    
    // 初始化：对应递归基 gcd(m,0)=m 时的系数 a1=1, b1=0; 以及下一层 a=0, b=1
    a1 = 1; b1 = 0; 
    a = 0; b = 1; 
    c = m; d = n;
    
    while (d != 0) {
        q = c / d;
        r = c % d;
        
        // 核心更新逻辑：利用辗转相除的性质更新系数
        // 这里的 t 用作临时变量交换值
        t = a1; a1 = a; a = t - q * a;
        t = b1; b1 = b; b = t - q * b;
        
        c = d; d = r;
    }
    
    // 输出结果: a*m + b*n = gcd(m,n)
    printf("%d * %d + (%d) * %d = %d\n", a, m, b, n, c);
}

第2步：递归实现

递归实现更贴近数学定义，逻辑清晰，适合理解算法本质。

复制代码代码如下:

// 返回值即为 GCD(m, n)，并通过指针返回系数 x, y
int ExtendedGCD(int m, int n, int *x, int *y)
{
    if (n == 0) {
        *x = 1;
        *y = 0;
        return m;
    }
    
    int x1, y1;
    int gcd = ExtendedGCD(n, m % n, &x1, &y1);
    
    *x = y1;
    *y = x1 - (m / n) * y1;
    
    return gcd;
}

使用示例与验证

假设输入 m = 30, n = 20：

最大公约数 GCD(30, 20) = 10。
根据算法，应存在 a*30 + b*20 = 10。
非递归代码可能输出：-1 * 30 + 2 * 20 = 10（注意：系数不唯一，-1和2是一组解，也可以是 1和-2 等）。

注意事项

数据类型溢出：当输入数值较大时，中间计算过程可能导致整数溢出，建议使用 long long 类型。
负数处理：标准扩展欧几里得算法通常针对正整数设计。若涉及负数，需先取绝对值处理，最后根据符号调整系数。
应用场景：除了求GCD，该算法最广泛的应用是求 a 关于 n 的乘法逆元（当 GCD(a, n) = 1 时），逆元即为代码输出的 a（需对 n 取模以确保为正）。