單位根/多項式整除

本章演示了在多項式整除問題中使用單位根。

多項式整除

設 $f(x)$ 和 $p(x)$ 是兩個多項式。

假設存在另一個多項式 $q(x)$，使得

$f(x)=p(x)\cdot q(x)$.

如果 $f(x)$，$p(x)$ 和 $q(x)$ 是具有整數係數的多項式，則，$f(x)$ 被稱為在整數上可被 $p(x)$ 整除。

類似地，如果 $f(x)$，$p(x)$ 和 $q(x)$ 是具有有理係數的多項式，則，$f(x)$ 被稱為在有理數上可被 $p(x)$ 整除。

如果 $f(x)$，$p(x)$ 和 $q(x)$ 是具有實係數或復係數的多項式，則，$f(x)$ 被稱為在實數或複數上可被 $p(x)$ 整除。

示例 1 設 $f(x)=x^{2}-1$ 且 $p(x)=2x+2$。這兩個多項式的係數都是整數。但是

$x^{2}-1=(2x+2)({\frac {1}{2}}x-{\frac {1}{2}})$.

右邊第二個括號中的多項式 ${\frac {1}{2}}x-{\frac {1}{2}}$ 沒有整數係數。因此，$f(x)$ 在整數範圍內不能被 $p(x)$ 整除。

但是，如果我們考慮 $f(x)$ 和 $p(x)$ 是具有有理數、實數或複數係數的多項式，那麼 ${\frac {1}{2}}x-{\frac {1}{2}}$ 也是具有有理數、實數或複數係數的多項式。所以，$f(x)$ 在有理數、實數或複數範圍內可以被 $p(x)$ 整除。證畢

因此，多項式的可除性與我們允許係數取值的數字集合密切相關。然而，由於 $f(x)$ 和 $p(x)$ 是已知多項式，商式 $q(x)$ 的係數是可除性的關鍵。

現在，設 $f(x)=p(x)\cdot q(x)$，其中 $f(x)$ 和 $p(x)$ 在我們指定的數字集合中具有係數。我們如何確定 $q(x)$ 也是一個在相同集合中具有係數的多項式？這個問題的答案在以下規則中給出

規則 1 設 $f(x)=p(x)\cdot q(x)$。

• 如果 $f(x)$ 和 $p(x)$ 具有復係數，則 $q(x)$ 具有復係數。 $f(x)$ 可以被 $p(x)$ 在複數域上整除。
• 如果 $f(x)$ 和 $p(x)$ 具有實係數，則 $q(x)$ 具有實係數。 $f(x)$ 可以被 $p(x)$ 在實數域上整除。
• 如果 $f(x)$ 和 $p(x)$ 具有有理係數，則 $q(x)$ 具有有理係數。 $f(x)$ 可以被 $p(x)$ 在有理數域上整除。
• 如果 $f(x)$ 和 $p(x)$ 的係數都是整數，並且 (充分但不必必要地) $p_{0}=1$，那麼 $q(x)$ 的係數都是整數。 $f(x)$ 能被 $p(x)$ 整除。

這個規則在附錄中證明。

當我們只考慮整數係數時，條件 $p_{0}=1$ 是不必要的。例如，令 $f(x)=2x^{2}-2$ 和 $p(x)=-2x+2$，那麼 $p_{0}=-2$，但是 $2x^{2}-2=(-2x+2)(-x-1)$。

因式定理和單位根

在初等代數中，我們有餘數定理。這裡只陳述定理，不提供證明。

餘數定理 多項式 $f(x)$ 被 $x-a$ 除的餘數等於 $f(a)$。

從這個定理，我們可以得到以下結果，通常被稱為“因式定理”。
因式定理 多項式 $f(x)$ 能被 $x-a$ 整除，當且僅當 $f(a)=0$。
(注意，$f(x)$ 和 $a$ 是已知的，我們自動假設它屬於可被整除的數字集合中)。

證明 假設 $f(x)$ 可被 $x-a$ 整除，則多項式 $f(x)$ 被 $x-a$ 除的餘數為零。因此，$f(a)=0$.
另一方面，如果 $f(a)=0$，則多項式 $f(x)$ 被 $x-a$ 除的餘數為零。因此，$f(x)=(x-a)q(x)$。此外，除數的首項係數為 $p_{0}=1$。因此，根據規則 1，$f(x)$ 可被 $x-a$ 整除，在整數、有理數、實數和複數範圍內。

因子定理的重複應用會導致更復雜的除數
規則 2 如果多項式 $f(x)$ 滿足

$f(a)=f(b)=0,\quad a\neq b$,

那麼 $f(x)$ 可被 $x^{2}-(a+b)x+ab$ 整除。
證明 根據因子定理，因為 $f(a)=0$，存在多項式 $q(x)$ 使得

$f(x)=(x-a)q(x)$.

令 $x=b$

$f(b)=(b-a)q(b)$.

由於 $f(b)=0$ 且 $a\neq b$，我們得出結論 $q(b)=0$。根據因式定理，存在多項式 $s(x)$ 使得

$q(x)=(x-b)s(x)$.

因此

$f(x)=(x-a)(x-b)s(x)$,

$f(x)=(x^{2}-(a+b)x+ab)s(x)$.

注意除數的首項係數為 1。

推論 1 如果實係數多項式 $f(x)$ 滿足 $f(\alpha +\beta i)=0$，其中 $\alpha$ 和 $\beta$ 是實數且 $\beta \neq 0$，則 $f(x)$ 可以被 $x^{2}-2\alpha x+(\alpha ^{2}+\beta ^{2})$ 整除。
證明 在代數中，我們已經知道如果一個實係數多項式 $f(x)$ 在某個複數 $z=\alpha +\beta i$ 處為零，那麼它也在 ${\overline {z}}=\alpha -\beta i$ 處為零。因此，我們可以應用規則 2 來獲得所需的結果，因為 $\beta \neq 0$ 意味著 $\alpha +\beta i\neq \alpha -\beta i$.

以上推論有一個有用的特例，如下所示
推論 2 如果一個整數係數多項式 $f(x)$ 滿足 $f(\omega )=0$，其中 $\omega =-{\frac {1}{2}}+{\frac {\sqrt {3}}{2}}i$ 是 1 的立方根，那麼 $f(x)$ 可以被 $x^{2}+x+1$ 整除。

推論 1 是複數在處理實係數多項式可除性的應用的一個例子。推論 2 透過利用 1 的立方根進一步限制了整數上的可除性。

我們也可以在多項式可除性問題中應用其他單位根，但我們需要類似於上面顯示的結果。

規則 3 如果一個多項式 $f(x)$ 滿足

$f(a_{1})=f(a_{2})=\cdots =f(a_{n})=0$

對於 $n$ 個不同的數 $a_{1},a_{2},\ldots ,a_{n}$，那麼 $f(x)$ 可以被乘積 $(x-a_{1})(x-a_{2})\cdots (x-a_{n})$ 整除。

規則 4 類似於規則 3：它們是因式定理的重複應用。

推論 3 如果一個整數係數多項式 $f(x)$ 滿足

$f(\epsilon _{k})=0$ 其中 $k={\begin{cases}1,2,\ldots ,{\frac {n}{2}}&{\text{if }}n{\text{ is even}}\\1,2,\ldots ,{\frac {n-1}{2}}&{\text{if }}n{\text{ is odd}},\end{cases}}$

那麼 $f(x)$ 可以被 $x^{n-1}+x^{n-2}+\cdots +x^{2}+x+1$ 整除。

為了證明這個推論，我們需要用到一個結論：單位根的非實根的共軛也是單位根的非實根。

在多項式可除性問題中使用單位根

示例 2 設 $f(x)=x^{3m+1}+x^{3n+2}+1$，其中 $m$ 和 $n$ 是整數。證明 $f(x)$ 可以被 $x^{2}+x+1$ 整除。
證明 令 $x=\omega$，則

$f(\omega )=\omega ^{3m+1}+\omega ^{3n+2}+1=\omega +\omega ^{2}+1=0$,

根據推論 2，$f(x)$ 可以被 $x^{2}+x+1$ 整除。

示例 3 設 $n$ 為自然數，且

$f(x)=x^{n+2}+(x+1)^{2n+1}$.

證明對於任意整數 $k$，$f(k)$ 是 $k^{2}+k+1$ 的倍數。
證明 很容易證明 $f(\omega )=0$ 並且 $f(x)$ 是一個係數為整數的多項式。因此，$f(x)$ 可以被 $x^{2}+x+1$ 整除。由於 $f(x)$ 和 $x^{2}+x+1$ 都是係數為整數的多項式，因此它們的商，假設為 $q(x)$，也是一個係數為整數的多項式。因此，當 $k$ 是一個整數時，$f(k)$ 是 $k^{2}+k+1$ 的整數倍。

例 4 求 $x^{1001}-1$ 被 $x^{4}+x^{3}+2x^{2}+x+1$ 除的餘數。
解 令 $f(x)=x^{1001}-1$ 並且 $p(x)=x^{4}+x^{3}+2x^{2}+x+1$。令餘數為 $r(x)$，則

$f(x)=p(x)\cdot q(x)+r(x)$,

其中 $q(x)$ 表示商。由於除數 $p(x)$ 的次數是 4，餘數 $r(x)$ 的次數最多是三。因此，令

$r(x)=ax^{3}+bx^{2}+cx+d$.

現在我們要確定$r(x)$的係數。
從

$p(x)=(x^{2}+1)(x^{2}+x+1)$,

我們知道

$p(i)=p(\omega )=0$,

所以

$f(i)=r(i),\quad f(\omega )=r(\omega )$

$i-1=-ai-b+ci+d,\quad -{\frac {3}{2}}-{\frac {\sqrt {3}}{2}}i=a+d+{\frac {b}{2}}-{\frac {c}{2}}+({\frac {c{\sqrt {3}}}{2}}-{\frac {b{\sqrt {3}}}{2}})i$

比較這兩個等式兩邊的實部和虛部

$d-b=-1,\quad c-a=1,\quad a+d-{\frac {b}{2}}-{\frac {c}{2}}=-{\frac {3}{2}},\quad {\frac {c{\sqrt {3}}}{2}}-{\frac {b{\sqrt {3}}}{2}}=-{\frac {\sqrt {3}}{2}}$

求解，$a=-1,b=1,c=d=0$。因此，餘數為$r(x)=-x^{3}+x^{2}$。

例 5 令$P(x)$、$Q(x)$、$R(x)$和$S(x)$是滿足以下恆等式的多項式

$P(x^{5})+xQ(x^{5})+x^{2}R(x^{5})=(x^{4}+x^{3}+x^{2}+x+1)S(x)$.

證明 $x-1$ 是 $P(x)$ 的因式。
證明 令

$P(x)=p_{m}x^{m}+p_{m-1}x^{m-1}+\cdots +p_{1}x^{1}+p_{0}$,

$S(x)=s_{n}x^{n}+s_{n-1}x^{n-1}+\cdots +s_{1}x^{1}+s_{0}$.

注意 $P(x^{5})+xQ(x^{5})+x^{2}R(x^{5})$ 只有 $x^{5k}$ 項，$x^{5k+1}$ 項和 $x^{5k+2}$ 項，對於非負整數 $k$。因此，$x^{5k-1}$ 項的係數全為零。那麼

$s_{5k-1}+s_{5k-2}+s_{5k-3}+s_{5k-4}+s_{5k-5}=0$.

另一方面，比較 $x^{5k}$ 項的係數

$p_{0}=s_{0}$,

$p_{k}=s_{5k}+s_{5k-1}+s_{5k-2}+s_{5k-3}+s_{5k-4}$

因此，$p_{k}=s_{5k}-s_{5k-5}$.
現在，我們將證明$s_{5m}=0$. 首先，請注意

$0=p_{m+1}=p_{m+2}=\cdots =p_{m+h}$

所以，

$0=p_{m+1}+p_{m+2}+\cdots +p_{m+h}$

$=(s_{5m+5}-s_{5m})+(s_{5m+10}-s_{5m+5})+\cdots +(s_{5m+5h}-s_{5m+5(h-1)})$

$=s_{5m+5h}-s_{5m}$ 對於任何$h>0$.

換句話說，$s_{5m}=s_{5m+5}=s_{5m+10}=\cdots$. 注意到$S(x)$ 是一個多項式，因此它具有有限的度數。 $s_{5m}\neq 0$ 將導致與之矛盾。 因此，$s_{5m}=0$.
所以

$P(x)=s_{0}+(s_{5}-s_{0})x+(s_{10}-s_{5})x^{2}+\cdots +(s_{5m-5}-s_{5m-10})x^{m-1}+s_{5m-5}x^{m}$

$=-(x-1)(s_{0}+s_{5}x+s_{10}x^{2}+\cdots +s_{5m-5}x^{m-1})$. 證畢

另一種證明 令 $\epsilon _{k}$ 為一個複數 5 次單位根，則

$(\epsilon _{k})^{5}=1$, $(\epsilon _{k})^{2}=\epsilon _{2k}$, $(\epsilon _{k})^{4}+(\epsilon _{k})^{3}+(\epsilon _{k})^{2}+\epsilon _{k}+1=0$.

將 $x=\epsilon _{k}$ 代入給定的恆等式

$P(1)+\epsilon _{k}Q(1)+\epsilon _{2k}R(1)=0$.

我們可以先分別將 $k=1,2$ 代入，然後分別比較實部和虛部，得到以下結果

$P(1)+{\frac {{\sqrt {5}}-1}{4}}Q(1)-{\frac {{\sqrt {5}}+1}{4}}R(1)=0$,

$P(1)-{\frac {{\sqrt {5}}+1}{4}}Q(1)+{\frac {{\sqrt {5}}-1}{4}}R(1)=0$,

${\frac {\sqrt {10+2{\sqrt {5}}}}{4}}Q(1)+{\frac {\sqrt {10-2{\sqrt {5}}}}{4}}R(1)=0$,

${\frac {\sqrt {10-2{\sqrt {5}}}}{4}}Q(1)-{\frac {\sqrt {10+2{\sqrt {5}}}}{4}}R(1)=0$,

我們可以輕鬆地解出這些方程

$P(1)=Q(1)=R(1)=0$.

根據因式定理，$x-1$ 是 $P(x)$ 的一個因式。證畢

另一種證明方法利用了單位根的性質。透過這樣做，我們也可以得出結論，$x-1$ 是 $Q(x)$ 和 $R(x)$ 的因式，這意味著 $S(x)$ 也包含因式 $x-1$.

在第一個證明中，我們只需要 $x^{5k-1}$ 項的係數為零。所以，我們可以新增一項 $x^{3}T(x^{5})$，結論仍然成立。

例 6 設 $P(x)$，$Q(x)$，$R(x)$，$T(x)$ 和 $S(x)$ 是滿足以下恆等式的多項式

$P(x^{5})+xQ(x^{5})+x^{2}R(x^{5})+x^{3}T(x^{5})=(x^{4}+x^{3}+x^{2}+x+1)S(x)$.

證明 $x-1$ 是 $P(x)$ 的因式。
證明 重複上一個例子的第一個證明。
另一種證明方法 重複前面例子的另一種證明方法：將 $x=\epsilon _{1},\epsilon _{2}$ 代入，並比較實部和虛部。用這種方法，我們也可以得出結論，所有多項式 $P(x)$，$Q(x)$，$R(x)$，$T(x)$ 和 $S(x)$ 都具有因子 $x-1$.