扩展欧几里得定理-扩展欧几里得定理

本指南将结合历年真题案例，完整解析该定理的推导过程、应用场景及核心技巧，确保读者能够从容应对各类竞赛与考试。

扩展欧几里得定理并非一个孤立的概念，它是数论中 Bezout 表示法（贝佐特表示）的直接应用。

• 基本形式：设 $a$ 与 $b$ 为两个整数，若 $d = text{gcd}(a, b)$，则存在一对整数 $x$ 和 $y$，使得 $ax + by = d$。这一等式揭示了线性组合的内在联系，即两个数的最大公约数可以通过它们自身的线性组合来表示。
• 唯一性与存在性：在满足 $x, y in mathbb{Z}$ 的条件下，若 $x_0$ 和 $y_0$ 是方程 $ax + by = d$ 的一组解，则所有可能的解 $x$ 和 $y$ 都具有固定的形式，即 $x = x_0 + frac{b}{d}n$，$y = y_0 - frac{a}{d}n$，其中 $n$ 为任意整数。
• 算法意义：这一结论将计算 gcd 的过程与求解不定方程的过程统一了起来。在计算机科学中，这等价于求解 $a x + b y = c$ 的齐次方程，是模逆运算求解的基础。

理解扩展欧几里得定理，必须清晰梳理其与传统欧几里得算法之间的逻辑链条。

• 传统欧几里得算法：通过反复用较大的数除以较小的数，能够求出 $text{gcd}(a, b)$。其核心步骤是：$r_{i-1} = a pm q_i times r_i$，其中 $r_i$ 是 $a$ 与 $r_{i-1}$ 的最大公约数。
• 扩展算法引入：在计算上述余数的过程中，我们巧妙地增加了变量。在步骤 $i$ 中，我们不仅求出余数 $r_i$，还额外计算出 $r_i$ 与 $r_{i-1}$ 的最大公约数 $d$ 的系数。
• 递推公式构建：设 $a_i = r_{i-1}$, $b_i = r_i$，则定义 $d_{i-1} = text{gcd}(a_i, b_i)$。扩展算法通过引入变系数 $x_i$ 和 $y_i$，使得 $a_i = x_i d_{i-1} + b_i y_i$，进而推导出 $d_i = x_{i-1} d_{i-1} + y_{i-1} d_i$，从而在每一步都获取了更全面的数学信息。

这一递推过程的数学严谨性在于，每一步新得到的系数都不是随机生成的，而是严格依赖于前一步的系数和当前的余数。这种结构使得我们能够反向追溯，最终将最终的 $x$ 和 $y$ 还原为 $a$ 和 $b$ 的原始表示。

为了更直观地掌握应用技巧，我们选取一个具体的题目进行深度剖析。假设题目要求计算 $text{gcd}(120, 234)$ 并求解方程 $120x + 234y = 12$。

• 第一步：执行传统欧几里得算法 $$ begin{aligned} 234 &= 1 times 120 + 114 \ 120 &= 1 times 114 + 6 \ 114 &= 19 times 6 + 0 end{aligned} $$ 由此可得 $text{gcd}(120, 234) = 6$。
• 第二步：使用扩展算法同步计算系数 我们在每一步记录系数 $x$ 和 $y$。
  1. 初始状态：$a_1 = 120, b_1 = 234$。由 $120 = 0 times 234 + 120$，得 $x_0 = 0, y_0 = 1$。
  2. 第一步：$234 = 1 times 120 + 114$。根据 $1 times 120 + 114 = 0 times 234 + 120$，得 $x_1 = 0, y_1 = 1$。 注意：此时 $x_1$ 是相对于 $234$ 的系数，需转化为相对于 $a$ 的系数。 实际上，标准写法是从 $a$ 开始推起，或者反向推导。我们采用反向推导法更直观：
  $6 = 120 - 114 = 120 - (234 - 120) = 2 times 120 - 1 times 234$。 由此得到 $x=2, y=-1$。

3. 继续推导方程 $120x + 234y = 12$ 的整数解。 由 $120x + 234y = 6 times 2$，将上式两边同时除以 6，得到 $20x + 39y = 2$。 我们继续运用扩展除法逻辑：
$2 = 20 - 18 = 20 - (39 - 2 times 20) = 3 times 20 - 1 times 39$。 代入系数得 $x=3, y=-1$。
• 第三步：验证与求解 将 $x=3, y=-1$ 代入 $120x + 234y = 12$，验证：$120 times 3 + 234 times (-1) = 360 - 234 = 12$。等式成立。

在实际的数论竞赛或工程应用题中，经常会遇到需要解同余方程 $ax equiv b pmod n$ 的情况。解决此类问题，核心在于利用扩展欧几里得定理求解 $ax + by = text{gcd}(a, n) = 1$ 这一恒等式。

• 逆序求解：当 $a$ 大于 $n$ 时，计算 $text{gcd}(a, n)$ 的扩展过程时，初始 $a$ 的系数可能很大。此时，我们只需将结果中的系数同时除以 $n$，即可得到模 $n$ 意义下的逆元。
• 同余方程形式：若 $text{gcd}(a, n) = 1$，并求得 $ax + ny = 1$，则 $ax equiv 1 pmod n$。方程 $ax equiv b pmod n$ 的解可以通过 $x = x_0 + k times n$ 的通式，结合通解公式 $x = x_0 + frac{n}{text{gcd}(a, n)}k$ 确定。

例如，若需解 $3x equiv 2 pmod 5$。首先计算 $text{gcd}(3, 5) = 1$。通过扩展算法，我们会得到 $3 times 2 + 5 times (-1) = 1$。
也是因为这些吧，原方程解为 $x equiv 2 times 2 pmod 5$，即 $x equiv 4 pmod 5$。这一技巧极大地简化了复杂的模运算计算。

在各类数学能力考核中，扩展欧几里得定理的考查往往隐蔽而灵活。它不仅仅是一个计算题，更是考察考生逻辑推理能力的重要环节。

• 题型辨析：识别题目是否为不定方程、同余方程或éz 系问题。若是，则优先考虑使用扩展算法直接得出整数解，而非先求 gcd。
• 解题路径：熟练掌握“辗转相除”与“逆推代换”的结合。平时练习中，应养成每一步都计算新系数的习惯，避免只算余数。
• 边界处理：当 $text{gcd}(a, n) neq 1$ 时，原方程 $ax equiv b pmod n$ 有解的充要条件是 $b$ 能被 $text{gcd}(a, n)$ 整除。若无解，则扩展算法将直接反映出这一矛盾。

掌握这一算法，不仅能提升你在数论部分的得分率，更是构建完备数学体系的关键一环。它在密码学中的 RSA 算法、在离散数学证明中的 Bezout 表示法，都有身影。

本指南通过对扩展欧几里得定理的深入剖析，希望助你厘清概念、掌握精髓。该方法论逻辑严密，步骤清晰，是解决各类数论问题的利器。在未来的学习中，请始终将“系数同步计算”作为重点，不断锤炼自己的数学直觉。期待你能够熟练运用此工具，在各类数学竞赛中取得优异成绩。