主要内容\(\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\myunit}{1 cm}
\newcommand{\alert}[1]{{\color{red}#1}}
\newcommand{\blue}[1]{{\color{blue}#1}}
\tikzset{
node style sp/.style={draw,circle,minimum size=\myunit},
node style ge/.style={circle,minimum size=\myunit},
arrow style mul/.style={draw,sloped,midway,fill=white},
arrow style plus/.style={midway,sloped,fill=white},
}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
节 5.2 多项式的整除
子节 5.2.1 主要知识点
定义 5.2.1.
设 \(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)\)，记为\(g(x)|f (x)\)。否则称\(g(x)\)不整除\(f(x)\)，记为 \(g(x)\nmid f(x)\)。整除的性质:
\(f(x)\)，\(g(x)\)，\(h(x)\in \mathbb{F}[x]\)，则
反身性：\(f(x)|f(x)\)；
传递性：\(f(x)|g(x)\)，\(g(x)|h(x)\)，则\(f(x)|h(x)\)；
互伴性：\(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)|g(x)\)，\(f(x)|h(x)\)，则对任意\(u(x)\)，\(v(x)\in\mathbb{F}[x]\)，有
\begin{equation*}
f(x)| g(x)u(x)+h(x)v(x).
\end{equation*}
特别地，若\(f(x)|g(x)\)，\(f(x)|g(x)q(x)+r(x) \)，则\(f(x)|r(x)\)。
多项式的带余除法
定理 5.2.2. 欧式除法.
设\(f(x),\ g(x)\in \mathbb{F}[x]\)， \(g(x)\ne 0\)， 则存在唯一 \(q(x),\ r(x)\in \mathbb{F}[x]\)，使得
\begin{equation*}
f (x) = g (x)q(x) + r(x),
\end{equation*}
其中 \({\deg r(x)}{\color{red}{<}}\deg g(x) \)。
推论 5.2.3.
\(f (x)\)，\(g (x)\in \mathbb{F}[x]\)，\(g (x) \ne 0 \)，则\(g(x)| f(x)\)当且仅当 \(g(x)\) 除 \(f(x)\) 的余式为0。
子节 5.2.2 带余除法的相关Sage代码
Sage中多项式带余除法的命令为 quo_rem，其中quo是英文单词quotient（商）的前3个字母，rem是remainder（余式）的前3个字母。其使用方法如下所示。
带余除法定理的证明是一个算法证明，下面我们在Sage中用代码复现一下这个算法，请同学们比较理解。
练习 5.2.3 练习
1.
对任意正整数\(n\)，证明：\(x-a\left|x^n-a^n\right.\)。
解答.
因存在 \(x^{n-1}+ax^{n-2}+a^2x^{n-3}+\cdots+a^{n-1}\in\mathbb{F}[x]\)，使得
\begin{equation*}
x^n-a^n=(x-a)(x^{n-1}+ax^{n-2}+a^2x^{n-3}+\cdots+a^{n-1}),
\end{equation*}
因此\(x-a\left|x^n-a^n\right.\)。
2.
设\(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}\)。
解答.
因为
\begin{equation*}
f(x)=(x+1)^n\left((x+1)^{k}+(2x)(x+1)^{k-1}+\cdots +(2x)^k\right),
\end{equation*}
所以
\begin{equation*}
\begin{array}{ccl}
(x-1)f(x)&=&(x+1)^n(x-1)\left((x+1)^{k}+(2x)(x+1)^{k-1}+\cdots +(2x)^k\right)\\
&=&(x+1)^n{\color{blue}\left(2x-(x+1)\right)}\left((x+1)^{k}+(2x)(x+1)^{k-1}+\cdots +(2x)^k\right)\\
&=&(x+1)^n\left((2x)^{k+1}-(x+1)^{k+1}\right)\\
&=&(x+1)^n(2x)^{k+1}-(x+1)^{n+k+1},
\end{array}
\end{equation*}
即
\begin{equation*}
(x-1)f(x)+(x+1)^{k+n+1}=2^{k+1}(x+1)^nx^{k+1},
\end{equation*}
从而\(\left. x^{k+1}\right|(x-1)f(x)+(x+1)^{k+n+1}\)。
3.
设\(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)\)。
解答.
因为\(g_1(x)g_2(x)|f_1(x)f_2(x),f_1(x)|g_1(x)\)，所以存在\(h(x),k(x)\in\mathbb{F}[x]\)，使得
\begin{equation}
f_1(x)f_2(x)=h(x)g_1(x)g_2(x),\tag{5.1}
\end{equation}
\begin{equation}
g_1(x)=k(x)f_1(x),\tag{5.2}
\end{equation}
将\((5.2.2)\)式代入\((5.2.1)\)式得
\begin{equation*}
f_1(x)f_2(x)=h(x)k(x)f_1(x)g_2(x)\mbox{。}
\end{equation*}
注意到\(f_1(x)\neq 0\)，由消去律得
\begin{equation*}
f_2(x)=h(x)k(x)g_2(x)\mbox{。}
\end{equation*}
因此\(g_2(x)|f_2(x)\)。
4.
设\(f(x)=3x^4+x^3+x+3,g(x)=2x^2+x+1\)，求\(f(x)\)除以\(g(x)\)的商式和余式。
解答.
商式\(q(x)=\frac{3}{2}x^2-\frac{1}{4}x-\frac{5}{8}\)，余式\(r(x)=\frac{15}{8}x+\frac{29}{8}\)。
5.
求\(a,b\)的值，使\(x^2+x+2|x^4+ax^2+b\)。
解答.
\(x^2+x+2|x^4+ax^2+b\Leftrightarrow (3-a)x+b-2(a-1)=0\Leftrightarrow a=3,b=4\)。
6.
设\(d,n\in\mathbb{Z}^+\)，证明：在\(\mathbb{F} [x]\)中，\(x^d-1\left|x^n-1\right.\)的充分必要条件是\(d|n\)。
解答.
充分性：因为\(d\mid n\)，所以存在\(k\in\mathbb{Z}^+\)，使得\(n=dk\)。因此
\begin{equation*}
x^n-1=\left(x^{d}\right)^k-1=(x^d-1)\left[\left(x^d\right)^{k-1}+\left(x^d\right)^{k-2}+\cdots +x^d+1\right],
\end{equation*}
故\(x^d-1\mid x^n-1\)。
必要性：（反证法）假设\(d\nmid n\)，则\(n=dq+r\)，其中\(0<r<d\)，则
\begin{equation*}
x^n-1=x^{dq+r}-x^r+x^r-1=x^r(x^{dq}-1)+(x^r-1)\mbox{。}
\end{equation*}
因为\(x^d-1\mid x^n-1\)且\(x^d-1\mid x^{dq}-1\)，所以
\begin{equation*}
x^d-1\mid (x^n-1)-x^r(x^{dq}-1),
\end{equation*}
即\(x^d-1\mid x^r-1\)，这与\(0<r<d\)相矛盾。因此\(d\mid n\)。
7.
设\(g(x)=ax+b,\ a,b\in\mathbb{F}\)。又\(f(x)\in\mathbb{F} [x]\)。证明：\(g(x)|f^2(x)\)的充分必要条件是\(g(x)|f(x)\)。
解答.
只需证明当\(g(x)|f^2(x)\)时，\(g(x)|f(x)\)。做带余除法，记
\begin{equation*}
f(x) = h(x) (ax+b)+r
\end{equation*}
(因为\(g(x)\)的次数不超过1，所以余式\(r\)是常数)。 则
\begin{equation*}
f^2(x)= \left(h^2(x)(ax+b)+2r h(x)\right)(ax+b)+r^2
\end{equation*}
所以\(f^2(x)\)除以\(g(x)\)的余式是\(r^2\)。因为\(g(x)|f^2(x)\)，所以\(r^2=0\)，推出\(r=0\)，即\(g(x)|f(x)\)。
