主要内容\(\newcommand{\Ima}{\rm Im }
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\F}{\mathbb F}
\newcommand{\C}{\mathbb C}
\newcommand{\K}{\mathbb K}
\newcommand{\myunit}{1 cm}
\newcommand{\blue}[1]{{\color{blue}#1}}
\newcommand\iddots{\mathinner{
\kern1mu\raise1pt{.}
\kern2mu\raise4pt{.}
\kern2mu\raise7pt{\Rule{0pt}{7pt}{0pt}.}
\kern1mu
}}
\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\,}$}}}
\)
节 1.2 带余除法与整除
练习 练习
基础题.
1.
设
\(f(x)=3x^4+x^3+x+3,g(x)=2x^2+x+1\)，求
\(g(x)\)除
\(f(x)\)的商式和余式。
解答.
\begin{equation*}
\begin{array}{r|rrrrr|l}
2x^2 +x +1 & 3x^4 & +x^3 & &+x &+3 & \\
& 3x^4 & +\frac{3}{2}x^3 & +\frac{3}{2}x^2 & & & \frac{3}{2}x^2 \\\hline
& & -\frac{1}{2}x^3 & -\frac{3}{2}x^2 &+x &+3 & \\
& & -\frac{1}{2}x^3 & -\frac{1}{4}x^2 & -\frac{1}{4}x & & \hspace{1.1cm}-\frac{1}{4}x \\\hline
& & & -\frac{5}{4}x^2 &+\frac{5}{4}x & +3& \\
& & & -\frac{5}{4}x^2 &-\frac{5}{8}x & -\frac{5}{8}& \hspace{2.4cm} -\frac{5}{8}\\\hline
& & & & \frac{15}{8}x & +\frac{29}{8}& \frac{3}{2}x^2 -\frac{1}{4}x -\frac{5}{8}
\end{array}
\end{equation*}
商式
\begin{equation*}
q(x)=\frac{3}{2}x^2-\frac{1}{4}x-\frac{5}{8},
\end{equation*}
余式
\begin{equation*}
r(x)=\frac{15}{8}x+\frac{29}{8}.
\end{equation*}
2.
求\(g(x)\)除\(f(x)\)的商与余式，并思考对于除式为一次因式的带余除法是否有更简便的求解方式。
-
\(f(x)=x^5+2x^3-1,g(x)=x+1\)；
-
\(f(x)=x^4-\frac{1}{2}x^3+3x^2-1,g(x)=2x-1\)。
解答.
(a) 作带余除法，
\begin{equation*}
\begin{array}{r|rrrrrr|l}
x +1 & x^5 & & +2x^3 & & &-1 & \\
& x^5 & +x^4 & & & & & x^4 \\\hline
& & -x^4 & +2x^3 & & &-1& \\
& & -x^4& -x^3 & & & &\hspace{.7cm}-x^3 \\\hline
& & & 3x^3 & & & -1 &\\
& & & 3x^3 & +3x^2 & & &\hspace{1.8cm} +3x^2 \\\hline
& & & & -3x^2 & &-1 & \\
& & & & -3x^2 & -3x & &\hspace{3cm} -3x \\\hline
& & & & & 3x & -1 & \\
& & & & & 3x & +3 &\hspace{4.2cm} +3 \\\hline
& & & & & & -4 & x^4-x^3+3x^2-3x+3
\end{array}
\end{equation*}
商式
\begin{equation*}
q(x)=x^4-x^3+3x^2-3x+3,
\end{equation*}
余式
\begin{equation*}
r(x)=-4.
\end{equation*}
(b) 作带余除法，
\begin{equation*}
\begin{array}{r|rrrrr|l}
2x-1 & x^4 & -\frac{1}{2}x^3 & +3x^2 & &-1 & \\
& x^4 & -\frac{1}{2}x^3 & & & & \frac{1}{2}x^3 \\\hline
& & & 3x^2 & &-1 & \\
& & & 3x^2 & -\frac{3}{2}x & & \hspace{1.1cm}+\frac{3}{2}x \\\hline
& & & &\frac{3}{2}x & -1& \\
& & & &\frac{3}{2}x & -\frac{3}{4}& \hspace{2.4cm} +\frac{3}{4}\\\hline
& & & & & -\frac{1}{4}& \frac{1}{2}x^3 +\frac{3}{2}x +\frac{3}{4}
\end{array}
\end{equation*}
商式
\begin{equation*}
q(x)=\frac{1}{2}x^3 +\frac{3}{2}x +\frac{3}{4},
\end{equation*}
余式
\begin{equation*}
r(x)=-\frac{1}{4}.
\end{equation*}
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*}
解答.
由带余除法，存在\(q(x),r(x)\in\mathbb{F}[x]\)，使得
\begin{equation}
f(x)=(x-a)(x-b)q(x)+r(x),\tag{1.2.1}
\end{equation}
其中
\(\deg r(x)<2\)。假设
\(r(x)=cx+d\)，将
\(x=a,x=b\)分别代入
(1.2.1) 式，得
\begin{equation*}
f(a)=ca+d,\quad f(b)=cb+d,
\end{equation*}
联立这两个方程，解得
\begin{equation*}
c=\frac{f(a)-f(b)}{a-b},d=\frac{af(b)-bf(a)}{a-b}.
\end{equation*}
因此\((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.\)。
解答.
因存在 \(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.\)。
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)\)。
解答.
因\(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{1.2.2}
\end{equation}
\begin{equation}
g_1(x)=k(x)f_1(x),\tag{1.2.3}
\end{equation}
\begin{equation*}
f_1(x)f_2(x)=h(x)k(x)f_1(x)g_2(x).
\end{equation*}
注意到\(f_1(x)\neq 0\)，由消去律得
\begin{equation*}
f_2(x)=h(x)k(x)g_2(x).
\end{equation*}
因此\(g_2(x)|f_2(x)\)。
6.
求
\(a,b\)的值，使
\(x^2+x+2|x^4+ax^2+b\)。
解答.
因为 \(x^2+x+2\)除 \(x^4+ax^2+b\)的余式为 \((3-a)x+b-2(a-1)\)，所以
\begin{align*}
& x^2+x+2|x^4+ax^2+b\\
\Leftrightarrow & (3-a)x+b-2(a-1)=0 \\
\Leftrightarrow & a=3,b=4.
\end{align*}
提高题.
7.
证明：
\begin{equation*}
f(x)\sim g(x) \Leftrightarrow [f(x)] = [g(x)].
\end{equation*}
解答.
“
\(\Rightarrow\)” 对任意
\(h(x)\in [f(x)]\)，有
\(f(x)\sim h(x)\)，即
\(f(x),h(x)\)互相整除。由于
\(f(x)\sim g(x)\)，即
\(f(x),g(x)\)互相整除，根据整除的传递性，
\(g(x),h(x)\)互相整除，故
\(g(x)\sim h(x)\)，因此
\(h(x)\in [g(x)]\)，从而
\([f(x)]\subseteq [g(x)]\)。同理，
\([g(x)]\subseteq [f(x)]\)，由此推出
\([f(x)]=[g(x)]\)。
“
\(\Leftarrow\)” 因为
\(f(x)\in [f(x)]\)且
\([f(x)]=[g(x)]\)，所以
\(f(x)\in [g(x)]\)，根据相伴多项式类定义，
\(f(x)\sim g(x)\)。
8.
设
\(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}\)。
9.
设
\(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\)。
10.
设
\(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)\)。
解答.
只需证明当\(g(x)|\left(f(x)\right)^2\)时，\(g(x)|f(x)\)。做带余除法，记
\begin{equation*}
f(x) = h(x) (ax+b)+r
\end{equation*}
(因为\(g(x)\)的次数不超过1，所以余式\(r\)是常数)， 则
\begin{equation*}
\left(f(x)\right)^2= \left(\left(h(x)\right)^2(ax+b)+2r h(x)\right)(ax+b)+r^2,
\end{equation*}
即\(g(x)\)除\(\left(f(x)\right)^2\)的余式是\(r^2\)。因为\(g(x)|\left(f(x)\right)^2\)，所以\(r^2=0\)，推出\(r=0\)。因此\(g(x)|f(x)\)。
11.
设
\(m,n,p\)都是非负整数，证明：
\(x^2+x+1\mid x^{3m}+x^{3n+1}+x^{3p+2}\)。
解答.
\begin{equation*}
x^3-1 | \left(x^3\right)^k-1.
\end{equation*}
由于\(x^2+x+1 | x^3-1\)，根据整除传递性得
\begin{equation*}
x^2+x+1 | x^{3k}-1.
\end{equation*}
注意到
\begin{equation*}
\begin{array}{cl}
& x^{3m}+x^{3n+1}+x^{3p+2}\\
=&\left(x^{3m}-1\right)+x\left(x^{3n}-1\right)+x^2\left(x^{3p}-1\right)+1+x+x^2
\end{array}
\end{equation*}
是 \(x^{3m}-1,x^{3n}-1,x^{3p}-1,x^2+x+1\)的多项式组合，故
\begin{equation*}
x^2+x+1\mid x^{3m}+x^{3n+1}+x^{3p+2}.
\end{equation*}
12.
除式为一次因式的带余除法有更为精简的计算公式，这种除法也称为综合除法。设\(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*}
解答.
由题设\(f(x)=(x-a)q(x)+r\)，展开右式得
\begin{align*}
& a_nx^n+a_{n-1}x^{n-1}+\cdots a_1x+a_0 \\
=&b_{n-1}x^n+(b_{n-2}-ab_{n-1})x^{n-1}+\cdots+(b_0-ab_1)x+(r-ab_0),
\end{align*}
比较两式系数，有
\begin{equation*}
b_{n-1}=a_n, b_{n-2}-ab_{n-1}=a_{n-1}, \ldots , b_0-ab_1=a_1, r-ab_0=a_0,
\end{equation*}
因而
\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*}
13.
用综合除法求\(g(x)\)除\(f(x)\)的商与余式，并与基础题中按照一般带余除法的计算方式进行比较。
-
\(f(x)=x^5+2x^3-1,g(x)=x+1\)；
-
\(f(x)=x^4-\frac{1}{2}x^3+3x^2-1,g(x)=2x-1\)。
解答.
(a)
\begin{equation*}
\begin{array}{r|rrrrrr}
-1 & 1 & 0 & 2 & 0 & 0 & -1\\
& & -1 & 1 & -3 & 3 & -3\\\hline
& 1 & -1 & 3 & -3 & 3 & -4
\end{array}
\end{equation*}
商式
\begin{equation*}
q(x)=x^4-x^3+3x^2-3x+3,
\end{equation*}
余式
\begin{equation*}
r(x)=-4.
\end{equation*}
(b) 先求\(\frac{1}{2}g(x)=x-\frac{1}{2}\)除\(f(x)\)的商与余式。
\begin{equation*}
\begin{array}{r|rrrrr}
\frac{1}{2} & 1 & -\frac{1}{2} & 3 & 0 & -1\\
& & \frac{1}{2} & 0 & \frac{3}{2} & \frac{3}{4}\\\hline
& 1 & 0 & 3 & \frac{3}{2} & -\frac{1}{4}
\end{array}
\end{equation*}
\(\frac{1}{2}g(x)\)除\(f(x)\)的商式为 \(q_1(x)=x^3+3x+\frac{3}{2}\)，余式为 \(r_1(x)=-\frac{1}{4}\)。因此，\(g(x)\)除\(f(x)\)的商式
\begin{equation*}
q(x)=\frac{1}{2}q_1(x)=\frac{1}{2}x^3 +\frac{3}{2}x +\frac{3}{4},
\end{equation*}
余式
\begin{equation*}
r(x)=r_1(x)=-\frac{1}{4}.
\end{equation*}
14.
写一个程序实现综合除法，并用上题中的例子进行验证。
