余数定理

· · 个人记录

对于关于 x 的多项式 f(x)，我们研究 f(x) 除以一次多项式 (x-a) 的余数。

设 f(x)=g(x)(x-a)+r

（由多项式除法定义，余式次数小于除式次数，这里是常数）

则 x=a 时，f(a)=r

借此，我们得到了余数定理（或称余式定理）：

f(x) \bmod (x-a)=f(a)

由余式定理，我们可以得到因式定理：

(x-a)\mid f(x) \Longleftrightarrow f(a)=0

从 x+a 拓展到 ax+b(a\neq 0) 的任意一次多项式形式。

f(x) = q(x)(x-\frac{b}{a})+r

从中我们还知道：若 f(x) \bmod (ax+b) =r，则 f(x) \bmod k(ax+b) = r，这里 k 取全体实数都成立。这是一个重要的东西。由此我们可以证明一个重要的命题：

已知 a_1,a_2,...a_k 两两不同，若 f(x) \bmod (x-a_i)=r(1<=i<=n)，则 f(x) \bmod \prod_{i=1}^{k}(x-a_i)=r.

由此得到一个重要推论：

关于 $f(x)$ 模所有不同一次式之积的余式，这是一个有意思的问题。一般说来，如果给定 $k$ 个不同的一次因式 $(x-a_1),(x-a_2),...,(x-a_n)$ ，还有 $f(x)$ 模它们的余数 $r_1,r_2,...,r_n$，则 $f(x) \bmod \prod_{i=1}^{k}(x-a_i)

的结果是可以求出来的。不难发现上面的推论就是这里的一个极特殊情况。如果我们设余式为

g(x)=\alpha_{k-1}x^{k-1}+\alpha_{k-2}x^{k-2}+...+\alpha_{0}

（待定 k 个系数），然后由因式定理得 f(a_i)=g(a_i)=r_i，解 k 元一次方程组确定g(x).

最后，用余数定理和一次多项式，我们可以证明代数基本定理的一小部分：

对于一个一元 n 次方程 a_nx^n+...+a_1=0，在实数域内，它的解不会超过 n 个。

证明：令 f(x)=a_nx^n+...+a_1，且 f(x_1)=f(x_2)=...=f(x_n)=0，x_i 互不相同

则 \prod_{i=1}^n(x-x_i) 依旧是 f(x) 的因式。注意到 f(x) 和这个因式都是 n 次的，则只差一个系数，即有

f(x)=k(x-x_1)(x-x_2)...(x-x_n) (k\neq 0)

如果此时还有一个与所有 x_i 都不相同的 y，使得 f(y)=0，则 y 必须与一个 x_i 相等。矛盾。证毕。

数学水平太垃圾了，写的有误请见谅。最后膜一下用因式定理证明 FFT 的jsz神仙。