证明多项式Xⁿ-1与Xᵐ-1的最大公因式为X^(n,m)-1
这是多项式环里非常经典的一个结论，咱们一步步拆解证明过程，保证每一步都清晰：
第一步：先证 $X^{(n,m)} - 1$ 是 $f(X)=X^n-1$ 和 $g(X)=X^m-1$ 的公因式
设 $d = (n,m)$，也就是整数 $n$ 和 $m$ 的最大公约数。根据最大公约数的定义，存在整数 $k$ 和 $l$，使得 $n = dk$，$m = dl$。
利用多项式的因式分解公式：
$$X^{dk} - 1 = (Xd)k - 1 = (X^d - 1)(X^{d(k-1)} + X^{d(k-2)} + \dots + X^d + 1)$$
显然 $X^d - 1$ 整除 $X^{dk} - 1 = X^n - 1$。同理，$X^d - 1$ 也整除 $X^{dl} - 1 = X^m - 1$。
所以 $X^d - 1$ 是 $f(X)$ 和 $g(X)$ 的一个公因式。
第二步：再证 $X^{(n,m)} - 1$ 是 $f(X)$ 和 $g(X)$ 的最大公因式
根据贝祖定理（Bezout's Identity），对于整数 $n$ 和 $m$，存在整数 $s$ 和 $t$，使得：
$$sn + tm = d$$
我们对 $X^d - 1$ 做如下变形：
$$
\begin{align*}
X^d - 1 &= X^{sn + tm} - 1 \
&= (Xn)s \cdot (Xm)t - 1 \
&= (Xn)s \cdot (Xm)t - (Xn)s + (Xn)s - 1 \
&= (Xn)s \left[(Xm)t - 1\right] + \left[(Xn)s - 1\right]
\end{align*}
$$
现在观察右边的两项：
- 对于 $(Xn)s - 1$，显然 $X^n - 1$ 整除它（套用因式分解公式：$Y^s -1 = (Y-1)(Y^{s-1}+\dots+1)$，令 $Y=X^n$ 即可）；
- 对于 $(Xm)t - 1$，同理 $X^m -1$ 整除它。
假设 $h(X)$ 是 $f(X)$ 和 $g(X)$ 的任意一个公因式，那么 $h(X)$ 整除 $X^n -1$ 和 $X^m -1$，自然也整除上面的两项。因此 $h(X)$ 整除这两项的和，也就是 $X^d -1$。
这就说明，$X^d -1$ 是 $f(X)$ 和 $g(X)$ 的公因式中次数最高的那个（因为任何公因式都整除它），也就是它们的最大公因式。
综上，$(f,g) = X^{(n,m)} -1$ 得证。
内容的提问来源于stack exchange，提问作者user528021
