最大公因式

两个多项式的最大公因式（最称GCD）是指此多项式是两多项式的因式，且不存在其他次数更高的公因式。最大公因式的概念类似两整数的最大公因数。

针对系数在域里的单变数多项式，可以像计算最大公因数一样，用多项式除法的辗转相除法计算最大公因式。可以得到的最大公因数，顶多会再乘以一个系数。

整数最大公因数和多项式最大公因式之间的类似之处，可以将所有用带余除法和辗转相除法可以推得的性质扩展到单变数多项式。而且，最大公因式有其特殊的性质，因此在代数的许多领域都会提到。一般来说，两多项式最大公因式的根也就是两个多项式的共同根，这就提供一个可以知道多项式根的资讯，但又不需真正求解的方式。例如，多项式的重根是该多项式以及其导数多项式最大公因式的根，而且最大公因式的计算，可以计算多项式的无平方因式分解（英语：square-free factorization），可提供多项式的根是原多项式特定重复度的根。

最大公因式也可以在整数域或是整数环上的多变数多项式里定义，或是在唯一分解整环上的多变数多项式里定义。只要在其其系数的环，存在最大公因数的算法，就有算法可以计算最大公因式。此算法是利用变体的辗转相除法，在变数的数量上递归，以化简问题。这是计算机代数里的基本工具，因为计算机代数系统会以此方式有系统的简化分式。相对的，大部分最大公因式的现代理论也已经发展，以满足计算机代数系统效率的要求。

定义

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