浅谈正多边形的尺规作图问题

xixihaha2021 · 2025-05-10 23:11:10 · 算法·理论

前言

云剪贴板

最近看了很多涉及正多边形的尺规作图问题的文章，但是目前洛谷没有关于该问题的记录，所以撰写此文。希望此文能帮助到包括我的更多人。

概述

查阅百度百科的 尺规作图 栏目，发现如下信息。

作正多边形

……

问题的解决：高斯，大学二年级时得出正十七边形的尺规作图法，并给出了可用尺规作图的正多边形的条件：尺规作图正多边形的边数目必须是2的非负整数次方和不同的费马数的积，解决了两千年来悬而未决的难题。

形式化地，正 n 边形可以用尺规作图构造，等价于

其中：

• k \ge 0;
• \forall\ x_1,x_2,\ p_{x_1} \not= p_{x_2};
• \forall\ x,\ \exists\ N \ge 0,\ p_x=2^{2^N}+1.

（以下简称命题。）

另外，目前只发现了 5 个 费马素数，即 3,5,17,257,65537。

证明过程

思路_{[1]}

由于正 n 边形的顶点在复平面的 n 次单位根上，故命题等价于对 \mathbb{Q}^{\text{alg}} 使用若干次二次扩域到达复平面上的点 e^{\frac{2\pi i}{n}}=\cos(\frac{2\pi}{n})+i\sin(\frac{2\pi}{n})。

显然若正 n 边形可作，则正 2n 边形也可作，故下文忽略 2^k 的因子。

引理 1：2^n+1 \in \mathbb{P}_+ 是 \exists\ m \ge 0,\ n=2^m 的充分条件。

事实上只需要满足 p=2^n+1 的质数为边数的正多边形就满足可作条件了，然而由引理 1 得，p 必须为费马素数。由此下文将费马素数当作 p=2^n+1 \in \mathbb{P}_+。

前置知识

n 次本原单位根

• \Phi_4(x)=x^2+1
• \Phi_6(x)=x^2-x+1

一般地，\Phi_n(x)=\frac{x^n-1}{\prod_{d|n,d \in [1,n]}\Phi_d(x)}。

引理 2：\Phi_n(x) 在 \mathbb{Q}(x) 中不可约。

分圆域

包含 \Phi_n(x) 所有根的最小扩域（也即分裂域）\mathbb{Q}(\xi_n) 定义为分圆域，其中 \xi_n 为任意一个 n 次本原单位根。不难证明这一点。

由欧拉函数 \phi(x) 的几何意义可知，\mathbb{Q}(\epsilon_n) 的扩张次数为 \phi(n)，也即分圆多项式 \Phi_n(x) 的次数为 \phi(n)。

充分性

首先对 n 分解，由引理 2 得，得到二次扩张链，只需保证每个需要的分圆多项式都不可约，即必须分解为素因子。

反证法：假设 n 的某个素因子不是费马素数，则该素因子的欧拉函数不是 2 的幂次，也即原分圆多项式的次数不为 2 的幂次，所以无法通过二次扩张得到，与可尺规作图矛盾，所以 n 的每个素因子必须是费马素数。

得证若一个正 n 边形可尺规作图，则（1）成立。

必要性

警告：上文中我尽可能少使用群论描述，但下文实在难以避免，特此说明。

注意到费马素数 p=2^{2^n}+1,n \ge 0 的分圆多项式为 \Phi_p(x)=\sum_{i=1}^{p-1} x^i，为 \phi(p)=2^{2^n} 阶。

根据伽罗瓦理论基本定理，当阶数为 a 的幂次时，在子群链中父群阶数为子群阶数的 a 倍，所以每次扩张的指数为 a。由于阶数为 2 的幂次，所以每次扩张的指数为 2。

因此分圆多项式可分解为若干个二次方程，显然可以构造为加、减、乘、除、二次根式的运算结果，所以可作。

若 n=p_1p_2p_3...p_m，则由于欧拉函数是积性函数，\phi(n)=\prod_{i=1}^m\phi(p_i)=\prod_{i=1}^m 2^{2^k_i}，仍为 2 的幂次，因此仍然可作。

得证若（1）成立，则一个正 n 边形可尺规作图。

引理证明

引理 1

反证法：假设 \exists\ m \ge 0,\ n=2^m 不成立。

设 a>1,a \not |\ 2,a \in \mathbb{P}_+,b \in \mathbb{N}_+,ab=n，则 2^n+1=2^{ab}+1=(2^b+1)\sum_{i=1}{a} (-1)^{i-1} \cdot 2^{b(a-i)}，与 2^n+1 \in \mathbb{P}_+ 矛盾，所以 \exists\ m \ge 0,\ n=2^m。

引理 2

发现我没在网上找到用艾森斯坦判别法证的，但是实际上可证，且并不困难。可以阅读 这篇文章，并将此问题留作习题。

作图过程

下面运用如上理论展示作正 n 边形的过程，以 n=17 为例。

必须说明的是，例如 n=15 的费马素数乘积形式的边数，可以在单位圆内作出正三角形和正五边形后，通过作差得到分母 15，再 n 等分线段得到正 15 边形的边长。如果边数含有因子 2^k，也可以 2^k 等分线段得到边长。

引理：n 等分线段在尺规作图中可作。

第 1 步：分组

首先你需要找到一个 n 的 原根。我们知道，\phi(n)=n-1=2^{2^n} 只有一个素因子 2，因此只需找到 g \in (1,n)，使 g^{\frac{n-1}{2}} \equiv 1(\bmod\ p)，例如 n=17 的最小原根为 3。

接下来以原根的幂次的奇偶性将所有单位根分成 2 组，构造 1 阶高斯周期。即 \eta_0=\sum_{i=0}^{\frac{n-3}{2}}\xi_n^{g^{2i}\bmod 17},\eta_1=\sum_{i=0}^{\frac{n-3}{2}}\xi_n^{g^{2i+1}\bmod 17}。

第 2 步：构造方程

由本原单位根的定义可知，n 次本原单位根之和为 -1，所以 \eta_0+\eta_1=-1。

由 \xi_n^k=\xi_n^{k \bmod 5}，展开计算 \eta_0 \cdot \eta_1，可得 \eta_0 \cdot \eta_1=-4。

由伟大韦达定理得，\eta_0 和 \eta_1 满足方程 x^2-(\eta_0+\eta_1)x+\eta_1 \cdot \eta_1=0，解得 \eta_0=\frac{-1+\sqrt{17}}{2},\eta_1=\frac{-1-\sqrt{17}}{2}。

第 3 步：递归

对 \eta_0 进行分组，使其的第奇数项之和为 \eta_{00}，第偶数项之和为 \eta_{01}。重复前 2 步得到 \eta_{00} 和 \eta_{01} 的值。同理可得 \eta_{000} 和 \eta_{001} 的值。

递归求解，直到解出 \xi_n 的值。

第 4 步：作图

最后得到的结果就是实部，完全由加、减、乘、除和二次根号组成，作图是简单的。

引理证明

甚至在中考的考纲里（应该），所以不证了。但是放个视频。

结语

阅读完本文，你理论上就可以完成正 n 边形的作图了。最后，有勘误可以私信我，会不定期统一修正。另外，本文的勘误会更快地在云剪贴板同步。

附录

[1]：本文的部分内容需要 这篇文章 的基础，推荐阅读本文前先阅读它。