定义

设 $m$ 为正整数。

$m$ 次单位根：满足 $\zeta^m = 1$ 的复数 $\zeta$。
$m$ 次本原单位根：$\zeta$ 是 $m$ 次单位根，且对任何 $0 < k < m$，$\zeta^k \neq 1$。

$m$ 次分圆多项式定义为

$\Phi_m(x) = \prod_{\substack{1 \leq k \leq m \\ \gcd(k,m)=1}} (x - e^{2\pi i k/m})$

即以所有 $m$ 次本原单位根为根的首一多项式。次数为 $\deg \Phi_m = \varphi(m)$。

基本分解

引理 1：$x^m - 1 = \prod_{d \mid m} \Phi_d(x)$。

每个 $m$ 次单位根 $\zeta = e^{2\pi i k/m}$ 的阶为 $m/\gcd(k,m)$，按阶分类恰好对应 $m$ 的各个因子 $d$。

整系数性质

引理 2：$\Phi_m(x)$ 是首一整系数多项式。

证明（归纳法）：$m=1$ 时 $\Phi_1(x) = x-1$，显然。假设对 $n < m$ 成立。定义

$g_m(x) = \prod_{\substack{d \mid m \\ d < m}} \Phi_d(x)$

由归纳假设，$g_m(x)$ 是首一整系数多项式。由 $x^m - 1 = \Phi_m(x) \cdot g_m(x)$，用多项式长除法知 $\Phi_m \in \mathbb{Q}[x]$。

整系数：设 $\Phi_m = A^{-1} \tilde{\Phi}_m$（$A$ 为正整数，$\tilde{\Phi}_m$ 为本原整系数多项式）。则 $A(x^m-1) = \tilde{\Phi}_m \cdot g_m$。由 Gauss 引理（多项式版本），$\tilde{\Phi}_m \cdot g_m$ 是本原多项式（$A$ 为正整数，$\tilde{\Phi}_m$ 为本原整系数多项式）。则 $A(x^m-1) = \tilde{\Phi}_m \cdot g_m$。由 Gauss 引理（多项式版本），$\tilde{\Phi}_m \cdot g_m$ 是本原多项式，但左边系数公因数为 $A$，故 $A=1$，$\Phi_m \in \mathbb{Z}[x]$。

无平方因子

引理 3：设 $p$ 为不整除 $m$ 的素数，则 $x^m - 1$ 模 $p$ 约化后无平方因子。

证明：引入形式导数（参见形式导数与重根的判别）。若 $x^m-1$ 模 $p$ 有平方因子，则它与 $(x^m-1)' = mx^{m-1}$ 有非常数公因子。但 $m \not\equiv 0 \pmod{p}$（因 $p \nmid m$），且 $x$ 与 $x^m-1$ 互素，故 $\gcd(x^m-1, mx^{m-1}) = 1$。

阶的刻画

引理 4（桥梁引理）：设 $a \in \mathbb{Z}$，$p$ 为素数，且 $p \nmid am$。若 $\Phi_m(a) \equiv 0 \pmod{p}$，则 $\mathrm{ord}_p(a) = m$。

证明：$\Phi_m(a) \mid a^m-1$ 推出 $a^m \equiv 1 \pmod{p}$，故 $\mathrm{ord}_p(a) = k$ 整除 $m$。

若 $k < m$，则 $a^k \equiv 1 \pmod{p}$，故 $x^k - 1$ 以 $a$ 为根。由于 $k \mid m$ 且 $k < m$，$x^k - 1$ 整除 $g_m(x) = \prod_{d \mid m, d < m} \Phi_d(x)$，所以 $g_m(a) \equiv 0 \pmod{p}$。同时 $\Phi_m(a) \equiv 0 \pmod{p}$，这意味着 $x^m-1$ 模 $p$ 有重根 $a$，与引理 3 矛盾。故 $k = m$。

算术函数与 Dirichlet 卷积

算术函数是定义在正整数上的复值函数

$f:\mathbb Z_{>0}\to\mathbb C.$

数论中常见的算术函数包括常值函数 $\mathbf 1(n)=1$、恒等函数 $\operatorname{id}(n)=n$、Möbius 函数 $\mu(n)$ 和 Euler 函数 $\varphi(n)$。

乘性函数

若 $f(1)=1$，并且对所有互素正整数 $m,n$ 都有

$f(mn)=f(m)f(n),$

则称 $f$ 为乘性函数。若不要求 $\gcd(m,n)=1$ 仍成立，则称为 完全乘性函数。

乘性函数由它在素数幂上的值完全决定。若

$n=p_1^{a_1}\cdots p_r^{a_r},$

则

$f(n)=\prod_{i=1}^r f(p_i^{a_i}).$

Dirichlet 卷积

两个算术函数 $f,g$ 的 Dirichlet 卷积定义为

$(f*g)(n)=\sum_{d\mid n}f(d)g\left(\frac nd\right).$

卷积满足交换律、结合律和分配律。其单位元为

\[\begin{cases} 1,&n=1,\\ 0,&n>1. \end{cases}$$ 即 $f*\varepsilon=f$。若 $f,g$ 都是乘性函数，则 $f*g$ 也是乘性函数。因此许多“对全部因子求和”的恒等式，都可以写成算术函数的代数运算。 --- ## Möbius 函数 ### 定义 Möbius 函数 $\mu:\mathbb Z_{>0}\to\{-1,0,1\}$ 定义为 \]

\mu(n)= \begin{cases} 1,&n=1,\ (-1)^r,&n=p_1p_2\cdots p_r,\quad p_1,\ldots,p_r\text{ 互不相同},\ 0,&\text{存在素数 }p\text{ 使 }p^2\mid n. \end{cases}

\[ 也就是说： - $n$ 含平方因子时，$\mu(n)=0$； - $n$ 无平方因子且有偶数个不同素因子时，$\mu(n)=1$； - $n$ 无平方因子且有奇数个不同素因子时，$\mu(n)=-1$。例如 | $n$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $8$ | $10$ | $12$ | $30$ | |:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:| | $\mu(n)$ | $1$ | $-1$ | $-1$ | $0$ | $-1$ | $1$ | $0$ | $1$ | $0$ | $-1$ | ### 乘性 $\mu$ 是乘性函数。若 $\gcd(m,n)=1$： - 只要 $m$ 或 $n$ 含平方因子，$mn$ 也含平方因子，两边都为 $0$； - 若 $m,n$ 都无平方因子，其素因子集合不相交，故不同素因子的个数相加，从而 $\mu(mn)=\mu(m)\mu(n)$。但 $\mu$ 不是完全乘性的，例如 $$\mu(2)^2=1,\qquad \mu(4)=0.$$ ### 基本因子和恒等式 Möbius 函数最重要的性质是 $$\boxed{\sum_{d\mid n}\mu(d)= \begin{cases} 1,&n=1,\\ 0,&n>1. \end{cases}}$$ 若 $n>1$ 的不同素因子为 $p_1,\ldots,p_r$，只有无平方因子 $d$ 对和式有贡献，因此 \]

\sum_{d\mid n}\mu(d) =\prod_{i=1}^r(1+\mu(p_i)) =\prod_{i=1}^r(1-1)=0.

\[ 用 Dirichlet 卷积表示，就是 $$\boxed{\mathbf 1*\mu=\varepsilon.}$$ 因此 $\mu$ 是常值函数 $\mathbf 1$ 关于 Dirichlet 卷积的逆元。 ### Möbius 反演公式 > **定理（Möbius 反演）**：若两个算术函数满足 > $$g(n)=\sum_{d\mid n}f(d),$$ > 则 > $$\boxed{f(n)=\sum_{d\mid n}\mu(d)g\left(\frac nd\right) > =\sum_{d\mid n}\mu\left(\frac nd\right)g(d).}$$ 用卷积记号，前提是 $g=\mathbf 1*f$。两边与 $\mu$ 卷积： \]

\mug=\mu(\mathbf 1f) =(\mu\mathbf 1)f =\varepsilonf=f.

\[ 这说明 Möbius 反演本质上是在“对全部因子求和”之后，用 $\mu$ 消去较小因子的累积贡献。 ### 加权反演更一般地，若 $$g(n)=\sum_{d\mid n}f(d)h\left(\frac nd\right),$$ 即 $g=f*h$，并且 $h(1)\ne0$，则 $h$ 存在唯一的 Dirichlet 卷积逆元 $h^{-1}$，从而 $$f=g*h^{-1}.$$ 普通 Möbius 反演就是 $h=\mathbf 1$、$h^{-1}=\mu$ 的特殊情形。 --- ## Euler 函数 ### 定义 Euler 函数（欧拉函数）$\varphi(n)$ 定义为 \]

\varphi(n)=#{1\le a\le n:\gcd(a,n)=1} =\left|(\mathbb Z/n\mathbb Z)^\times\right|.

\[ 它既计算模 $n$ 的简化剩余系中元素的个数，也等于 $n$ 次本原单位根的个数，因此 $$\boxed{\deg\Phi_n(x)=\varphi(n).}$$ 更完整的群论和 Euler 定理讨论参见 [中国剩余定理与Euler定理](/notes/crt-euler#欧拉函数|欧拉函数)。 ### 素数幂与一般公式对于素数幂 $p^k$，$1,\ldots,p^k$ 中不与 $p^k$ 互素的数恰好是 $p$ 的倍数，共有 $p^{k-1}$ 个，所以 $$\varphi(p^k)=p^k-p^{k-1}=p^k\left(1-\frac1p\right).$$ $\varphi$ 是乘性函数。若 $$n=p_1^{a_1}\cdots p_r^{a_r},$$ 则 \]

\boxed{\varphi(n) =n\prod_{p\mid n}\left(1-\frac1p\right) =\prod_{i=1}^r p_i^{a_i-1}(p_i-1).}

\[ 它不是完全乘性的，例如 $$\varphi(2)\varphi(2)=1,\qquad \varphi(4)=2.$$ ### 因子和恒等式将 $n$ 次单位根按其精确阶 $d\mid n$ 分类。阶恰为 $d$ 的单位根有 $\varphi(d)$ 个，而全部 $n$ 次单位根共有 $n$ 个，因此 $$\boxed{\sum_{d\mid n}\varphi(d)=n.}$$ 用 Dirichlet 卷积表示为 $$\mathbf 1*\varphi=\operatorname{id}.$$ 对它作 Möbius 反演可得 \]

\boxed{\varphi(n) =\sum_{d\mid n}\mu(d)\frac nd =n\sum_{d\mid n}\frac{\mu(d)}d.}

\[ 由于只有无平方因子的 $d$ 有贡献， \]

n\sum_{d\mid n}\frac{\mu(d)}d =n\prod_{p\mid n}\left(1-\frac1p\right),

\[ 这再次给出 Euler 函数的乘积公式。 ### 与本原单位根的关系任取一个本原 $n$ 次单位根 $\zeta_n=e^{2\pi i/n}$。所有本原 $n$ 次单位根恰为 $$\zeta_n^a,\qquad 1\le a\le n,\quad \gcd(a,n)=1.$$ 因此本原单位根的个数是 $\varphi(n)$，而分圆多项式可写成 \]

\Phi_n(x)= \prod_{\substack{1\le a\le n\\gcd(a,n)=1}} (x-\zeta_n^a).

\[ 这解释了为什么 Euler 函数自然地成为分圆多项式的次数。 --- ## Möbius 反演与分圆多项式 ### 乘积反演基本分解 $$x^n-1=\prod_{d\mid n}\Phi_d(x)$$ 是一个“对全部因子取乘积”的关系。其乘法形式的 Möbius 反演给出 \]

\boxed{\Phi_n(x) =\prod_{d\mid n}(x^d-1)^{\mu(n/d)} =\prod_{d\mid n}(x^{n/d}-1)^{\mu(d)}.}

\[ 公式中可能出现指数 $-1$，所以右侧表面上是有理函数；但因各因子发生精确消去，最终结果仍是整数系数多项式。严格地说，不必依赖复对数。设 $$H_n(x)=\prod_{d\mid n}(x^d-1)^{\mu(n/d)}.$$ 代入 $x^d-1=\prod_{e\mid d}\Phi_e(x)$ 后，$\Phi_e(x)$ 在 $H_n(x)$ 中的总指数为 \]

\sum_{\substack{d\mid n\e\mid d}}\mu\left(\frac nd\right) =\sum_{k\mid n/e}\mu\left(\frac{n/e}{k}\right)

\begin{cases} 1,&e=n,\ 0,&e<n. \end{cases}

\[ 故 $H_n(x)=\Phi_n(x)$。 ### 例：计算 $\Phi_{12}(x)$ $12$ 的因子为 $1,2,3,4,6,12$。只有 \]

\mu(12)=0,\quad \mu(6)=1,\quad \mu(4)=0,\quad \mu(3)=-1,\quad \mu(2)=-1,\quad \mu(1)=1

\[ 可能贡献，因此 \]

\Phi_{12}(x) =\frac{(x^{12}-1)(x^2-1)} {(x^6-1)(x^4-1)} =x^4-x^2+1.

\[ ### 次数公式对分圆恒等式比较次数： $$n=\deg(x^n-1)=\sum_{d\mid n}\deg\Phi_d =\sum_{d\mid n}\varphi(d).$$ 反过来，对 $\sum_{d\mid n}\varphi(d)=n$ 作 Möbius 反演，得到 \]

\deg\Phi_n=\varphi(n) =\sum_{d\mid n}\mu(d)\frac nd.

\[ 所以 $\mu$ 负责从“全部 $n$ 次单位根”中排除来自真因子阶的根，而 $\varphi$ 记录排除之后剩余的本原根数量。这正是两种算术函数在分圆多项式中同时出现的原因。 --- ## 具体例子 | $m$ | $\Phi_m(x)$ | |:---:|:---| | 1 | $x - 1$ | | 2 | $x + 1$ | | 3 | $x^2 + x + 1$ | | 4 | $x^2 + 1$ | | 5 | $x^4 + x^3 + x^2 + x + 1$ | | 6 | $x^2 - x + 1$ | 低阶分圆多项式的系数都在 $\{-1, 0, 1\}$ 中，但高阶时不一定如此。 --- ## 关键应用引理 4 是连接分圆多项式理论与原根理论的桥梁： - **原根存在性**：$\Phi_{p-1}(x)$ 模 $p$ 的根给出阶为 $p-1$ 的元素，即模 $p$ 的原根。 - **Dirichlet 定理（$b=1$）**：考虑 $\Phi_m(mN)$ 的素因子，由引理 4 知其给出 $p \equiv 1 \pmod{m}$ 的素数，类似欧几里得证明素数无穷多的精神。详见 [原根](/notes/primitive-roots)。\]