主要内容

高等代数: 多项式与线性代数

1.2 带余除法与整除

上一节中我们介绍了多项式的加法、减法和乘法三种运算的定义,其中减法是作为加法逆运算引入的。多项式乘法的逆运算——除法——并不是普遍可行的,类似于整数集内除法也不是普遍可行的一样。与整数集上的带余除法一样,本节中我们给出多项式的带余除法,并利用多项式带余除法给出两个多项式是否有整除关系的判定方法。

子节 1.2.1 带余除法

我们先来看一个具体的例子。

1.2.1.

\begin{equation*} f(x) = 3x^4-4x^3+5x-1, \end{equation*}
\begin{equation*} g(x) = x^2 -x +1, \end{equation*}
求多项式\(q(x),r(x)\)使得
\begin{equation*} f(x) = q(x)g(x)+r(x), \end{equation*}
\(\deg{r(x)} \)严格小于 \(\deg g(x)\)
解答.
类似于整数求商和余数的方法,我们可以按下面的计算格式来实现多项式带余除法:
\begin{equation*} \begin{array}{rrr|rrrrr|lll} x^2 &-x &+1 & 3x^4 & -4x^3 & &+5x &-1 & & & \\ & & & 3x^4 & -3x^3 & +3x^2 & & & 3x^2 & & \\\hline & & & & -x^3 & -3x^2 &+5x &-1 & & & \\ & & & & -x^3 & +x^2 & -x & & & -x & \\\hline & & & & & -4x^2 &+6x & -1& & &\\ & & & & & -4x^2 &+4x & -4& & &-4\\\hline & & & & & & 2x & -3& 3x^2 &-x &-4 \end{array} \end{equation*}
\(q(x)=3x^2-x-4\)\(r(x) = 2x-3\),则
\begin{equation*} \deg r(x)=1 < 2 =\deg g(x), \end{equation*}
且容易验证
\begin{equation*} f(x)=q(x)g(x)+r(x). \end{equation*}
观察上面的计算过程:每次我们都是用 \(g(x)\)的倍式消掉前面多项式的最高次项,新获得的多项式次数至少降低1。到最后一行过程停止,原因是前面的多项式次数已经严格小于\(g(x)\)的次数。总结这个过程并一般化,我们有如下定理。

证明.

先证明存在性。接下来按次数进行分类讨论,记\(\deg g(x)=m\)。注意到\(g(x)\ne 0\),所以 \(m\ge 0 \)
情形1:\(m=0\)。此时\(g(x)=b_0\neq 0\)。于是,
\begin{equation*} f(x)=g(x)\left[\frac{1}{b_0}f(x)\right]+0, \end{equation*}
\(q(x)=\left[\frac{1}{b_0}f(x)\right] \)\(r(x)=0\), 其中\(\deg 0 = -\infty <\deg g(x)=0\)
情形2:\(m > 0\),且\(\deg f(x)<m\)。此时
\begin{equation*} f(x)=g(x) 0+f(x), \end{equation*}
\(q(x)= 0,\ r(x)=f(x) \), 其中\(\deg f(x)<m=\deg g(x)\)
情形3:\(m>0\),且\(\deg f(x)\geq m\)。对被除式的次数\(n\)作数学归纳法。假设对于次数小于\(n\)的被除式存在性命题成立,以下考虑\(n\)次多项式\(f(x)\),其中\(n\geq m\)。设
\begin{equation*} f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0, \end{equation*}
\begin{equation*} g(x)=b_mx^m+b_{m-1}x^{m-1}+\cdots+b_0, \end{equation*}
其中\(a_n\ne 0,b_m\ne 0\)。令
\begin{equation} f_1(x)=f(x)-g(x)\left(\frac{a_n}{b_m}x^{n-m}\right),\tag{1.2.1} \end{equation}
\(\deg f_1(x)<n\)。根据归纳假设,存在\(q_1(x),r_1(x)\in\F[x]\),使得
\begin{equation} f_1(x)=g(x)q_1(x)+r_1(x),\tag{1.2.2} \end{equation}
其中\(\deg r_1(x)<\deg g(x)\)。将 (1.2.2) 代入(1.2.1),得
\begin{equation*} \begin{array}{ccl} f(x)& = & f_1(x)+g(x)\left(\frac{a_n}{b_m}x^{n-m}\right)\\ & = & g(x)\left[q_1(x)+\frac{a_n}{b_m}x^{n-m}\right]+r_1(x). \end{array} \end{equation*}
\(q(x)=q_1(x)+\frac{a_n}{b_m}x^{n-m},r(x)=r_1(x)\),可知结论成立。
下面证明唯一性:设存在\(q(x),r(x),q_0(x),r_0(x)\in\F[x]\),使得
\begin{equation*} f(x)=g(x)q(x)+r(x),\ f(x)=g(x)q_0(x)+r_0(x), \end{equation*}
其中\(\deg r(x)<\deg g(x),\deg r_0(x)<\deg g(x)\)。则
\begin{equation} g(x)\left[q(x)-q_0(x)\right]=r_0(x)-r(x).\tag{1.2.3} \end{equation}
假如\(q(x)\neq q_0(x)\),则\(\deg \left(q(x)-q_0(x)\right)\geq 0\)。由 (1.2.3)
\begin{equation*} \deg\left[r_0(x)-r(x)\right]=\deg g(x)+\deg \left[q(x)-q_0(x)\right]\geq \deg g(x). \end{equation*}
\begin{equation*} \deg\left[r_0(x)-r(x)\right]\leq\max\{\deg r_0(x),\deg r(x)\}< \deg g(x), \end{equation*}
矛盾,因此\(q(x)=q_0(x)\)。从而
\begin{equation*} r_0(x)-r(x)=g(x)\left[q(x)-q_0(x)\right]=0, \end{equation*}
\(r(x)=r_0(x)\)
定理 1.2.2 中的 \(q(x)\) 称为 \(g(x)\)\(f(x)\)商式\(r(x)\)称为 余式
带余除法定理的叙述中虽然出现了数域 \(\F\),但数域\(\F\)事实上与带余除法的结果无关。举例来说,例 1.2.1中的 \(f(x),g(x)\)都既可以看成是有理系数多项式集\(\Q[x]\)中的多项式,也可以看成是\(\R[x]\)中的多项式。无论哪一种看法,都不会改变商式和余式的计算结果。我们有下面一个一般的结论。

证明.

\(\F,\K\)是两个数域,且\(\F\subseteq\K\)。若\(f(x),g(x)\in\F[x]\),且\(g(x)\neq 0\),则\(f(x),g(x)\in\K[x]\)。在\(\F[x]\)中用带余除法,存在\(q_\F(x),r_\F(x)\in\F[x]\),使得
\begin{equation*} f(x)=g(x)q_\F(x)+r_\F(x), \end{equation*}
\(\deg r_\F(x) <\deg g(x)\)。在\(\K[x]\)用带余除法,存在\(q_\K(x),r_\K(x)\in\K[x]\),使得
\begin{equation*} f(x)=g(x)q_\K(x)+r_\K(x), \end{equation*}
\(\deg r_\K(x)< \deg g(x)\)。由\(\F\subseteq \K\)可知\(q_\F(x),r_\F(x)\in\K[x]\)。因此等式
\begin{equation*} f(x)=g(x)q_\F(x)+r_\F(x) \end{equation*}
\(\K[x]\)中也成立。由\(\K[x]\)中带余除法的唯一性,得\(q_\F(x)=q_\K(x)\)\(r_\F(x)=r_\K(x)\)
需要提醒的是带余除法定理中的条件 \({\deg r(x)}{\color{red}{<}}\deg g(x) \)特别重要,这个条件保证了商式和余式的唯一性。当\(g(x)\)是一个一次多项式时,我们有下面的结论。

证明.

根据带余除法( 定理 1.2.2 ),存在唯一的\(g(x)\in \F[x],r\in\F\),使得
\begin{equation*} f(x)=(x - b) g(x)+ r. \end{equation*}
\(x\)\(b\)代入,得\(f(b)=r\)。因此存在唯一的\(g(x)\in\mathbb{F}[x]\),使得
\begin{equation*} f(x)=(x - b) g(x)+ f(b). \end{equation*}

子节 1.2.2 整除

带余除法结果中余式为0有特殊重要的意义,此时\(f(x)=q(x)g(x)\)。我们引入如下术语。

定义 1.2.5.

\(f (x)\)\(g(x)\in\mathbb{F}[x]\)。若存在\(h(x)\in\mathbb{F}[x]\),使得
\begin{equation*} f (x) = g(x) h(x) , \end{equation*}
则称\(g(x)\)\(f(x)\)因式,或\(f(x)\)\(g(x)\) 整除,或\(g(x)\)整除\(f(x)\),记为\(\blue{g(x)|f (x)}\)。否则称\(g(x)\)不整除\(f(x)\),记为 \(\blue{g(x)\nmid f(x)}\)
根据定义,可以知道下面一个常用结论的正确性。

1.2.7.

\(a,b,c\)适合什么条件时,有\(x^2+ax+1\mid x^4+bx^2+c\)?。
解答.
根据带余除法,
\begin{equation*} x^4+bx^2+c=\left(x^2+ax+1\right)q(x)+r(x), \end{equation*}
其中
\begin{equation*} q(x)=x^2-ax+a+b^2-1, \end{equation*}
\begin{equation*} r(x)=a\left(2-a-b^2\right)x+c+1-a^2-b. \end{equation*}
因而\(x^2+ax+1\mid x^4+bx^2+c\)当且仅当
\begin{equation*} \left\{\begin{matrix} a\left(2-a-b^2\right)=0,\\ c+1-a^2-b=0, \end{matrix}\right. \end{equation*}
\begin{equation*} \left\{\begin{array}{l} a=0,\\ b=c+1 \end{array}\right.\mbox{或}\left\{\begin{array}{l} a^2+b=2,\\ c=1. \end{array}\right. \end{equation*}
对于被一次因式整除这种特殊情形,有下面一个简单的推论。

1.2.9.

\(x-a\left|f(x^n)\right.\),证明:\(x^n-a^n\left|f(x^n)\right.\)
解答.
\(x-a| f(x^n)\),所以由 推论 1.2.8\(f(a^n)=0\)。由此推出
\begin{equation*} x-a^n| f(x), \end{equation*}
即存在\(g(x)\in\mathbb{F}[x]\),使得
\begin{equation*} f(x)=\left(x-a^n\right)g(x), \end{equation*}
进而存在\(g(x^n)\in\mathbb{F}[x]\),使得
\begin{equation*} f(x^n)=\left(x^n-a^n\right)g(x^n). \end{equation*}
因此\(x^n-a^n\left|f(x^n)\right.\)
容易验证整除满足以下性质:设\(f(x)\)\(g(x)\)\(h(x)\in \mathbb{F}[x]\),则
  1. 反身性:\(f(x)|f(x)\)
  2. 传递性:\(f(x)|g(x)\)\(g(x)|h(x)\),则\(f(x)|h(x)\)
  3. 互伴性:\(f(x)|g(x)\)\(g(x)|f(x)\),则存在\(0\ne c\in \mathbb{F}\),使得
    \begin{equation*} f(x)=cg(x), \end{equation*}
    此时称\(f(x)\)\(g(x)\)相伴多项式 ,记作\(f(x)\sim g(x)\)
把与一个多项式\(f(x)\in \F[x]\) 相互整除的所有多项式放在一起构成一个集合,称这样的集合为 \(f(x)\)相伴多项式类,记为 \(\blue{[f(x)]} \),即
\begin{equation*} \blue{[f(x)]} = \{g(x)| g(x)\in \F[x], f(x)\sim g(x)\}. \end{equation*}
可以验证:
\begin{equation*} f(x)\sim g(x) \Leftrightarrow [f(x)] = [g(x)]. \end{equation*}
举例来说:0多项式的相伴多项式类只有一个0多项式,即
\begin{equation*} [0]=\{0\}; \end{equation*}
非0常数多项式c的相伴多项式类为所有的非0常数,即
\begin{equation*} [c]=\F\backslash \{0\},\quad (c\ne 0); \end{equation*}
对于正整数\(n\),单项式\(x^n\)的相伴多项式类为所有的\(n\)次单项式,即
\begin{equation*} [x^n]=\{cx^n| c\in \F,c\ne 0\}. \end{equation*}
根据整除的性质,相伴多项式类中的多项式之间相差的就是一个非0常数数乘。为了简便,在讨论非0多项式的相伴多项式类相关问题时,通常我们会选取首项系数为1的多项式作为这一类多项式的代表。在一个相伴多项式类中,首1多项式是唯一的。
关于整除,下面的命题也是一个常用结论。

证明.

由已知\(f(x)\mid g(x),f(x)\mid h(x)\)得,存在\(q(x),s(x)\in\F[x]\),使得
\begin{equation*} g(x)=f(x)q(x),\ h(x)=f(x)s(x). \end{equation*}
\begin{equation*} \begin{array}{ccl} g(x)u(x)+h(x)v(x)& =& f(x)q(x)u(x)+f(x)s(x)v(x)\\ &=&f(x)\left[q(x)u(x)+s(x)v(x)\right], \end{array} \end{equation*}
因此\(f(x)\mid g(x)u(x)+h(x)v(x)\)。特别地,若
\begin{equation*} f(x)\mid g(x),f(x)\mid g(x)q(x)+r(x), \end{equation*}
\begin{equation*} f(x)\mid -g(x)q(x)+\left[g(x)q(x)+r(x)\right], \end{equation*}
\(f(x)\mid r(x)\)
我们称 \(g(x)u(x)+h(x)v(x)\)为多项式 \(g(x)\)\(h(x)\)多项式组合。则 命题 1.2.10也可以叙述为:整除关系关于多项式组合封闭。

1.2.11.

\(f(x)\mid g_1(x) -g_2(x)\)\(f(x)\mid h_1(x)-h_2(x)\),证明:
\begin{equation*} f(x)\mid g_1(x) h_1(x)- g_2(x) h_2(x). \end{equation*}
解答.
因为
\begin{align*} \amp g_1(x) h_1(x)- g_2(x) h_2(x) \\ =\amp \left(g_1(x) -g_2(x)\right)h_1(x)+(h_1(x)-h_2(x))g_2(x), \end{align*}
所以根据命题 1.2.10即得结论。

子节 1.2.3 带余除法的相关Sage代码

Sage中多项式带余除法的命令为 quo_rem(),其中quo是英文单词quotient(商)的前3个字母,rem是remainder(余式)的前3个字母。其使用方法如下所示。
除quo_rem()命令外,sage还提供了两个运算符来直接求商与余式,这两个运算符也是整数运算中的求商和余数运算符,如下例所示。
带余除法定理的证明是一个算法证明,下面我们在Sage中用代码复现一下这个算法,请同学们比较证明和程序进行理解。

练习 1.2.4 练习

基础题.

1.
\(f(x)=3x^4+x^3+x+3,g(x)=2x^2+x+1\),求\(g(x)\)\(f(x)\)的商式和余式。
2.
\(g(x)\)\(f(x)\)的商与余式,并思考对于除式为一次因式的带余除法是否有更简便的求解方式。
  1. \(f(x)=x^5+2x^3-1,g(x)=x+1\)
  2. \(f(x)=x^4-\frac{1}{2}x^3+2x^3+3x^2-1,g(x)=2x-1\)
3.
\(a,b\in\mathbb{F}\)\(a\neq b\),证明:\((x-a)(x-b)\)\(f(x)\)的余式是
\begin{equation*} \frac{f(a)-f(b)}{a-b}x+\frac{af(b)-bf(a)}{a-b}. \end{equation*}
4.
对任意正整数\(n\),证明:\(x-a\left|x^n-a^n\right.\)
5.
\(f_1(x),f_2(x),g_1(x),g_2(x)\in\mathbb{F} [x]\),其中\(f_1(x)\neq 0\)
\begin{equation*} g_1(x)g_2(x)|f_1(x)f_2(x),f_1(x)|g_1(x), \end{equation*}
证明:\(g_2(x)|f_2(x)\)
6.
\(a,b\)的值,使\(x^2+x+2|x^4+ax^2+b\)
7.
证明:
\begin{equation*} f(x)\sim g(x) \Leftrightarrow [f(x)] = [g(x)]. \end{equation*}

提高题.

8.
除式为一次因式的带余除法有更为精简的计算公式,这种除法也称为综合除法。设\(f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_0\in\F[x]\)\(x-a\)\(f(x)\)的商为\(q(x)=b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+\cdots +b_0\),余式为\(r\in\F\)。证明:
\begin{equation*} b_{n-1}=a_n,\ b_i=ab_{i+1}+a_{i+1},\ 0\leq i\leq n-2,\ r=ab_0+a_0. \end{equation*}
9.
用综合除法求\(g(x)\)\(f(x)\)的商与余式,并与基础题中按照一般带余除法的计算方式进行比较。
  1. \(f(x)=x^5+2x^3-1,g(x)=x+1\)
  2. \(f(x)=x^4-\frac{1}{2}x^3+2x^3+3x^2-1,g(x)=2x-1\)
10.
写一个程序实现综合除法,并用上题中的例子进行验证。
11.
\(f(x)=(x+1)^{k+n}+(2x)(x+1)^{k+n-1}+\cdots +(2x)^k(x+1)^n\),这里\(k,n\)为非负整数。证明:\(\left. x^{k+1}\right|(x-1)f(x)+(x+1)^{k+n+1}\)
12.
\(d,n\in\mathbb{Z}^+\),证明:在\(\mathbb{F} [x]\)中,\(x^d-1\left|x^n-1\right.\)的充分必要条件是\(d|n\)
13.
\(g(x)=ax+b,\ a,b\in\mathbb{F}\)。又\(f(x)\in\mathbb{F} [x]\)。证明:\(g(x)|\left(f(x)\right)^2\)的充分必要条件是\(g(x)|f(x)\)
14.
\(m,n,p\)都是非负整数,证明:\(x^2+x+1\mid x^{3m}+x^{3n+1}+x^{3p+2}\)