欧几里得算法

欧几里得算法（辗转相除法）用于求两数的最大公因子（GCD）。

原理

设 b 为大数，a 为小数，带余除法：b = q×a + r。关键在于 (b,a) = (a,r)，如此辗转，直到出现 (d, 0)，则 d 为最大公因子。

例如 30 与 18：30 = 1×18 + 12，18 = 1×12 + 6，12 = 2×6 + 0，故 gcd(30,18) = 6。

实现要点

1. 排序：大数在前、小数在后。

2. 用 Mod 或 QuotientRemainder 求余数，反复迭代直到余数为 0。

推广：多项式的结式

欧几里得算法可推广到多项式。设 P(w,z)、Q(w,z) 为两个互质多项式，则只有有限个 z₀ 使得 P(w,z₀)=0 与 Q(w,z₀)=0 有公共根。对 P、Q 做辗转相除，得到只含 z 的多项式 R(z)；若 R 不恒为零，则满足条件的 z₀ 必须使 R(z₀)=0，故仅有有限个。