最大公因式

兩個多項式的最大公因式（，简稱GCD）是指此多項式是兩多項式的因式，且不存在其他次數更高的公因式。最大公因式的概念類似兩整數的最大公因數。

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

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

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

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

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

和的最大公因式常寫成，但此寫法不嚴謹，因為最大公因式不唯一。

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

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

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

因此，像或的等式其實是數學式的誤用，應該解讀為「是 和的一個GCD」及「和的GCD和和的GCD是同一個集合」。而表示兩多項式的公因式只有不為0的常數。此情形下，和是**'。

性質
*如以上所述，兩多項式有最大公因式，若其係數在域、整環，或是唯一分解整環上。
*若是和的公因式，則其最大公因式會整除。
*\gcd(p,q)= \gcd(q,p).
*\gcd(p, q)= \gcd(q,p+rq)針對任何多項式。此特性是輾轉相除法的基礎。
*針對任何係數環裡的可逆元素，\gcd(p,q)=\gcd(p,kq)。
*因此\gcd(p,q)=\gcd(a_1p+b_1q,a_2p+b_2q)，針對任何使得a_1 b_2 - a_2 b_1可逆的純量a_1, b_1, a_2, b_2。
*若\gcd(p, r)=1，則\gcd(p, q)=\gcd(p, qr).
*若\gcd(q, r)=1，則\gcd(p, qr)=\gcd(p, q)\,\gcd(p, r).
*針對二個係數是在域上的單變數多項式和，存在多項式和，使得\gcd(p,q)=ap+bq，且和的所有總性組合除以\gcd(p,q)都可以整除。（貝祖等式）。
*三個或多個多項式的的最大公因式可以用類似兩多項式的作法來定義。可以用兩多項式的最大公因式，配合以下等式計算：\gcd(p, q, r) = \gcd(p, \gcd(q, r)),和\gcd(p_1, p_2, \dots , p_n) = \gcd( p_1, \gcd(p_2, \dots , p_n)).

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

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

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

例1：找出和的最大公因式。

因此，其最大公因式為。

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

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

輾轉相除法可以得到兩個多項式：商式和餘式，使得
a(x) = q_0(x) b(x) + r_0(x)
\quad \text{and} \quad
\deg(r_0(x))

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

例2：找出和的最大公因式：

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

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

參考資料
引用
書目
*
*
*
*
*
*
*

• Paola Boito: Structured matrix based methods for approximate polynomial GCD, Scuola Normale Superiore Pisa, ISBN 978-88-7642-380-2 (2011).