扩展欧几里得算法详解（Java语言实现贝祖等式与最大公约数的线性组合）

为什么需要扩展欧几里得算法？

该算法在以下场景中非常有用：

• 求解模线性方程（如 ax ≡ 1 (mod m)，即求模逆元）
• RSA加密算法中的密钥生成
• 中国剩余定理的实现
• 判断两个数是否互质，并找出其线性组合

Java实现扩展欧几里得算法

我们可以通过递归或迭代方式实现。下面是一个清晰的递归版本，并封装在一个类中：

public class ExtendedGCD {        // 存储结果的内部类    static class Result {        long gcd;        long x;        long y;                Result(long gcd, long x, long y) {            this.gcd = gcd;            this.x = x;            this.y = y;        }    }        // 扩展欧几里得算法（递归实现）    public static Result extendedGcd(long a, long b) {        if (b == 0) {            return new Result(a, 1, 0);        }                Result prev = extendedGcd(b, a % b);        long gcd = prev.gcd;        long x = prev.y;        long y = prev.x - (a / b) * prev.y;                return new Result(gcd, x, y);    }        // 测试方法    public static void main(String[] args) {        long a = 30;        long b = 20;        Result res = extendedGcd(a, b);                System.out.println("gcd(" + a + ", " + b + ") = " + res.gcd);        System.out.println(a + " * " + res.x + " + " + b + " * " + res.y + " = " + res.gcd);        // 验证：30*1 + 20*(-1) = 10    }}

代码说明：

• Result 类用于同时返回 gcd、x、y 三个值。
• 递归终止条件：当 b == 0 时，gcd 为 a，且 x = 1, y = 0。
• 递归关系：假设已知 gcd(b, a % b) = g = b * x1 + (a % b) * y1，通过代数变换可得当前的 x 和 y。

运行结果示例

运行上述代码，输出如下：

gcd(30, 20) = 1030 * 1 + 20 * -1 = 10

常见问题解答

Q：x 和 y 是唯一的吗？

A：不唯一。但扩展欧几里得算法会给出其中一组特解。

Q：负数能处理吗？

A：可以。Java 的 % 运算符对负数也有效，但建议传入非负数以避免混淆。可在调用前取绝对值，并根据符号调整结果。

总结

通过本教程，你已经掌握了扩展欧几里得算法的核心思想及其在Java语言中的实现。它不仅能高效求出最大公约数，还能解出贝祖等式中的系数，是学习密码学和算法设计的重要基石。动手试试吧，修改 a 和 b 的值，观察不同的 x 和 y 如何满足等式！

关键词回顾：扩展欧几里得算法、Java实现扩展欧几里得、贝祖等式求解、最大公约数与线性组合