最大公因式

兩個多項式的最大公因式（英語：Polynomial greatest common divisor，簡稱GCD）是指此多項式是兩多項式的因式，且不存在其他次數更高的公因式。最大公因式的概念類似兩整數的最大公因數。

針對系數在域裏的單變數多項式，可以像計算最大公因數一樣，用多項式除法的輾轉相除法計算最大公因式。可以得到的最大公因數，頂多會再乘以一個系數。

整數最大公因數和多項式最大公因式之間的類似之處，可以將所有用帶餘除法和輾轉相除法可以推得的性質擴展到單變數多項式。而且，最大公因式有其特殊的性質，因此在代數的許多領域都會提到。一般來說，兩多項式最大公因式的根也就是兩個多項式的共同根，這就提供一個可以知道多項式根的資訊，但又不需真正求解的方式。例如，多項式的重根是該多項式以及其導數多項式最大公因式的根，而且最大公因式的計算，可以計算多項式的無平方因式分解，可提供多項式的根是原多項式特定重複度的根。

最大公因式也可以在整數域或是整數環上的多變數多項式裏定義，或是在唯一分解整環上的多變數多項式裏定義。只要在其其系數的環，存在最大公因數的演算法，就有演算法可以計算最大公因式。此演算法是利用變體的輾轉相除法，在變數的數量上遞歸，以化簡問題。這是計算機代數裏的基本工具，因為計算機代數系統會以此方式有系統的簡化分式。相對的，大部份最大公因式的現代理論也已經發展，以滿足計算機代數系統效率的要求。

定義

令p和q是多項式，其系數在整環F（多半是域或是整數）以內。多項式d是p和q的最大公因式是指多項式p和q除以多項式d都可以整除，而且d除以p和q的每一個公因式，都可以整除。每一對多項式（兩個都不為零）有最大公因式，若且唯若其系數在的整環F為唯一分解整環。

若F是域，且p和q沒有都為零，多項式d為兩者的最大公因式若且唯若p和q除以d都可以整除，而且多項式d是所有公因式中，次數最大的。若p = q = 0，則GCD為0，不過也有學者認為此情形下是未定義。

p和q的最大公因式常寫成gcd(p, q)，但此寫法不嚴謹，因為最大公因式不唯一。

最大公因式不唯一：若d是p和q的最大公因式，則多項式f也是最大公因式，若且唯若F內存在不為零的常數u，使得 $${\displaystyle f=ud}$$ 且 $${\displaystyle d=u^{-1}f.}$$

因此針對相同兩個多項式，存在多個相同次數的最大公因式，彼此之間只相差一個系數。

在整數的最大公因數裏，上述的不確定因素可以用選擇正的最大正因數來處理。兩個整數的最大正因數也是其正因數中最大的那個。但因為整數系數的多項式裏，沒有自然的全序關係，無法用以上方式處理。針對域上單變數的多項式，可以額外要求其最大公因式要是首一多項式（最高次項的系數是1），但在多變數的多項式中，無法以類似方式處理。

因此，像d = gcd(p, q)或gcd(p, q) = gcd(r, s)的等式其實是數學式的誤用，應該解讀為「d是p 和q的一個GCD」及「p和q的GCD和r和s的GCD是同一個集合」。而gcd(p, q) = 1表示兩多項式的公因式只有不為0的常數。此情形下，p和q是互質多項式。

性質

• 如以上所述，兩多項式有最大公因式，若其系數在域、整環，或是唯一分解整環上。
• 若c是p和q的公因式，則其最大公因式會整除c。
• ${\displaystyle \gcd(p,q)=\gcd(q,p).}$
• ${\displaystyle \gcd(p,q)=\gcd(q,p+rq)}$針對任何多項式r。此特性是輾轉相除法的基礎。
• 針對任何系數環裏的可逆元素k，${\displaystyle \gcd(p,q)=\gcd(p,kq)}$。
• 因此${\displaystyle \gcd(p,q)=\gcd(a_{1}p+b_{1}q,a_{2}p+b_{2}q)}$，針對任何使得${\displaystyle a_{1}b_{2}-a_{2}b_{1}}$可逆的純量${\displaystyle a_{1},b_{1},a_{2},b_{2}}$。
• 若${\displaystyle \gcd(p,r)=1}$，則${\displaystyle \gcd(p,q)=\gcd(p,qr)}$.
• 若${\displaystyle \gcd(q,r)=1}$，則${\displaystyle \gcd(p,qr)=\gcd(p,q)\,\gcd(p,r)}$.
• 針對二個系數是在域上的單變數多項式p和q，存在多項式a和b，使得${\displaystyle \gcd(p,q)=ap+bq}$，且p和q的所有總性組合除以${\displaystyle \gcd(p,q)}$都可以整除。（貝祖等式）。
• 三個或多個多項式的的最大公因式可以用類似兩多項式的作法來定義。可以用兩多項式的最大公因式，配合以下等式計算：$${\displaystyle \gcd(p,q,r)=\gcd(p,\gcd(q,r)),}$$和$${\displaystyle \gcd(p_{1},p_{2},\dots ,p_{n})=\gcd(p_{1},\gcd(p_{2},\dots ,p_{n})).}$$

計算最大公因式

有許多計算兩多項式最大公因式的方法，其中兩個如下：

1. 多項式因式分解（英語：Factorization of polynomials），找出兩個多項式的所有因式，再由其中找出兩個多項式的最大公因式。此方式只適用在簡單多項式的情形，一般情形下，多項式因式分解是比計算最大公因式更困難的事。
2. 輾轉相除法，用類似兩數字輾轉相除法的方式，計算兩多項式的最大公因式。

因式分解

若要用因式分解找出兩個多項式的最大公因式，首先要對兩個多項式作完整的分解。然後，將所有的公因式相…乘。此時，得到的公因式不一定會是首一多項式，因此可以乘以系數，使其變成首一多項式。最後會得到包括所有公因式，並且是首一多項式的最大公因式。

例1：找出x² + 7x + 6和x² − 5x − 6的最大公因式。

x² + 7x + 6 = (x + 1)(x + 6)

x² − 5x − 6 = (x + 1)(x − 6)

因此，其最大公因式為x + 1。

輾轉相除法

多項式的分解很困難，在多項式次數很高時更是如此。輾轉相除法是對任何次數多項式都適用的方式，是反覆的找兩個多項式，進行帶餘除法。兩個數字的輾轉相除法，每一次計算都都會讓數字變小。兩個多項式的輾轉相除法，每一次計算都都會讓多項式的次數。最後得到的非零餘式，若需要的話可以乘系數，使其成為首一多項式。

具體來說，要找到兩個多項式a(x)和b(x)的最大公因式，可以假設b ≠ 0（不然，最大公因式就是a(x)），以及 $${\displaystyle \deg(b(x))\leq \deg(a(x))\,.}$$

輾轉相除法可以得到兩個多項式：商式q(x)和餘式r(x)，使得 $${\displaystyle a(x)=q_{0}(x)b(x)+r_{0}(x)\quad {\text{and}}\quad \deg(r_{0}(x))<\deg(b(x))}$$

a(x)和b(x)都可以被g(x)整除，若且唯若b(x)和r₀(x)都可以被g(x)整除。因此 $${\displaystyle \gcd(a(x),b(x))=\gcd(b(x),r_{0}(x)).}$$ 令 $${\displaystyle a_{1}(x)=b(x),b_{1}(x)=r_{0}(x),}$$ 可以再使用輾轉相除法得到新的多項式 q₁(x), r₁(x), a₂(x), b₂(x)……。在每一步，下式都成立 $${\displaystyle \deg(a_{k+1})+\deg(b_{k+1})<\deg(a_{k})+\deg(b_{k}),}$$ 因此最後會得到 $${\displaystyle b_{N}(x)=0}$$ 而最大公因式為： $${\displaystyle \gcd(a,b)=\gcd(a_{1},b_{1})=\cdots =\gcd(a_{N},0)=a_{N}.}$$

例2：找出x² + 7x + 6和x² − 5x − 6的最大公因式：

x² + 7x + 6 = 1 ⋅ (x² − 5x − 6) + (12 x + 12)

x² − 5x − 6 = (12 x + 12) (1/12 x − 1/2) + 0

因為12 x + 12是最後一個非零的餘式，因此這是兩多項式的最大公因式，其首一最大公因式為x + 1。

此例中，很容易避免很複雜的系數，像是在第二步就可以找到12並且消去。這可以用偽餘序列（pseudo-remainder sequences）來處理，不過若不小心，可能會在計算中引入很大的整數。因此在電腦計算中，會使用其他的方式處理。

參考資料

引用

書目

• Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise. Algorithms in real algebraic geometry, chapter 4.2. Springer-Verlag. 2006.
• Davenport, James H.; Siret, Yvon; Tournier, Évelyne. Computer algebra: systems and algorithms for algebraic computation. Translated from the French by A. Davenport and J.H. Davenport. Academic Press. 1988. ISBN 978-0-12-204230-0.
• van Hoeij, M.; Monagan, M.B. Algorithms for polynomial GCD computation over algebraic function fields. ISSAC 2004: 297–304. 2004.
• Javadi, S.M.M.; Monagan, M.B. A sparse modular GCD algorithm for polynomials over algebraic function fields. ISSAC 2007: 187–194. 2007.
• Knuth, Donald E. The Art of Computer Programming II. Addison-Wesley. 1969: 370–371.
• Knuth, Donald E. Seminumerical Algorithms. The Art of Computer Programming 2 Third. Reading, Massachusetts: Addison-Wesley. 1997: 439–461, 678–691. ISBN 0-201-89684-2.
• Loos, Rudiger, Generalized polynomial remainder sequences, B. Buchberger; R. Loos; G. Collins (編), Computer Algebra, Springer Verlag, 1982
• Paola Boito: Structured matrix based methods for approximate polynomial GCD, Scuola Normale Superiore Pisa, ISBN 978-88-7642-380-2 (2011).