解法: ガウス=ヴァンツェルの定理:円分体による正多角形の作図可能性

$n = 2^k p_1^{e_1} \cdots p_m^{e_m}$($p_i$ は相異なる奇素数)と書く。オイラーのトーシェント関数は乗法的であるから、$k\ge1$ のとき $\varphi(n) = 2^{k-1}\prod_{i=1}^m p_i^{e_i - 1}(p_i - 1)$ となる($k=0$ のときは先頭の因子を除く)。$\varphi(n)$ が $2$ の冪であるためには、各因子 $p_i^{e_i-1}(p_i-1)$ 自体が $2$ の冪でなければならない。

$p_i$ は奇数であるから、項 $p_i^{e_i-1}$ が $2$ の冪となるのは $e_i-1=0$、すなわち $e_i=1$ のときに限られる:$n$ の各奇素因数はちょうど1回しか現れてはならない。残るのは $p_i - 1$ 自体が $2$ の冪であること、すなわち $p_i - 1 = 2^{r_i}$ とおけば $p_i = 2^{r_i}+1$ となることである。簡単な議論(もし $r_i$ が奇数の約数 $d>1$ を持てば、$2^{r_i}+1$ は真の約数 $2^{r_i/d}+1$ で割り切れてしまう)により、このような $p_i$ が素数になり得るのは $r_i$ 自体が $2$ の冪、$r_i=2^{s_i}$ であるときに限られ、$p_i = 2^{2^{s_i}}+1$——フェルマー素数——となることが示される。

両方の条件を合わせると、$n$ が作図可能であるのはまさに $n = 2^k p_1 \cdots p_m$($p_i$ は相異なるフェルマー素数)のときである(Gauss 1801, Art. 366)。これはまさに、第3番目のフェルマー素数である $17=2^{2^2}+1$ の背後にあるパターンであり、最初の2つである $n=3,5$ の背後にあるパターンでもある。