给定两个多项式，求解扩展欧几里得算法中的系数

咱们已经明确两个目标多项式：

• $a(x) = 3x^4 -4x^3 -11x^2 +4x +9$
• $b(x) = 3x^3 +5x^2 +x -1$

通过欧几里得算法已经算出它们的最大公因式是1，现在咱们就用扩展欧几里得算法，一步步推导出满足 $a(x)u(x) + b(x)v(x) = 1$ 的系数多项式 $u(x)$ 和 $v(x)$。

先回顾欧几里得算法的除法步骤 #

先把已知的除法过程转换成多项式等式，方便后续倒推：
$$
a(x) = b(x)(x - 3) + 3x^2 + 8x + 6 \tag{1}
$$
$$
b(x) = (3x^2 + 8x + 6)(x - 1) + 3x + 5 \tag{2}
$$
$$
3x^2 + 8x + 6 = (3x + 5)(x + 1) + 1 \tag{3}
$$

从余数1开始倒推 #

从最后一步的等式(3)入手，把余数1用前两个多项式表示：
$$
1 = (3x^2 + 8x + 6) - (3x + 5)(x + 1)
$$

接下来用等式(2)把 $3x + 5$ 替换成 $b(x) - (3x^2 + 8x + 6)(x - 1)$，代入上式：
$$
\begin{align*}
1 &= (3x^2 + 8x + 6) - \left[ b(x) - (3x^2 + 8x + 6)(x - 1) \right](x + 1) \
&= (3x^2 + 8x + 6) - b(x)(x + 1) + (3x^2 + 8x + 6)(x^2 - 1) \
&= (3x^2 + 8x + 6) \cdot x^2 - b(x)(x + 1)
\end{align*}
$$

再用等式(1)把 $3x^2 + 8x + 6$ 替换成 $a(x) - b(x)(x - 3)$，继续代入：
$$
\begin{align*}
1 &= \left[ a(x) - b(x)(x - 3) \right]x^2 - b(x)(x + 1) \
&= a(x)x^2 - b(x)(x^3 - 3x^2) - b(x)(x + 1) \
&= a(x)x^2 - b(x)(x^3 - 3x^2 + x + 1)
\end{align*}
$$

这样咱们就得到了最终的系数多项式：

• $u(x) = x^2$
• $v(x) = -x^3 + 3x^2 - x - 1$

代入原式验证的话，确实会得到结果1，完全符合要求。

用表格展示直观迭代过程 #

如果喜欢更清晰的迭代记录方式，可以用表格跟踪每一步的多项式和对应系数：

表格最后一行就是咱们要找的最终结果~

内容的提问来源于stack exchange，提问作者teco2al