$x^n-1$问题

问题描述

请对下面的多项式$ A_n(x) $进行因式分解：

$$ A_n(x) = x^n - 1 \tag{1}$$

其中，$ n \in \text{N}^* $。

分析

对于$ n = 1$的情况，我们无需分解。对于$n = 2 $的情况，我们可以分解为$ (x - 1)(x + 1) $。
如果次数更高，这个问题就比较棘手。

对于这个问题，我们有如下的定理：

$$ m \mid n \Longrightarrow (x^m - 1) \mid (x^n - 1) \tag{2}$$

这个定理可以用多项式除法来验证。

因此，我们为了分解$(1)$式，首先用$\Theta(\sqrt{n})$的时间对$n$进行分解质因数，从而能找到$(1)$的几个因式，然后原始就可以表示成几个形如$(x^a - 1)(x^b - 1) \cdots (x^z - 1)$的形式，从而能够递归的继续分解。

然而我们需要注意一点：以$n=6$为例，$6$的因子有$1$、$2$、$3$和$6$。我们发现选择了$(x^6 - 1)$作为因式跟没选一样。然而选择其它的因子时发现更严重的问题：

$$ (x - 1) \mid (x^3 - 1) \Longrightarrow (x - 1) \nmid {x^6 - 1 \over x^3 - 1} $$

这样导致几个因子间会有冲突，因此我们无法直接选择因式。

为了解决这个问题，我们定义一系列的多项式$ p_n(x) $：

$$ p_n(x) = { x^n - 1 \over \prod_{i \mid n}p_i(x)} \; (i \neq n) \tag{3}$$

实际上，这些多项式只是将原本$ x^n - 1 $中的非本身因式去掉了，这样使得：

$$ (x - 1) \mid {x^6 - 1 \over p_3(x) } $$

因为

$$ {x^6 - 1 \over p_3(x) } = {x^6 - 1 \over {(x^3 - 1) / (x - 1)}} = (x - 1) \cdot {x^6 - 1 \over x^3 - 1} $$

这样，我们可以将任意的$ A_n(x) $表示为如下形式：

$$ A_n(x) = \prod_{i \mid n} p_i(x) \tag{4}$$

根据$(3)$式和$(4)$式，递推完$ p_n(x) $后，我们就可以将$ A_n(x) $中的每一项都求解出来。如果多项式除法的时间复杂度为$ \Theta(g(n)) $，那么我们可以在$ \Theta(n\sqrt{n} \cdot g(n)) + \Theta(\sqrt{n}) = \Theta(n\sqrt{n} \cdot g(n))$的时间内对$ A_n(x) $进行因式分解。