最大公因式

两个多项式的最大公因式（英语：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).