前置知识
在复数域 C 中,多项式 xn−1 有 n 个根: cos2πkn+isin2πkn,k=0,1,⋯,n−1 。由 Euler 公式,可以写作 e2πik/n=exp2πikn 。
以下为了方便,记 ωn=exp2πin ,则 ωkn=(ωn)k=exp2πikn 。在上下文已知的情况下,可以用 ω 代替 ωn (在某些文献中,用 ε 表达相同的含义)。
根据上述记号, xn−1 的 n 个根可以记作 1,ω,ω2,⋯,ωn−1
因此, 由 Vieta 定理(根与系数的关系),可以得到
性质 1.1: xn−1=(x−1)(x−ω)(x−ω2)⋯(x−ωn−1)
由初中的因式分解技巧,有 xn−1=(x−1)(xn−1+xn−2+⋯+x+1) ,于是就有
推论 1.1: xn−1+xn−2+⋯+x+1=(x−ω)(x−ω2)⋯(x−ωn−1)
在上式中代入任何一个 ωin, 即可得到:
推论 1.2:
单位根群
由公式 \omega_n^k=\exp\frac{2\pi\mathrm{i}k}{n} 得知,1, \omega_n, \omega_n^2, \cdots, \omega_n^{n-1} 关于乘法运算\cdot构成了一个 n 阶循环群 \omega_n 被称为单位根群 (Group of root or unity),其中 \omega_n 是 \omega_n 的一个生成元。
从而有 \omega_n^a \cdot \omega_n^b=\omega_n^{a+b},\left(\omega_n^a\right)^b=\omega_n^{a b}, \omega_n^k=\omega_{\lambda n}^{\lambda k} ,以及特殊地 \overline{\omega_n^k}=\omega_n^{-k}
提到群,自然就会想到它的生成元。那哪些元素会成为它的生成元呢?
如果一个单位根, 比如 \omega_6^2=\frac{-1+\sqrt{3} \mathrm{i}}{2}, 它其实也是一个 3 次的单位根, 因此它所生成的所有单位根都是 3 次的, 而不会生成 \omega_6=\frac{1+\sqrt{3} \mathrm{i}}{2} 。
由有限循环群的结论, \omega_n^k 是 \omega_n 的生成元,当且仅当 n \perp k ,即 (n, k)=1 。因此,这些满足 n \perp k 的单位根 \omega_n^k 有着特殊的性质,这就是我们即将讨论的重点。
辨析:
单位根: n 阶单位根是满足 x^n = 1 的复数根,这些根在复平面上均匀分布在单位圆上。单位根的一般形式为 \omega_n^k,其中 \omega_n = e^{2\pi i / n} 是一个主 n 阶单位根,而 k 是从 0 到 n-1 的整数。
本原单位根: 一个 n 阶本原单位根是一种特殊的单位根,它的任意次幂(除了 n 的倍数次)都不等于 1。具体地,如果 \omega_n^k 是一个 n 阶的本原单位根,那么对于任意非零整数 m < n ,都有 (\omega_n^k)^m \neq 1。
分圆多项式
如果一个 n 阶单位根 \omega_n^k, 满足对于任意的 i=1,2, \cdots, n-1, \omega_n^{k-i} \neq 1 (即 \omega_n^k 是群 \omega_n 的生成元), 则称 n 阶单位根 \omega_n^k 是本原的 (Primitive), \omega_n^k 称为本原单位根 (Primitive root of unity), 简称原根。
定理 3.1: \omega_n^k 是 n 阶本原单位根的充要条件是 n \perp k 。
由定理3.1,可知 n 阶本原单位根恰有 \phi(n) 个
上面提到过, 以所有 n 阶单位根为根的多项式为 x^n-1, 那么以所有 \phi(n) 个 n 阶本原单位根为根的多项式又有什么样的性质呢?这就是我们接下来要提到的分圆多项式。
定义分圆多项式 (Cyclotomic polynomial) 所有以 n 阶本原单位根为单根的首一多项式, 记作 \Phi_n(x), 即
注意到 n 个单位根将复平面上的单位圆 |z|=1 等分成了 n 等分, 因此得名为分圆多项式 (Cyclotomic)。
由于 n 阶本原单位根一共有 \phi(n) 个, 因此 n 阶分圆多项式的次数 \operatorname{deg} \Phi_n(x)=\phi(n), 这解释了为什么分圆多项式用 \Phi_n(x) 表示。
分圆多项式的一个最基础最重要的定理由下面的定理 3.2 给出。
定理 3.2: \prod_{d|n} \Phi_d(x)=x^n-1 。
证明:
证明这个定理之前,我们比较两边的次数,可以发现一个有趣的事实:\sum_{d|n}\phi(d)=n,这个的理解笔者刚学抽代的时候就有点迷糊,先给出该定理的证明(记录一下),之后再给出定理3.2的证明
1. 如果 $n=1$,$\phi(n)=\phi(1)=1=n$
2. 如果 $n$ 是质数,$\phi(n) = n-1$,因此有 $\phi(n)+\phi(1)=n$
3. 如果 $n$ 是一个质数的幂,即$n=p^k$,则有$\sum_{d \mid n} \phi(d)=\sum_{i=0}^k \phi\left(p^i\right)=\sum_{i=1}^k p^{i-1}(p-1)+1=p^k$
4. 如果 $n$ 是任意整数,则由整数环是唯一分解整环可得 $n=p_1^{k_1} p_2^{k_2} p_3^{k_3}\dots p_n^{k_n}$,有$\sum_{d|n}\phi(d)=\sum_{i_1=0}^{k_1}\sum_{i_2=0}^{k_2}\dots\sum_{i_n=0}^{k_n}\phi(p_1^{i_1} p_2^{i_2} p_3^{i_3}\dots p_n^{i_n})=n(相互独立互质,利用欧拉函数的积性)$
接下来我们证明定理3.2
给定一个 n 阶单位根 \omega_n^k, 我们定义 d=\operatorname{gcd}(n, k) 。这意味着我们可以将 n 和 k 分别写为 n=n_1d 和 k=k_1 d, 其中 \operatorname{gcd}\left(n_1, k_1\right)=1 。因此, \omega_n^k=\omega_{n_1 d}^{k_1 d}=\left(\omega_{n_1 d}^d\right)^{k_1}=\omega_{n}^{k_1} 。这里 \omega_{n_1}^{k_1} 是一个 n_1 阶单位根
由于 n_1 和 k_1 互质, 所以 \omega_{n_1}^{k_1} 实际上是一个 n_1 阶的本原单位根。这表明, 从任意 n 阶单位根出发, 通过适当的因子分解和简化, 总能找到一个相对 “更原始” 的单位根, 即某个较小阶数的本原单位根
互斥性:对于 n 的不同因数 d 和 d^{\prime}, 其中 d \neq d^{\prime}, d 阶的本原单位根和 d^{\prime} 阶的本原单位根是不同的。本原单位根的定义保证了它不能通过较小的幂次得到 1 , 这意味着两个不同阶数的本原单位根不可能相等。
对于 n 的每一个因数 d,一个 d 阶的本原单位根 \omega_d^e (其中 e 是小于 d 并与 d 互质的整数), 也是一个 n 阶单位根, 因为 \omega_d^e=\omega_{d /(n / d)}^{e(n / d)}=\omega_n^{e(n / d)}
从以上分析可知,所有 n 的因数 d 对应的 d 阶本原单位根的乘积实际上构成了多项式 x^n-1 的根(性质1.1)。因为 x^n-1 的根包括了所有 n 阶单位根, 而这些单位根又可以通过本原单位根表示。
在定理 3.2 的等式两端代入 n=p ( p 是素数), 由于 p 的因子只有 1 和 p, 就有 \Phi_1(x) \Phi_p(x)=x^p-1, 由于 \Phi_1(x)=x-1, 因此我们得到了
当 n 比较小时, \Phi_n(x) 的性状如下:
直觉告诉你, 分圆多项式的系数一定在 \{-1,0,1\} 的范围中 !
然而这却是假的。当 n=105 时,
进一步, 当 n=463505=5 \times 7 \times 17 \times 19 \times 41 时, \Phi_n(x) 的绝对值最大的系数竟有 -17310! 这也可以说明分圆多项式在 n 较大时的增长速度是非常迅猛的。
不过,虽然分圆多项式的系数很大,但是我们还是可以非常容易地求出它的值。因为如果对定理 3.2 的等式两端取对数,我们就能得到
可以看出,这是一个 Möbius 变换 (Dirichlet 前缀和) 的形式。因此,我们尝试使用 Möbius 反转变换,即
两边再取指数, 就有
于是我们就得到了一个计算 \Phi_n(x) 的表达式。
而定理 3.2 中的式子是一个分解式,所有的分圆多项式都是在 \mathbb{Z} 中不可约 (irreducible) 的。
参考
[1] https://yhx-12243.github.io/OI-transit/memos/17.html#mjx-eqn-2
[2] https://blog.csdn.net/ADjky/article/details/61198817