x^n-1问题
riteme.site

$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) $进行因式分解。