本原单位根

在复数域$C$中，对于多项式$x^n-1$有$n$个根：

$x=\cos\frac {2\pi k}n+i\sin \frac {2\pi k}n,k=0,1,...,n-1$

根据欧拉公式：

$e^{ix}=\cos(x)+i\sin(x)$

可以写成$x=e^{\frac{2\pi ik}n}=\exp \frac{2\pi ik}n$。

$\exp$是指数函数的缩写。

可以记$\omega_n=\exp \frac{2\pi i}n$，能得到$\omega_n^k=\exp \frac{2\pi ik}n$。那么$x^n-1$的根可以写成$1,\omega,…,\omega^{n-1}$。可以将这个多项式转化：

$x^n-1=(x-1)(x-\omega)...(x-\omega^{n-1})$

根据公式$\omega_n^k=\exp \frac{2\pi ik}n$，这$n$个数关于乘法构成了$n$阶循环群（单位根群），$\omega_n$是这个群的一个生成元。

如果一个$n$阶单位根$\omega^k_n$，满足对于任意$i=1,2,…,n-1$，$\omega^{ki}_i≠1$，那么这个单位根就是本原单位根，简称原根。

定理：$\omega^k_n$是$n$阶本原单位根的充要条件是$(n,k)=1$。

$n$阶原根有$\phi(n)$个。

分圆多项式

已知所有$n$阶单位根为根的多项式为$x^n-1$，定义分圆多项式是所有以$n$阶原根为单根的首一多项式，记作$\Phi_n(x)$：（规定$(k,n)=1$）

$\Phi_n(x)=\prod_{1≤k≤n}(x-\omega^k_n)$

$n$个单位根将复平面单位圆进行了$n$等分，得名分圆多项式。

$n$阶本原单位根一共有$\phi(n)$个，所以$n$阶分圆多项式次数$\deg\Phi_n(x)=\phi(n)$。

一个重要的定理：

$\prod_{d|n}\Phi_d(x)=x^n-1$

对于数$n$和欧拉函数$\phi(x)$，有一个关系：
$\sum_{d|n}\phi(d)=n$

当上面定理的$n=p$时，$p$因子只有$1,p$，所以得到：

$\Phi_1(x)\Phi_p(x)=x^p-1$

由于$\Phi_1(x)=X-1$，所以能求得高次质数的分圆多项式：

$\Phi_p(x)=\frac{x^p-1}{x-1}=x^{p-1}+x^{p-2}+...+1$

这里利用到因式分解的一个小技巧：
$x^n-1=(x-1)(x^{n-1}+x^{n-2}+...+x+1)$

列举一些低阶的分圆多项式：

注意分圆多项式不是三值多项式，当$n$增大时，会出现更大的系数。

现在学习如何计算$\Phi_n(x)$的表达式，对上面定理的公式进行取对数（注意求积运算变为求和）：

$\log(x^n-1)=\sum_{d|n}\log\Phi_d(x)$

这里需要用到Möbius反转变换，将上式变为：

$\log\Phi_n(x)=\sum_{d|n}\mu(\frac nd)\log(x^d-1)$

这里的$\mu$是莫比乌斯函数，定义：

当$n=1$时，$\mu(n)=1$。

当$n$是$k$个不同质数的乘积，$\mu(n)=(-1)^k$。

当$n$有重复的质因数，$\mu(n)=0$。

两边取指数：

$\Phi_n(x)=\prod_{d|n}(x^d-1)^{\mu(\frac nd)}$

分圆多项式是整系数多项式，且在整数多项式环$Z[x]$中不可约。

当$n＞1$时，分圆多项式的系数对称。

当$n＞1$时，$\Phi_n(x)$的一次项系数等于$-\mu(n)$。

一个公式：

$\Phi_{2^d}(x)=x^{2^{d-1}}+1$