分圆多项式与分圆域

· · 题解

前置芝士：域论初步

复数域上，方程

x^n=1

有且仅有 n 个根 \omega_n,\omega_n^2,\cdots,\omega_n^n，其中 \omega_n=e^{\frac{2\pi i}{n}}。

考虑 x^n-1 在 \mathbb{Q} 上的因式分解。
注意到，\omega_n,\omega_n^2,\cdots,\omega_n^n 关于复数乘法构成循环群，\omega_n^k 为其生成元当且仅当 k 与 n 互质，
故定义 分圆多项式

\Phi_n(x)=\prod_{k=1}^n(x-\omega_n^k)^{[\gcd(n,k)=1]}

则

x^n-1=\prod_{k=1}^n(x-\omega_n^k)=\prod_{d|n}\prod_{k=1}^n(x-\omega_n^k)^{[\gcd(n,k)=d]} =\prod_{d|n}\prod_{k=1}^{\frac{n}{d}}(x-\omega_{\frac{n}{d}}^k)^{[\gcd(\frac{n}{d},k)=1]}=\prod_{d|n}\Phi_{\frac{n}{d}}(x)=\prod_{d|n}\Phi_d(x)

于是由莫比乌斯反演即可得到计算分圆多项式的一个方法

\ln(x^n-1)=\sum_{d|n}\ln\Phi_d(x) \ln \Phi_n(x)=\sum_{d|n}\mu\left(\dfrac{n}{d}\right)\ln(x^d-1) \Phi_n(x)=\prod_{d|n}(x^d-1)^{\mu\left(\frac{n}{d}\right)}\quad(1)

因为 \mu(n)\in\{1,-1\},x^n-1,\dfrac{1}{x^n-1}=-\displaystyle\sum_{k=0}^{+\infty}x^{nk}\in\Z[[x]]，

故 \Phi_n(x)\in\Z[x]，即 分圆多项式一定是整系数多项式。

求证：\Phi_n(x) 在 \mathbb{Q} 上不可约。
证明：由高斯引理，设 \Phi_n(x)=f(x)g(x)\ (f(x),g(x)\in\Z[x])，

$\qquad$ 设 $\omega_n$ 为 $f(x)$ 的根，则只需要证明对于任意与 $n$ 互质的正整数 $m$， $\qquad\ \omega_n^m$ 是 $f(x)$ 的根即可。将 $m$ 质因数分解，于是相当于证明， $\qquad$ 若 $\alpha$ 为 $f(x)$ 的一个根，则对于任意小于 $n$，且不是 $n$ 的质因子的的质数 $p$， $\qquad\ \alpha^p$ 也是 $f(x)$ 的一个根。 $\qquad$ 假设 $\alpha^p$ 不是 $f(x)$ 的根，即 $\alpha^p$ 是 $g(x)$ 的根，那么 $\alpha$ 就是 $f(x)$ 和 $g(x^p)$ 的公共根。 $\qquad$ 又因为 $f(x)$ 是 $\alpha$ 在 $\mathbb{Q}$ 上的极小多项式，故 $g(x^p)\bmod f(x)=0$， $\qquad$ 于是设 $g(x^p)=f(x)h(x)$，由高斯引理可得 $h(x)\in\Z[x]$。 $\qquad$ 将等式 $g(x^p)=f(x)h(x)$ 中各多项式的系数对 $p$ 取模，得 $$g(x^p)\equiv f(x)h(x)\pmod{p}$$ $\qquad$ 根据弗洛尼乌斯自同态， $$g^p(x)\equiv f(x)h(x)\pmod{p}$$ $\qquad$ 因此 $\pmod{p}$ 意义下 $f(x)$ 是 $g(x)$ 的因式。又因为 $$x^n-1\equiv f(x)g(x)\pmod{p}$$ $\qquad$ 故 $x^n-1$ 在 $\Z_p$ 上不可分，即在分裂域上有重根。又因为 $n$ 与 $p$ 互质，故在 $\Z_p[x]$ 中有 $$\gcd(x^n-1,(x^n-1)')=\gcd(x^n-1,nx^{n-1})=\gcd(x^n-1,x^{n-1})=1$$ $\qquad$ 即 $x^n-1$ 在 $\Z_p$ 上可分，产生矛盾。因此 $\Phi_n(x)$ 在 $\mathbb{Q}$ 上不可约。

由上可得，x^n-1 在 \mathbb{Q} 上的因式分解就是

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

除了直接使用式 (1) 计算单个分圆多项式外，我们还可从 (1) 总结出以下性质线性筛出 \Phi_n(x)：

  1. 若素数 p 是 n 的质因子，则 \Phi_{pn}(x)=\Phi_n(x^p)
  2. 若素数 p 与 n 互质，则 \Phi_{pn}(x)=\dfrac{\Phi_n(x^p)}{\Phi_n(x)}

这就是本题的解法。

分圆域及其自同构群

将 \omega_n 加入 \mathbb{Q} 中产生的单扩域 \mathbb{Q}(\omega_n) 称为 n 次分圆域。
由刚才的讨论可知，\omega_n 在 \mathbb{Q} 上的极小多项式为 \Phi_n(x)，
故 [\mathbb{Q}(\omega_n):\mathbb{Q}]=\deg\Phi_n(x)=\varphi(n)，\varphi 为欧拉函数。

讨论 \mathbb{Q}(\omega_n) 上的自同构，则对于任意的 \sigma\in\operatorname{Aut}(\mathbb{Q}(\omega_n))，必有

\sigma(\omega_n)=\omega_n^m\quad (\gcd(n,m)=1)

于是

\sigma(\omega_n^k)=(\omega_n^m)^k=\omega_n^{mk}

又因为 (\omega_n^{m_1})^{m_2}=\omega_n^{m_1m_2}，故 n 次分圆域的自同构群与整数模 n 乘法群 \Z_n^\times 同构。
其中，m\in\Z_n^\times 对应同构映射 \sigma(\omega_n)=\omega_n^m。