充分性证明

下面我们证明：$Q_k \times Q_{k+e}$ 可以表示成上一层 $P_v$ 的线性组合。
我们要算的乘积是 $Q_k \times Q_{k+e}$。我们把这两个多项式具体写出来：

1. $Q_k$ 的展开式：它的指数是从 $k$ 开始，每次跳 $E$ 步。共有 $F$ 项。
   $Q_k = \zeta^{g^k} + \zeta^{g^{k+E}} + \zeta^{g^{k+2E}} + \dots + \zeta^{g^{k+(F-1)E}}$
   为了方便，我们用变量 $j$ 代表第几项，即里面的元素形如 $\zeta^{g^{k+jE}}$ （$j$ 从 $0$ 到 $F-1$）。

2. $Q_{k+e}$ 的展开式：它的起点比 $Q_k$ 多走了半步（即加了 $e$），每次也是跳 $E$ 步。
   $Q_{k+e} = \zeta^{g^{k+e}} + \zeta^{g^{k+e+E}} + \dots + \zeta^{g^{k+e+(F-1)E}}$
   我们用变量 $r$ 代表它的第几项，即里面的元素形如 $\zeta^{g^{k+e+rE}}$ （$r$ 从 $0$ 到 $F-1$）。

现在，把这两个长长的多项式相乘（利用分配律，即左边的每一项都要和右边的每一项相乘）。
总共会产生 $F \times F = F^2$ 个项。
根据指数的乘法法则 $\zeta^A \times \zeta^B = \zeta^{A+B}$，这 $F^2$ 个项的指数（在模 $p$ 意义下）都可以统一写成这样的“加和形式”：

$\text{指数和 } S = g^{k+jE} + g^{k+e+rE} \pmod p$    (式 6.2)
(其中 $j$ 和 $r$ 独立地在 $0$ 到 $F-1$ 之间遍历组合)

这 $F^2$ 个项看起来乱七八糟，怎么知道它们加起来是个什么东西呢？
高斯的魔法在于：不要去硬算，去寻找它们内部的对称性。
我们下面要分四个方面证明乘积的对称性。

1. 我们要证明，乘积结果的每一项，依然在所有被分组的根中，即在 $\zeta^1 \dots \zeta^{p - 1}$ 之中，不会出现 $\zeta^p$（即不会出现 $1$)
2. 我们要证明，如果 $\zeta^{g^k}$ 出现在了乘积结果中，$\zeta^{g^{k + E}}$ 也必定在乘积结果中而且出现的次数相同，这说明如果 $Q_v$ 中的一个根在乘积结果中，整个 $Q_v$ 都在乘积结果中，且每个根出现次数相同。
3. 我们要证明，如果 $\zeta^{g^k}$ 出现在了乘积结果中，$\zeta^{g^{k + e}}$ 也必定在乘积结果中而且出现的次数相同，这说明如果 $Q_v$ 的根都在乘积结果中出现 $A$ 次，那么 $Q_{v+e}$ 的根也都在乘积结果中出现 $A$ 次。这说明 $P_v$ 中的每个根都在乘积结果中出现了相同的 $A$ 次。
4. 我们要证明，只要 $Q_k$ 中根的个数大于 $1$，如果 $\zeta^x$ 在某个组 $Q_k$ 中，那么 $\zeta^{-x}$ 也必定在 $Q_k$ 中，从而保证 $Q_k$ 中的所有根求和后虚部会相互抵消。即任意分组的求和都是实数。

上面的性质 1，2，3 保证了 $Q_k \times Q_{k+e}$ 可以表示成上一层 $P_v$ 的整系数线性组合，又知道 $Q_k + Q_{k+e} = P_k$，只要先求出所有上层 $P_v$ 的值，根据韦达定理，就可以通过解二次方程的方法求出 $Q_k$ 和 $Q_{k+e}$。性质 4 保证了二次方程的解一定是实数，也就是每次开根号的内部一定是正实数。那么所有求解都可以通过尺规作图完成。

随着分组的细化，最后必然能求出只有 $\zeta$ 和 $\zeta^{-1}$ 的组的根的和，即能求出 $\zeta + \zeta^{-1}$ 的值。而
$\cos(\frac{2\pi}{p}) = \frac{1}{2}(\zeta + \zeta^{-1})$
这样我们就求出了最终的 $\cos(\frac{2\pi}{p})$。

现在我们来依次证明上面的性质 1，2，3，4

「性质1」的证明：乘积中绝对不会出现常数项 $\zeta^0 = 1$
我们要证明，不论 $j$ 和 $r$ 取何值，指数之和绝对不可能为 $0$。假设存在某一项等于 $1$，即：

$g^{k+jE} + g^{k+e+rE} \equiv 0 \pmod p$

这意味着两个数互为相反数：

$g^{k+e+rE} \equiv -g^{k+jE} \pmod p$

在模 $p$ 的原根世界里，$-1$ 的指数是多少呢？因为 $g^{p-1} \equiv 1 \pmod p$，考虑方程：$x^2 \equiv 1\pmod p$，可分解为：$(x + 1)(x - 1) \equiv 0$，因为 $x \equiv 1$ 不在原根的幂次中，所以原根幂次中的解只能是 $x \equiv -1$。另一方面，因为 $p$ 是费马素数，$(p-1)/2$ 是正整数，所以 $g^{(p-1)/2}$ 在原根的幂次中。$(g^{(p-1)/2})^2 \equiv g^{p - 1} \equiv 1$，所以 g^{(p-1)/2} 是 $x^2 \equiv 1$ 在原根幂次中的解，因此必有：

$-1 \equiv g^{(p-1)/2} \pmod p$    (式 6.3)

因为 $p$ 是费马素数 $2^m + 1$，所以 $(p-1)/2 = 2^{m-1}$。我们将 $-1$ 替换为指数形式，等式变为：

$g^{k+e+rE} \equiv g^{k+jE + 2^{m-1}} \pmod p$

由于原根的不同幂次（指在模 $p - 1$ 意义下不同的幂次）两两不同，要让两边的结果相等，它们的指数在模 $p-1$（即 $2^m$）意义下必须同余：

$k+e+rE \equiv k+jE + 2^{m-1} \pmod{2^m}$

两边同时减去 $k$，并提取 $E$：
$e + (r-j)E \equiv 2^{m-1} \pmod{2^m}$

别忘了，高斯的拆分规则是 $E = 2e$。我们在等式两边同时除以 $e$（注意模也要变化，数论中如果 $a \cdot c \equiv b \cdot c \pmod M$，那么两边同时约去 $c$ 时，模数 $M$ 必须变成 $\frac{M}{\gcd(c, M)}$，只有和模互素的数才可以模不变直接约去）

$1 + 2(r-j) \equiv \frac{2^{m-1}}{e} \pmod{\frac{2^m}{e}}$

请仔细观察这个式子！等号左边 $1 + 2(r-j)$ 显然是一个奇数。等号右边的 $\frac{2^{m-1}}{e}$ 是什么呢？
分为 $E$ 组时每组最少有2个元素，所以分为 $e$ 组时每组最少有4个元素，一共有 $p - 1 = 2^m$ 个元素，所以 $e$ 最大只能是 $2^{m - 2}$，所以右边 $\frac{2^{m-1}}{e}$ 一定是2的幂次，它必然是一个偶数！一个奇数怎么可能在模一个偶数的情况下，和另一个偶数同余呢？这在数学上是绝对矛盾的。因此，假设不成立！展开式中绝对不会有任何两项加起来等于 $0$，乘积中永远不会出现幽灵常数 $1$。

「性质2」与「性质3」的合并证明：
我们要证明，乘积 $Q_k \times Q_{k+e}$ 展开后的 $F^2$ 个项并非杂乱无章，而是必然能打包成完整的 $Q_v$ 组（性质2），并且这些 $Q_v$ 还能两两配对，完美组合成上一层的 $P_v$（性质3）。
为了看清这种代数结构的内在对称性，我们引入近世代数中极具威力的工具——自同构算子 $\sigma$。

第一步：定义算子 $\sigma_m$

我们定义一个操作算子 $\sigma_m$：它的作用是将多项式中所有的单位根 $\zeta$，统一替换为 $\zeta^{g^m}$（即对每一项进行 $g^m$ 次方运算）。在原根的指数世界里，这种替换的几何意义是极其直观的：

$\sigma_m(\zeta^{g^x}) = (\zeta^{g^m})^{g^x} = \zeta^{g^m \cdot g^x} = \zeta^{g^{x+m}}$

也就是说，$\sigma_m$ 算子的本质，就是把多项式中的每一个根，在原根序列中往后精准地整体推移 $m$ 步！
在将 $\sigma_m$ 应用于乘积之前，我们必须确认一个极其重要的代数性质：先相乘再替换，与先各自替换再相乘，结果是绝对等价的。
对于任意单项式 $\zeta^A$ 和 $\zeta^B$：
先乘后替：$\sigma_m(\zeta^A \times \zeta^B) = \sigma_m(\zeta^{A+B}) = (\zeta^{g^m})^{A+B} = \zeta^{A \cdot g^m + B \cdot g^m}$
先替后乘：$\sigma_m(\zeta^A) \times \sigma_m(\zeta^B) = (\zeta^{g^m})^A \times (\zeta^{g^m})^B = \zeta^{A \cdot g^m} \times \zeta^{B \cdot g^m} = \zeta^{A \cdot g^m + B \cdot g^m}$
结果完全相等！对于加法显然也有 $\sigma_m(X + Y) = \sigma_m(X) + \sigma_m(Y)$。
因此，对于任意多项式，我们都有极其优雅的同态性质：

$\sigma_m(Q_k \times Q_{k+e}) = \sigma_m(Q_k) \times \sigma_m(Q_{k+e})$

第二步：应用 $\sigma_E$ 算子，证明根总是以完整的 $Q_v$ 出现（性质2）

现在，我们令步长 $m = E$，即对乘数施加 $\sigma_E$ 算子（全体后推 $E$ 步）：
因为 $Q_k$ 和 $Q_{k+e}$ 本身就是以 $E$ 为周期步长生成的循环组，所以往后推 $E$ 步，根刚好在它们各自的组内循环了一圈。即：

$\sigma_E(Q_k) = Q_k$，且 $\sigma_E(Q_{k+e}) = Q_{k+e}$。

代入同态性质中：

$\sigma_E(Q_k \times Q_{k+e}) = Q_k \times Q_{k+e}$

结论： 乘积展开式作为一个整体，在“根的指数全体后移 $E$ 步”的魔法下，保持绝对不变！这意味着，如果展开式中包含某个根 $\zeta^{g^i}$，那么将其后移 $E$ 步得到的 $\zeta^{g^{i+E}}$ 也必定在展开式中，且出现的次数完全相等。这意味着如果 $Q_v$ 中任意一个根 $\zeta^{g^i}$ 出现在乘法展开式中，那么整个 $Q_v$ 组里的所有根都会以相同的次数出现。这就证明了，乘积展开式必然可以表示为若干个 $Q_v$ 的整系数线性组合。

第三步：应用 $\sigma_e$ 算子，证明 $Q_v$ 完美合并为 $P_v$（性质3）

在确认了展开式是由一块块完整的 $Q_v$ 拼成之后，我们令步长 $m = e$，对乘数施加 $\sigma_e$ 算子（全体后推半步长 $e$）：
对于 $Q_k$：全体后推 $e$ 步，起点从 $g^k$ 变成了 $g^{k+e}$，恰好生成了 $Q_{k+e}$。即

$\sigma_e(Q_k) = Q_{k+e}$

对于 $Q_{k+e}$：后推 $e$ 步变成 $Q_{k+2e}$。因为 $2e = E$，根据前面的结论，跨越一个完整步长 $E$ 等于回到自身。即

$\sigma_e(Q_{k+e}) = Q_k$

代入同态性质中：

$\sigma_e(Q_k \times Q_{k+e}) = \sigma_e(Q_k) \times \sigma_e(Q_{k+e}) = Q_{k+e} \times Q_k$

根据乘法交换律，它等价于原来的 $Q_k \times Q_{k+e}$。结论： 乘积展开式在“全体后移 $e$ 步”的 $\sigma_e$ 魔法下，再次保持绝对不变！这意味着如果展开式中包含了 $A$ 个 $Q_v$ 组，那么将其后移 $e$ 步，它必然也等量地包含 $A$ 个 $Q_{v+e}$ 组。它们永远以 $A(Q_v + Q_{v+e})$ 的形式成对绑定。而根据我们的拆分定义，$Q_v + Q_{v+e}$ 恰好就是上一层已知的 $P_v$！至此，我们极其严谨地证明了：$Q_k \times Q_{k+e}$ 的结果不仅封闭在所有原根幂次集合内（不会出现 $1$），而且必定可以表示为上一层若干个 $P_v$ 的整系数线性组合。

「性质4」的证明：求和虚部抵消保证每次解出的都是实数

如果在求根公式里遇到了复数，那尺规作图就泡汤了。我们必须证明每个组 $P_k$ 的值（可位于任意层，只要含 $\ge 2$ 个根）都是实数。
$P_k$ 是实数，当且仅当组内的复数能够共轭配对。即如果 $\zeta^{g^i} \in P_k$，那么它的共轭 $\zeta^{-g^i}$ 也必须在 $P_k$ 中。
由「性质1」中推导出的(式 6.3)我们知道：

$-1 \equiv g^{(p-1)/2} \pmod p$

$\zeta^{-g^i} = \zeta^{g^{(p-1)/2}g^i} = \zeta^{g^{i + (p-1)/2}}$

因为任意的组 $P_k$ 只要根数 $f \ge 2$，组数 $e \le (p-1)/2$，于是 $(p-1)/2$ 一定是 $e$ 的正整数倍，可以表示为 $Ae$，于是：

$\zeta^{-g^i} = \zeta^{g^{i + Ae}}$

由于 $P_k$ 的步长为 $e$，这意味着如果 $\zeta^{g^i} \in P_k$ 那么 $\zeta^{g^{i+e}}$ 也在 $P_k$ 中，进而 $\zeta^{g^{i + Ae}}$ 即 $\zeta^{-g^i}$ 也一定在 $P_k$ 中。结论：互为共轭的两个根，永远被死死锁在同一个组里。 它们相加时虚部完全抵消，结果必为纯实数。