8.2 多項式最大公因式與不可約性

從整數 gcd 到多項式 gcd

第 7 章說明整數整除由最大公因數、Euclidean algorithm、Bézout 恆等式與質因數分解 控制。第 8 章在多項式中重建同一套結構。類比很強，但多項式有一個新的細節： 乘上一個非零常數不會改變整除關係的本質。

例如 $x-1$ 與 $5x-5$ 只差一個非零常數倍。為了令 gcd 唯一，我們取 monic 代表。

多項式整除與相伴多項式

定義

多項式整除

對 $f(x),g(x)\in \mathbb R[x]$，若存在 $q(x)\in \mathbb R[x]$ 使得

$$f(x)=g(x)q(x),$$

便稱 $g(x)$ 整除 $f(x)$，記作 $g(x)\mid f(x)$。

兩個非零多項式互相整除，當且僅當它們只差一個非零常數倍。

定理

互相整除

對非零 $f(x),g(x)\in \mathbb R[x]$，

$$g\mid f\text{ 且 }f\mid g \quad\Longleftrightarrow\quad f(x)=kg(x)$$

其中 $k\in \mathbb R$ 且 $k\ne0$。

證明用次數即可。若 $f=d_1g$ 且 $g=d_2f$，則 $f=d_1d_2f$。由於 $f\ne0$， 乘積 $d_1d_2$ 必須是常數多項式 $1$，所以 $d_1$、$d_2$ 都是常數。

$\mathbb R[x]$ 中的最大公因式

定義

多項式最大公因式

設 $f(x),g(x)\in \mathbb R[x]$ 不同時為零。若 $d(x)$ 滿足：

1. $d(x)\mid f(x)$ 且 $d(x)\mid g(x)$；
2. 每個 $f$ 與 $g$ 的共同因式都整除 $d(x)$；

則 $d(x)$ 是 $f$ 與 $g$ 的最大公因式。記號 $\gcd(f,g)$ 指唯一的 monic 最大公因式。

這裡「最大」不是大小排序，而是整除意義：gcd 是吸收所有共同因式的那個共同因式。

相差非零常數倍的兩個非零多項式稱為相伴多項式。域上的非零常數具有多項式逆元，稱為單位。 反過來，若兩個多項式的乘積為 $1$，由乘積次數等於次數之和可知，兩者次數都為零。 這解釋了為甚麼非零常數倍不影響整除，也解釋了為甚麼不可約分解不把常數當作真正因式。

若 $d_1,d_2$ 都滿足 gcd 定義，則彼此整除，所以 $d_1=kd_2$，其中 $k$ 非零。 若兩者都是首一多項式，即最高次項係數為一，比較最高次項便得 $k=1$。 任何非零 gcd 都可除以其最高次項係數成為首一多項式。這證明標準答案的唯一性； 存在性則由下面的 Euclidean algorithm 給出，不能與唯一性混為一談。

若 $h\ne0$ 的最高次項係數為 $\lambda$，則 $\gcd(h,0)=\gcd(0,h)=h/\lambda$。因為每個多項式都整除零，共同因式恰好是 $h$ 的因式。 本節的首一 gcd 定義排除 $(0,0)$：它的共同因式可以有任意大的次數， 所以沒有首一多項式能被所有這些共同因式整除。

常見錯誤

gcd 按慣例取 monic

若 Euclidean algorithm 的最後非零餘式是 $-2x+2$，通常不把 gcd 寫成 $-2x+2$。 因為 $-2x+2=-2(x-1)$，monic gcd 是 $x-1$。

多項式 Euclidean algorithm

證明: Euclidean algorithm 保持甚麼，又怎樣標準化

起點條件。 取不同時為零的 $f,g\in\mathbb R[x]$。若有一個輸入為零，使用上述約定； 否則每次除以非零多項式。每次餘式或者為零，或者次數嚴格小於除式次數，不需要規定零多項式的次數。

不變量。 等式 $r=f-qg$ 與 $f=qg+r$ 分別證明兩個方向：一個多項式同時整除 $f,g$，當且僅當它同時整除 $g,r$。每步保持的是完整的共同因式集合，而不只是次數相同。

終止與目標。 非零餘式次數形成嚴格遞減的非負整數序列，不能無限繼續。 最後一對是 $(h,0)$；每個原來的共同因式都整除 $h$，而由不變量，$h$ 本身也整除原來的兩個輸入。 因此 $h$ 滿足 gcd 定義的兩條條件。

標準化。 若 $h$ 的最高次項係數為 $\lambda$，返回 $h/\lambda$。 這樣既保留整除關係，又令結果首一。下例中 $h=-x+1$、$\lambda=-1$，所以得到 $x-1$。 若已有 $h$ 的 Bézout 係數，也必須把兩個係數同除以 $\lambda$；只改變等式左邊會破壞恆等式。

例題

一個多項式 Euclidean algorithm

設

$$f(x)=4x^4-2x^3-16x^2+5x+9,\qquad g(x)=2x^3-x^2-5x+4.$$

逐次作帶餘除法，得到

$$f(x)=(2x)g(x)+(-6x^2-3x+9),$$$$g(x)=\left(-\frac13x+\frac13\right)(-6x^2-3x+9)+(-x+1),$$

且

$$-6x^2-3x+9=(6x+9)(-x+1)+0.$$

最後非零餘式是 $-x+1$，所以 monic gcd 是

$$\gcd(f,g)=x-1.$$

Bézout 恆等式

延伸 Euclidean algorithm 亦適用於 $\mathbb R[x]$。

定理

多項式 Bézout 恆等式

若 $f(x),g(x)\in \mathbb R[x]$ 非零，則存在 $a(x),b(x)\in \mathbb R[x]$ 使得

$$\gcd(f,g)=a(x)f(x)+b(x)g(x).$$

證明從 $f=1f+0g$、$g=0f+1g$ 開始。若連續兩個餘式已表示為 $r_i=A_if+B_ig$，下一步除法給出

$$r_{i+1}=r_{i-1}-q_i r_i =(A_{i-1}-q_iA_i)f+(B_{i-1}-q_iB_i)g.$$

新係數仍是多項式，因此每個餘式都是 $f,g$ 的多項式線性組合。算法終止後， 把最後兩個係數同除以最後非零餘式的最高次項係數，便得到首一 gcd 的表示，完成存在性證明。 若有一個輸入為零，恆等式仍成立：對最高次項係數為 $\lambda$ 的 $f\ne0$， 輸入 $(f,0)$ 可用係數 $1/\lambda,0$；輸入 $(0,f)$ 則交換這兩個係數。

在例題中，令 $r_1=-6x^2-3x+9$、$q_2=-x/3+1/3$。第二次除法記錄的是 $-x+1=g-q_2r_1$。先變號，再代入 $r_1=f-2xg$，得到

$$x-1=q_2r_1-g=q_2(f-2xg)-g=q_2f+(-2xq_2-1)g.$$

因此標準化後的明確恆等式為

$$x-1= \left(-\frac13x+\frac13\right)f(x) +\left(\frac23x^2-\frac23x-1\right)g(x).$$

這不只是計算技巧。若 $\gcd(f,g)=1$，Bézout 恆等式說明 $f$ 與 $g$ 的多項式線性 組合可以產生常數多項式 $1$，這正是許多整除定理的核心。

Bézout 係數並不唯一。若 $Af+Bg=d=\gcd(f,g)$，則對同一係數域中任意 $t\in\mathbb R[x]$，都有

$$\left(A+t\frac gd\right)f+\left(B-t\frac fd\right)g=d.$$

因為 $d$ 整除 $f,g$，兩個商仍是多項式；新加入的兩項互相抵消。 把 gcd 首一化，只固定了 gcd 的值，並沒有使表示它的係數對唯一。

定義

互質多項式

非零多項式 $f(x)$ 與 $g(x)$ 互質，意思是

$$\gcd(f,g)=1.$$

等價地，存在 $a(x),b(x)\in \mathbb R[x]$ 使得

$$a(x)f(x)+b(x)g(x)=1.$$

不可約多項式

定義

在一個域上不可約

設 $F$ 是一個域。非常數多項式 $p(x)\in F[x]$ 若不能寫成

$$p(x)=g(x)h(x)$$

其中 $g(x),h(x)\in F[x]$ 且 $0\lt\deg g,\deg h\lt\deg p$，便稱為在 $F$ 上不可約。

不可約性取決於係數域。

例題

改變係數域會改變不可約性

$x^2-2$ 在 $\mathbb Q$ 上不可約，但在 $\mathbb R$ 上可約：

$$x^2-2=(x-\sqrt2)(x+\sqrt2).$$

$x^2+1$ 在 $\mathbb R$ 上不可約，但在 $\mathbb C$ 上可約：

$$x^2+1=(x-i)(x+i).$$

反例模式

一個域中沒有根，不等於在每個域上不可約

「擴大係數域不會改變不可約性」是假命題。前例中，$\sqrt2\notin\mathbb Q$，但 $\sqrt2\in\mathbb R$；$i\notin\mathbb R$，但 $i\in\mathbb C$。 擴大係數域後，顯示的一次因式才成為允許的多項式因式。

正確判別是：域 $F$ 上的二次多項式不可約，當且僅當它在 $F$ 中沒有根。 非平凡分解的次數只能為 $1+1$，一次因式會給出根；反過來，有根便由因式定理得到一次因式。 因此 $x^2-2$ 沒有有理根，而 $x^2+1$ 沒有實根，因為實數 $t$ 滿足 $t^2+1\gt0$。 必須保留「二次」條件；這段論證沒有證明任意次數的無根多項式都不可約。

在 $\mathbb C[x]$ 中，每個不可約多項式都是一次式。原因是代數基本定理保證每個非常數複 係數多項式都有根。在 $\mathbb R[x]$ 中，不可約多項式剛好是一次式以及判別式 $b^2-4ac\lt0$ 的二次式 $ax^2+bx+c$。

實係數多項式的非實根與其共軛根成對出現。若 $\alpha\notin\mathbb R$，則

$$(x-\alpha)(x-\bar\alpha)=x^2-2\operatorname{Re}(\alpha)x+|\alpha|^2$$

是實係數二次式，且沒有實一次因式。把非實根成對組合，實根保留為一次因式， 便得到實數上的一次及二次因式分解，因此更高次數的多項式必有真因式。 反過來，一次式由次數可知不可約，負判別式二次式則由無實根判別可知不可約。 這裏二次式的條件包含 $a\ne0$。

整除與因式分解的證明

以下論證適用於域 $F$，包括 $\mathbb Q$、$\mathbb R$、$\mathbb C$。 多項式除法只要求能夠除以非零最高次項係數，而域中總能這樣做， 所以前面的 gcd 與 Bézout 證明同樣適用於 $F[x]$。

定理

不可約多項式具有質數式的整除性質

設 $F$ 為域，$p\in F[x]$ 不可約，且 $a,b\in F[x]$。 若 $p\nmid a$，則 $\gcd(a,p)=1$。若 $p\mid ab$，則 $p\mid a$ 或 $p\mid b$。

令 $d=\gcd(a,p)$。因為 $d\mid p$，可寫 $p=de$。不可約性迫使 $d$ 或 $e$ 為常數。 若 $e$ 是常數，它必非零，故 $d$ 與 $p$ 相伴；於是 $d\mid a$ 會推出 $p\mid a$。 在 $p\nmid a$ 的假設下，這不可能，因此 $d$ 只能是常數，其首一代表就是 $1$。 這一步使用的是不可約性的定義，沒有預先假定不可約多項式已經具有質數性質。

現在設 $p\mid ab$。若 $p\mid a$，結論已成立；否則 Bézout 給出 $ua+vp=1$。 兩邊乘以 $b$ 得 $b=uab+vpb$。右邊兩項都被 $p$ 整除，所以 $p\mid b$。 這才完成「整除乘積必整除某個因式」的證明。

定理

多項式線性組合的可解性

設 $F$ 為域，$a,b,c\in F[x]$，且 $a,b$ 不同時為零，令 $d=\gcd(a,b)$。 存在 $u,v\in F[x]$ 滿足 $au+bv=c$，當且僅當 $d\mid c$。

必要性：$d\mid a,b$ 使 $d\mid au+bv$，故有解必有 $d\mid c$。 充分性：若 $c=dh$，取 Bézout 係數 $A,B$ 使 $Aa+Bb=d$，再乘以 $h$， 便得到解 $u=hA$、$v=hB$。這樣不但排除不可解的右邊，也為每個符合整除條件的右邊構造了一個解。 若 $a=b=0$，另行判斷原方程：恰好在 $c=0$ 時有解，不需要替 gcd 增設約定。

定理

不可約因式分解的存在與唯一性

設 $F$ 為域，$f\in F[x]$ 為非常數多項式。則 $f=c\,p_1\cdots p_r$，其中 $c\in F$ 非零，每個 $p_j$ 都首一且不可約。 常數 $c$ 與首一因式的多重集唯一；因式可以重複，排列次序不影響分解。

存在性。 對 $f$ 的正次數歸納。一次多項式不可約。若 $f$ 已不可約， 把它首一化，並把最高次項係數留作常數即可。否則 $f=gh$，其中兩個因式次數都為正， 又嚴格小於 $\deg f$。由歸納假設，$g,h$ 都能分解成不可約因式，相乘就給出 $f$ 的分解。 最後逐個把因式首一化，所有非零常數合併為 $c$。次數嚴格下降保證過程結束； 整個過程不要求因式互不相同，所以重複因式也被涵蓋。

唯一性。 假設 $c\,p_1\cdots p_r=d\,q_1\cdots q_s$ 是兩種上述分解。 反覆使用已經證明的質數性質，$p_1$ 必整除某個 $q_j$：它次數為正，不能整除非零常數 $d$。 由於 $q_j$ 不可約，商只能是常數；再由兩者首一，得到 $p_1=q_j$。 調整次序並消去這個共同非零因式。域上的多項式環沒有零因子，所以消去合法。 重複上述步驟；若一邊的因式先用完，就會得到非零常數等於正次數乘積，與次數法則矛盾。 因此兩列因式連同重數完全匹配，最後剩下 $c=d$。

觀看多項式 Euclidean algorithm 如何產生 monic gcd、回代成 Bézout 恆等式，並支撐依係數域而定的不可約判別。

1. Monic gcd

   x-1、5x-5、-2x+2 這些常數倍有相同整除行為，所以 gcd 以 monic 代表記錄。

2. Euclidean 不變量

   由 f=gq+r 可知，f 與 g 的共同因式正好就是 g 與 r 的共同因式；所以 gcd(f,g)=gcd(g,r)。

3. 例子餘式鏈

   在本章例子中，餘式依次是 r1=-6x^2-3x+9、r2=-x+1，然後是 0。

4. 回代

   最後非零餘式 -x+1 標準化為 x-1，再回代成 x-1=(-1/3x+1/3)f+(2/3x^2-2/3x-1)g。

5. 係數域依賴

   不可約性取決於係數域：x^2-2 在 Q 與 R 之間改變，x^2+1 在 R 與 C 之間改變。

6. 類似質數

   若 p 不可約且 p 不整除 a，Bézout 給出 ua+vp=1；乘以 b 便解釋 p|ab 為何迫使 p|b。

多項式 gcd 有三層連接：把相伴多項式標準化為 monic gcd，透過 Euclidean 餘式鏈保持共同因式，再用 Bézout 證明不可約多項式的整除判別。

例題：可解性判別

例題

用 gcd 判斷多項式方程有無解

判斷是否存在 $u(x),v(x)\in \mathbb R[x]$ 使得

$$(x^2-1)u(x)+(x-1)v(x)=x+1.$$

左邊是 $x^2-1$ 與 $x-1$ 的多項式線性組合。因為

$$x^2-1=(x-1)(x+1),$$

所以

$$\gcd(x^2-1,x-1)=x-1.$$

由多項式 Bézout 可解性判別，方程有解必須有 $x-1\mid x+1$。但代入 $x=1$ 得到 $2\ne0$，所以 $x-1$ 不整除 $x+1$，方程無解。

常見錯誤

常見錯誤

把常數倍當成不同 gcd 答案

在 $\mathbb R[x]$ 中，$x-1$、$2x-2$、$-7x+7$ 的整除內容相同。只有 $x-1$ 是 monic 代表，因此標準 gcd 寫作 $x-1$。

常見錯誤

說不可約時沒有指定係數域

「$x^2-2$ 不可約」這句話不完整。它在 $\mathbb Q$ 上不可約，但在 $\mathbb R$ 上可約。討論 不可約性時一定要說明係數域。

總結

多項式 gcd 理論複製了整數 gcd 理論的結構，只是以次數取代大小，以 monic 標準化 取代正數代表。Euclidean algorithm 在保持共同因式不變的同時降低次數；延伸算法給出 Bézout 恆等式。不可約多項式扮演質數的角色，但不可約性取決於係數域：在 $\mathbb C$ 上只有 一次式不可約；在 $\mathbb R$ 上，不可約多項式是一次式與判別式為負的二次式。

練習閱讀指南

求 Bézout 恆等式時，要保留每一步除法方程。gcd 是向下做 Euclidean algorithm 得到， 但 Bézout 表示是把方程向上回代得到。常見錯誤是改寫了一個餘式，卻忘記它來自哪一個 前一方程。最後最好展開 $a(x)f(x)+b(x)g(x)$，檢查高次項是否全部抵消。

判斷不可約性時，係數域是題目的一部分。二次式沒有有理根，不代表它在 $\mathbb R$ 上不可約； 二次式沒有實根，仍會在 $\mathbb C$ 上分解。對 $\mathbb R$ 上二次式，判別式測試已足夠；對 $\mathbb Q$， 則要使用有理根與數系資訊。例如 $x^2-5$ 在 $\mathbb Q$ 上不可約，因為 $\sqrt5$ 不是有理數， 但它在 $\mathbb R$ 上可分解。

快速檢查

思考檢查

為甚麼在 $\mathbb R[x]$ 中要取 monic gcd？

想想共同因式乘上非零常數後會怎樣。

解答 · 答案

最大公因式只在非零常數倍意義下唯一；取 monic 代表後，記號才真正唯一。

思考檢查

$-x+1$ 與 $0$ 的 monic gcd 是甚麼？

把非零多項式標準化。

解答 · 答案

gcd 是 $x-1$，因為 $-x+1=-(x-1)$，monic 代表是 $x-1$。

思考檢查

$x^2+1$ 在 $\mathbb R$ 上不可約嗎？在 $\mathbb C$ 上不可約嗎？

比較兩個域中可用的根。

解答 · 答案

它在 $\mathbb R$ 上不可約，因為沒有實根；但在 $\mathbb C$ 上可約，因為 $x^2+1=(x-i)(x+i)$。

練習

第 4、5 題固定一個域 $F$；所有多項式屬於 $F[x]$，不可約性均相對於 $F$。

1. 用 Euclidean algorithm 計算 $\mathbb R[x]$ 中的 $\gcd(x^3-1,x^2-1)$。
2. 在例題中，展開右邊以驗證 $x-1$ 的 Bézout 恆等式。
3. 判斷 $x^2-5$ 在 $\mathbb Q$、$\mathbb R$、$\mathbb C$ 上是否不可約。
4. 證明：若 $p(x)$ 不可約且 $p\nmid a(x)$，則 $\gcd(a,p)=1$。
5. 證明：若 $p(x)$ 不可約且 $p\mid a(x)b(x)$，則 $p\mid a(x)$ 或 $p\mid b(x)$。
6. 判斷是否存在 $u(x),v(x)\in \mathbb R[x]$ 使得 $(x^2-1)u(x)+(x-1)v(x)=x+1$。

解答 · 參考解答 1

先除得 $x^3-1=x(x^2-1)+(x-1)$，再除得 $x^2-1=(x+1)(x-1)+0$。最後非零餘式 $x-1$ 已首一，故為 gcd。

解答 · 參考解答 2

記 $A=-x/3+1/3$、$B=2x^2/3-2x/3-1$。分別展開兩個乘積，得到

$$Af=-\frac43x^5+2x^4+\frac{14}{3}x^3-7x^2-\frac43x+3,$$$$Bg=\frac43x^5-2x^4-\frac{14}{3}x^3+7x^2+\frac73x-4.$$

$x^5,x^4,x^3,x^2$ 的係數逐對抵消，剩餘項給出

$$Af+Bg=\left(-\frac43+\frac73\right)x+(3-4)=x-1.$$

最後非零餘式原為 $-x+1$。首一化時，餘式及其兩個 Bézout 係數都要除以 $-1$； 這裏使用的 $A,B$ 已包含這一標準化。

解答 · 參考解答 3

$x^2-5$ 在 $\mathbb Q$ 上不可約，因為 $\sqrt5\notin \mathbb Q$；在 $\mathbb R$ 上可分解為 $(x-\sqrt5)(x+\sqrt5)$；因此在 $\mathbb C$ 上亦可約。

解答 · 參考解答 4

由於 $p$ 不可約，它的因式只有常數倍與本身。若 $p\nmid a$，gcd 不可能有 $\deg p$，故只能是 $1$。

解答 · 參考解答 5

若 $p\nmid a$，由第 4 題得 $\gcd(a,p)=1$。取 $u,v$ 使 $ua+vp=1$， 兩邊乘以 $b$，可得 $p\mid b$。

解答 · 參考解答 6

$x^2-1$ 與 $x-1$ 的 gcd 是 $x-1$。但 $x-1$ 不整除 $x+1$，所以不存在。