最大公因式

兩個多項式的最大公因式（英語：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})).}$$

參考資料

引用

書目

• 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).