多項式最大公因式（polynomial GCD）

正如 12 與 18 共有最大公因數 6，兩個多項式也共有一個最大公因式——能整除兩者且無餘式的最高次多項式。對 x^2 - 1 與 x^2 - 2x + 1 而言，公因式是 (x - 1)。找出它是電腦代數中最基本的運算之一，因為你一旦知道兩個多項式的公因式，就能消去它、用它因式分解，或用它化簡一個分式。

方法是歐幾里得演算法，就是歐幾里得用於整數的同一想法，透過多項式長除法搬到多項式上。要求 gcd(a, b)（deg a >= deg b）：用 b 除 a 得餘式 r（次數嚴格更低），然後把這對 (a, b) 換成 (b, r) 並重複。每一步次數下降，所以餘式終會歸零，而最後一個非零餘式就是最大公因式（通常正規化成首一）。例如 gcd(x^2 - 1, x^2 - 2x + 1)：相減得餘式 2x - 2，再用 2x - 2 除 x^2 - 2x + 1 得餘式 0——所以最大公因式是 x - 1。多項式最大公因式是有理表達式中消去公因式的引擎，也是許多因式分解與化簡常式內部的第一步。

多項式最大公因式之所以重要，是因為它讓精確消去變得可靠，但它帶著符號計算的招牌警告。若天真地在有理數上做，中間餘式的係數會劇烈爆炸——這是表達式膨脹的教科書案例，兩個不起眼多項式的最大公因式途中竟經過巨怪般的中間分數。標準的解法很聰明：子結式演算法把係數成長控制住，而模運算最大公因式法在數個質數模下算出答案再重建它，完全繞開膨脹。連這麼基本的運算，都必須防範它自身的中間爆炸。