附录1 - 多项式的带余除法

设 $f(x), g(x)$ 是域 $F$ 上的多项式，且 $g(x) \neq 0$。则存在唯一的多项式 $q(x)$（商式）和 $r(x)$（余式），使得：

$f(x) = q(x)g(x) + r(x)$    其中 $r(x) = 0$ 或者 $\deg(r) < \deg(g)$

($\deg$ 表示多项式的次数)

存在性的证明，其实就是给出一个一定会停止的除法算法。

从被除式 $f(x)$ 开始，把“当前还没有处理完的部分”称为当前余式。第一轮的当前余式就是 $f(x)$。如果当前余式的次数已经小于除式 $g(x)$ 的次数，就直接停止；否则，用当前余式的最高次项除以除式的最高次项，得到一个部分商式。这个操作本质上就是把最高次项的 系数相除，次数相减（注：由于要做系数的除法，所以要求系数的取值范围必须构成一个 数域，即每一个非 $0$ 系数都有唯一的乘法逆元。这就是为什么谈论多项式时会说 某某域上的多项式，指的就是系数的数域）。

得到部分商式后，用当前余式减去“部分商式乘以除式”，就能正好消掉当前余式的最高次项，得到下一轮新的余式。于是每做一轮，余式的次数都会严格下降，或者余式直接变成 $0$。

只要新的余式的次数仍然 $\ge$ 除式的次数，就继续重复这个过程；最终必然会停在“余式为 $0$”或“余式次数小于除式次数”的状态。停止时留下的余式就是最终的 $r(x)$，而每一轮得到的部分商式累加起来，就是最终的商式 $q(x)$。这就证明了商式和余式至少是存在的。

下面的竖式，就是把这段算法画出来：左边是除式，类似“根号”里面的是被除式和每一轮的当前余式，上方逐步累加的是商式，最底下停止时留下的是余式。

这个竖式里的每一步都在做同一件事：用当前余式的最高次项，除以除式 $x - 3$ 的最高次项 $x$。每次横线下面出现的新一行，就是下一轮的当前余式。

第一步：当前最高次项是 $x^3$，所以部分商式是 $x^3 \div x = x^2$。

$(x - 3)x^2 = x^3 - 3x^2$

用原来的被除式减去它，得到第一次余式：

$(x^3 - 2x^2 + 0x + 3) - (x^3 - 3x^2) = x^2 + 0x + 3$

第二步：当前余式的最高次项是 $x^2$，所以新的部分商式是 $x^2 \div x = x$。

$(x - 3)x = x^2 - 3x$

继续相减，得到第二次余式：

$(x^2 + 0x + 3) - (x^2 - 3x) = 3x + 3$

第三步：当前余式的最高次项是 $3x$，所以新的部分商式是 $3x \div x = 3$。

$(x - 3)3 = 3x - 9$

继续相减，得到最后的余式：

$(3x + 3) - (3x - 9) = 12$

因为最后的余式 $12$ 的次数是 $0$，已经小于除式 $x - 3$ 的次数 $1$，所以除法停止。上方的商式是：

$q(x) = x^2 + x + 3$

最底下的余式是：

$r(x) = 12$

因此：

$x^3 - 2x^2 + 0x + 3 = (x - 3)(x^2 + x + 3) + 12$

多项式的系数取值范围必须是一个“数域”，但是多项式的 $x$ 的取值范围，并不要求也是一个数域，因为多项式并不要求对除法封闭（即两个多项式相除不要求也是一个多项式，只有整除的情况才会是）。因此 $x$ 的取值范围只要求是一个 包含了系数域 的 环。包含系数域是因为任意系数都可以和 $x$ 进行四则运算，“环”是指多项式只需要对乘法和加法封闭。

假设存在两组结果 $(q_1(x), r_1(x))$ 和 $(q_2(x), r_2(x))$ 都满足条件，即：
$f(x) = q_1(x)g(x) + r_1(x)$  且
$f(x) = q_2(x)g(x) + r_2(x)$
两式相减可得：
$0 = [q_1(x) - q_2(x)]g(x) + [r_1(x) - r_2(x)]$ ，移项得到：
$[q_1(x) - q_2(x)]g(x) = r_2(x) - r_1(x)$
此时我们进行反证：
假设 $q_1(x) \neq q_2(x)$，那么 $q_1(x) - q_2(x) \neq 0$。
根据多项式乘法的次数性质，等式左边的次数为：
$\deg([q_1 - q_2]g) = \deg(q_1 - q_2) + \deg(g) \ge \deg(g)$
然而，对于等式右边，因为 $r_1$ 和 $r_2$ 的次数都严格小于 $g$ 的次数，所以它们的差 $r_2(x) - r_1(x)$ 的次数也必定严格小于 $g$ 的次数（或者为 $0$）：
$\deg(r_2 - r_1) < \deg(g)$
这导致等式左右两边的次数矛盾！因此，假设不成立，必须有 $q_1(x) - q_2(x) = 0$，即 $q_1(x) = q_2(x)$。代回原式即可得到
$r_2(x) - r_1(x) = 0$，即 $r_1(x) = r_2(x)$。
结论：商式和余式是唯一的。