多项式的四则运算
为方便后续研究关于多项式的各种高级运算，有必要在本文讨论一下多项式的四则运算和实现。其中，加法和减法互为逆运算，定义和实现也很简单。 乘法与加法构成分配率，也比较直观。除法并不是乘法的逆运算，它对多项式并不是封闭的，概念相对复杂一些。
1. 多项式的加减法
根据代数的定义，所有的多项式构成的集合是一个环。它有两个基本的运算，加法和乘法。这两个运算是封闭的，即任意两个多项式相加或者相乘，结果仍然是个多项式。
假设我们有两个多项式 \(\boldsymbol{a} = a_m x^m + \cdots + a_1 x + a_0 = \sum_{i=0}^m a_i x^i\) 和 \(\boldsymbol{b} = b_n x^n + \cdots + b_1 x + b_0 = \sum_{i=0}^n b_i x^i\)，不妨设 \(m < n\)，那么多项式的加法可以写成如下的形式:
$$ \begin{aligned} \boldsymbol{a} + \boldsymbol{b} & = (a_m x^m + \cdots + a_1 x + a_0) + (b_n x^n + \cdots + b_1 x + b_0) \\ & = b_n x^n + \cdots + (a_m + b_m) x^m + \cdots + (a_1 + b_1) x + (a_0 + b_0) \\ & = \sum_{i=0}^m(a_i+b_i)x^i + \sum_{i=m+1}^n b_i x^i \end{aligned} $$我们令 \(a_i = 0, i > m\)，那么加法的实现只需对应项的系数相加就可以了。 参见例程。
所有系数都是 0 的多项式被称为多项式的零元。关于加法，多项式\(\boldsymbol{a} = \sum_{i=0}^m a_i x^i\)的相反式为 \(-\boldsymbol{a} = \sum_{i=0}^m -a_i x^i\)。 \(\boldsymbol{a}\) 和它的逆 \(-\boldsymbol{a}\)相加即为零元。如果多项式满足关系 \(\boldsymbol{c} = \boldsymbol{a} + \boldsymbol{b}\)， 那么等号两侧同时加上 \(\boldsymbol{a}\) 或 \(\boldsymbol{b}\) 的相反式可得:
$$ \boldsymbol{c} + (-\boldsymbol{a}) = \boldsymbol{b}, \qquad \boldsymbol{c} + (-\boldsymbol{b}) = \boldsymbol{a} $$省略等号左侧的加号，多项式有如下形式的的减法。由于减法是利用加法运算定义的，所以它并不是一个独立的运算。
$$ \boldsymbol{c} - \boldsymbol{a} = \boldsymbol{b}, \qquad \boldsymbol{c} - \boldsymbol{b} = \boldsymbol{a} $$2. 多项式的乘法
我们仍然考虑多项式 \(\boldsymbol{a} = a_m x^m + \cdots + a_1 x + a_0 = \sum_{i=0}^m a_i x^i\) 和 \(\boldsymbol{b} = b_n x^n + \cdots + b_1 x + b_0 = \sum_{i=0}^n b_i x^i\)，不妨设 \(m < n\)。根据实数乘法分配率，我们可将 \(\boldsymbol{a} \cdot \boldsymbol{b}\) 展开如下:
$$ \begin{aligned} \boldsymbol{a} \cdot \boldsymbol{b} & = (a_m x^m + \cdots + a_1 x + a_0) \cdot (b_n x^n + \cdots + b_1 x + b_0) \\ & = (a_m b_n) x^{m+n} + (a_{m-1} b_{n} + a_m b_{n-1}) x^{m+n-1} + \cdots + (a_1 b_0 + a_0 b_1) x + a_0 b_0 \end{aligned} $$根据上式可知，\(\boldsymbol{c} = \boldsymbol{a}\cdot \boldsymbol{b}\) 展开后共有 \(m+n\) 项，其中 \(k\) 次项的系数为:
$$ \begin{aligned} c_k & = a_k b_0 + a_{k-1} b_1 + \cdots + a_1 b_{k-1} + a_0 b_k \\ & = \Pi_{i + j = k} a_i b_j \end{aligned} $$根据上式，我们可以在一个双层嵌套循环里面完成系数累加。 参见例程。 对于乘法，存在单位元 1，使得任意多项式与之相乘都是都是其本身。 但大多数多项式都不存在逆。所以我们也不能像实数那样找到一个除法作为多项式乘法的逆运算。
3. 多项式的带余除法
虽然我们不能写出可以作为多项式乘法逆运算的除法，但我们可以像整数的除法那样通过商和余数来定义多项式的除法。 设 \(\boldsymbol{a},\boldsymbol{b}\) 是任意两个多项式，并且 \(\boldsymbol{b} \neq 0\)。那么必然存在唯一的一对多项式 \(\boldsymbol{q}, \boldsymbol{r}\)，使得:
$$ \begin{equation}\label{f1} \boldsymbol{a} = \boldsymbol{q} \boldsymbol{b} + \boldsymbol{r} \end{equation} $$其中，\(\boldsymbol{r}\) 要么为 \(0\)，要么它是一个比 \(\boldsymbol{b}\) 次数小的多项式。我们称 \(\boldsymbol{q}\) 为商式，\(\boldsymbol{r}\) 为余式。 \(\boldsymbol{a}\) 和 \(\boldsymbol{b}\) 分别为被除式和除式。
若多项式 \(\boldsymbol{a}\) 的次数小于 \(\boldsymbol{b}\) 的次数。那么取 \(\boldsymbol{q} = 0\), \(\boldsymbol{r} = \boldsymbol{a}\) 可以直接写出上面式(\(\ref{f1}\))的形式。 若 \(\boldsymbol{a}\) 的次数不小于 \(\boldsymbol{b}\) 的次数，不妨设它们具有如下的形式:
$$ \begin{aligned} \boldsymbol{a} & = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0 \\ \boldsymbol{b} & = b_m x^m + b_{m-1} x^{m-1} + \cdots + b_1 x + b_0 \\ \end{aligned} $$我们从 \(\boldsymbol{a}\) 中减去 \(a_nb_m^{-1} x^{n-m} \cdot \boldsymbol{b}\)，即可消除 \(\boldsymbol{a}\) 的最高次项，得到一个多项式 \(\boldsymbol{\alpha_1}\):
$$ \begin{equation}\label{f2} \boldsymbol{\alpha_1} = \boldsymbol{a} - a_nb_m^{-1} x^{n-m} \cdot \boldsymbol{b} \end{equation} $$若 \(\boldsymbol{\alpha_1} \neq 0\) 并且其次数 \(n_1 ≥ m\)。记 \(\boldsymbol{\alpha_1}\) 的最高次项系数为 \(\alpha_{1,n_1}\)。 那么我们就对 \(\boldsymbol{\alpha_1}\) 执行相同的操作，消除其最高此项，有:
$$ \boldsymbol{\alpha_2} = \boldsymbol{\alpha_1} - \alpha_{1,n_1}b_m^{-1} x^{n_1-m} \cdot \boldsymbol{b} $$如此重复下去，我们会得到一系列次数递减的多项式 \(\boldsymbol{\alpha_1}, \boldsymbol{\alpha_2}, \cdots, \boldsymbol{\alpha_k}\)，最后的 \(\boldsymbol{\alpha_k}\) 的次数 \(n_k < m\)， 具有形式:
$$ \boldsymbol{\alpha_k} = \boldsymbol{\alpha_{k-1}} - \alpha_{k-1,n_{k-1}}b_m^{-1} x^{n_{k-1}-m} \cdot \boldsymbol{b} $$ 将这些多项式逐级代入到式(\(\ref{f2}\))，有: $$ \begin{equation}\label{f3} \begin{aligned} \boldsymbol{a} & = a_nb_m^{-1} x^{n-m} \cdot \boldsymbol{b} + \boldsymbol{\alpha_1} \\ & = a_nb_m^{-1} x^{n-m} \cdot \boldsymbol{b} + \alpha_{1,n_1}b_m^{-1} x^{n_1-m} \cdot \boldsymbol{b} + \boldsymbol{\alpha_2} \\ & = a_nb_m^{-1} x^{n-m} \cdot \boldsymbol{b} + \alpha_{1,n_1}b_m^{-1} x^{n_1-m} \cdot \boldsymbol{b} + \cdots + \alpha_{k-1,n_{k-1}}b_m^{-1} x^{n_{k-1}-m} \cdot \boldsymbol{b} + \boldsymbol{\alpha_k} \\ & = \underbrace{\left[a_nb_m^{-1} x^{n-m} + \alpha_{1,n_1}b_m^{-1} x^{n_1-m} + \cdots + \alpha_{k-1,n_{k-1}}b_m^{-1} x^{n_{k-1}-m}\right]}_{\boldsymbol{q}} \cdot \boldsymbol{b} + \underbrace{\boldsymbol{\alpha_k}}_{\boldsymbol{r}} \end{aligned} \end{equation} $$上式实际上就是所谓的多项式长除法，根据这个推导过程，我们直接给出一个实现。 参见例程。 很多材料里面喜欢用我们在中小学熟悉的除法竖式来描述这个过程，非常直观，但个人感觉转换成程序语言有点抽象。
长除法很通用，给定任意两个多项式，我们都可以通过上述长除法得到商式和余式。但是在很多场合下我们的除式都是这种形式 \(\boldsymbol{b} = x - x_0\) 的， 此时，长除法的效率就显得比较低了。这种情况下，上一节中介绍的收缩(deflation)约化技术更适用。 它也被称为综合除法(Synthetic Divide)。 参见例程。