「tsujimotterの29予想」の初等的証明 - tsujimotterのノートブック

今日のテーマはこちらです：

定理1（tsujimotterの29予想）

$p$ を任意の素数とする。このとき、次が成り立つ：

$X^4 + Y^4 + Z^4 \equiv 0 \pmod{p}$ が $(X, Y, Z) \not\equiv (0, 0, 0) \pmod{p}$ なる整数解 $X, Y, Z$ を持たない $\Longleftrightarrow \; p = 5, \; 29$

合同式に解がないのはなぜか $\bmod{5}$ と $\bmod{29}$ のときだけであるという不思議な現象についての予想です。

この予想に関する経緯を少しだけ説明します。

元々、Wikipedia で（ほぼ）上記の主張が証明抜きで述べられているのを見つけたというのがはじまりです。この主張に興味をもって調べてみると、「数の事典」という本にも同様の記述が載っていて、そこには「3つの4乗数の和は，5でも29でもわりきれない（ただし， $5^4+5^4+5^4$ と $29^4+29^4+29^4$ の場合を除く）．[Euler]」と書いてあります。Eulerの名前がありますね。殊更に $5, 29$ と書かれていますが、他の数ではこのような現象は起きないのでしょうか。しかしながら、どの本やウェブサイトを探してみても証明は書いてありません。

この問題が気になった私は、一番最初に述べた問題を「tsujimotterの29予想」と名付け、数値的に確認した上でブログにまとめました：
tsujimotter.hatenablog.com

その後、nishimuraさんという方により、Twitter経由で「代数曲線のハッセ境界を用いた解法」を教えていただき、解決に至りました。
tsujimotter.hatenablog.com

しかしながら、上記の解法は「初等的な証明」とは言えず、オイラーの時代に実現出来たものとは思えません。

今回、Twitter経由で「原則として（ @boxwhite1 ）さん」より「初等的証明」を発見したとのご連絡いただきました。発見された証明は、まさにオイラーやガウスの時代にあった道具立てを用いた証明となっています。（実際、ガウスによる定理を用います）

@boxwhite1 さんより許可いただいて、今回の記事でこの証明を紹介したいと思います。興味深い証明を教えていただきましてありがとうございます。ここ数年の胸のつっかえが取れた気分で、とても嬉しいです。

念の為の補足なのですが、「初等的証明」だからといって「簡単な証明」というわけではありません。今回の証明は「4次剰余」に関するガウスの考察の一部分を利用するのですが、これがとても複雑です。かなり長いものになりますが、とても面白いのでよろしければお付き合いください。「ガウスすごいな」と感じると思います。

なお、@boxwhite1 さんが最初に思いついた証明は、実はもっと複雑で長かったのですが、私にご連絡いただいてから改めてより簡潔な証明を思いついたそうで、その方針に従って書き直したものとなります。その際のやりとりは、こちらのツイートのリプライの中で行われています。

tsujimotter の定理（素数を法とした合同式x^4+y^4+z^4=0にはほとんどの場合整数解が存在する）の初等的な証明を得た。（今日の進捗）
— 原則として (@boxwhite1) 2020年9月30日

目次：

問題の言い換え

p = 8n+1, 8n+5型の共通の事項

p = 8n+1型の場合

p = 8n+5型の場合

p = 4n+3型の場合

おわりに

参考文献

問題の言い換え

証明に行く前に、問題を少し言い換えたいと思います。

上では、 $(X, Y, Z) \not\equiv (0, 0, 0) \pmod{p}$ であるような解について考えました。すなわち、 $X, Y, Z$ が同時に $0$ に合同ではないような解です。

今回はより強く「 $X, Y, Z$ のいずれも $0$ に合同ではない」という条件の解を考察したいと思います。すなわち、定理1を示す代わりに、次の主張を示すことにしたいと思います。

定理2（tsujimotterの29予想の言い換え）

$p$ を任意の素数とする。このとき、次が成り立つ：

$X^4 + Y^4 + Z^4 \equiv 0 \pmod{p}$ が $XYZ \not\equiv 0 \pmod{p}$ なる整数解 $X, Y, Z$ を持たない $\Longleftrightarrow \; p = 2, \; 5, \; 17, \; 29, \; 41$

$XYZ \not\equiv 0 \pmod{p}$ なる解 $(X, Y, Z)$ は、当然 $(X, Y, Z) \not\equiv (0, 0, 0) \pmod{p}$ である解となっています。したがって定理2の条件は、定理1のものより厳しい条件であると言えます。

それゆえに少し例外の素数が増えますが、気にしないでおきましょう。実際、定理2で新たに発生した例外ケース（ $p = 2, \; 17, \; 41$ のとき）のときは、 $X, Y, Z$ のいずれかに $0$ を入れるのを許容することで、 $(X, Y, Z) \equiv (0, 0, 0) \pmod{p}$ なる解を作ることができます：　

$1^4 + 0^4 + 1^4 \equiv 0 \pmod{2}$ 　　（ $(X, Y, Z) = (1, 0, 1)$ とした）

$2^4 + 0^4 + 1^4 \equiv 0 \pmod{17}$ 　　（ $(X, Y, Z) = (2, 0, 1)$ とした）

$3^4 + 0^4 + 1^4 \equiv 0 \pmod{41}$ 　　（ $(X, Y, Z) = (3, 0, 1)$ とした）

よって $p = 2, 17, 41$ については、定理1の条件（ $(X, Y, Z) \equiv (0, 0, 0)$ なる解を持たない）を満たす素数ではないと言えます。

したがって

定理2 $\Longrightarrow$ 定理1（tsujimotterの29予想）

が成り立つことが分かりました。

このような考察の下、今回の記事では定理2の証明を目指したいと思います。

定理2の形をさらに言い換えるべく、下記の同値性を示したいと思います。

任意の素数 $p$ に対して、以下が成り立つ：

$X^4 + Y^4 + Z^4 \equiv 0 \pmod{p}$ が $XYZ \not\equiv 0 \pmod{p}$ なる整数解 $X, Y, Z$ を持つ
$\Longleftrightarrow \;\;$ $x^4 + y^4 + 1 \equiv 0 \pmod{p}$ が $xy \not\equiv 0 \pmod{p}$ なる整数解 $x, y$ を持つ

（上を仮定して下を導く）
$X^4 + Y^4 + Z^4 \equiv 0 \pmod{p}, \;\;XYZ \not\equiv 0 \pmod{p}$ なる整数解 $X, Y, Z$ があると仮定する。

$\bmod{p}$ での $Z$ の逆元を $W$ とすると $ZW \equiv 1 \pmod{p}$ である。この $W$ を両辺にかけると

$(XW)^4 + (YW)^4 + 1 \equiv 0 \pmod{p}$

となり、 $x = XW, \; y = YW$ として下の整数解が得られた。

（下を仮定して上を導く）
$x^4 + y^4 + 1^4 \equiv 0 \pmod{p}, \;\;xy \not\equiv 0 \pmod{p}$ なる整数解 $x, y$ があると仮定する。 $X = x, \; Y = y, \; Z = 1$ とすれば、上の整数解が得られる。

よって問題は「合同式 $x^4 + y^4 + 1 \equiv 0 \pmod{p}, \;\; xy \not\equiv 0 \pmod{p}$ の $\bmod{p}$ における解の個数」に帰着されました。

このような解の個数を $N_p$ とします。有限体の言葉を使って書くと

$N_p = \# \{ (x, y) \in \mathbb{F}_p^2 \mid x^4 + y^4 + 1 = 0, \;\; xy \neq 0 \}$

ということですね。

証明は次節以降でまとめますが、かなり長いです。

まず、 $p = 4n+1$ 型と $p = 4n+3$ 型で場合分けが発生します。さらに $p = 4n+1$ 型は、 $p = 8n + 1$ 型と $p = 8n + 5$ 型に分かれます。この違いは些細な違いなので、基本的に $p = 8n + 1$ の方を真面目に説明して、 $p = 8n + 5$ の方は違う部分だけ言及する形にしたいと思います。

なお、 $p = 8n + 1$ 型、 $p = 8n + 5$ 型については、参考文献に記載した「ガウスの数論論文集（ちくま学芸文庫）」における「４次剰余の理論　第１論文」を雛形にしています。

目標とする定理はこちらです。

定理3

(1) $p$ を $4$ で割って $1$ あまる素数とし、 $p$ を奇数 $a$ および偶数 $b$ によって $p = a^2 + b^2$ と表す。ここで、 $a$ は $a\equiv 1 \pmod{4}$ となるように正負を定める。

このとき、次が成り立つ：

(i) $p = 8n+1$ のとき：

$\displaystyle N_p = p - 6a - 11$

(ii) $p = 8n+5$ のとき：

$\displaystyle N_p = p - 6a + 1$

(2) また、 $p$ を $4$ で割って $3$ あまる素数とすると、次が成り立つ：

$\displaystyle N_p = p + 1$

定理3は $x^4 + y^4 + 1 \equiv 0\pmod{p}$ の解の個数 $N_p$ を完全に特定することができるすごい定理です。

この定理を仮定すれば、もちろん定理2（tsujimotterの29予想の言い換え）を示すことができます。

（定理3 $\; \Longrightarrow \;$ 定理2の証明）
$p \equiv 1 \pmod{4}$ とする。定理3の (1)-(i), (ii) と $p = a^2 + b^2 > a^2 > 0$ より

$\displaystyle N_p \geq p - 6a - 11 > (\sqrt{p})^2 - 6\sqrt{p} - 11$

が得られる。 $p \equiv 3 \pmod{4}$ のときも定理3の (2) より、 $N_p > (\sqrt{p})^2 - 6\sqrt{p} - 11$ は成り立つ。

ので、グラフの観察により $\sqrt{p} \geq 8$ のとき（すなわち、 $p \geq 64$ のとき） $N_p$ が1以上になるとわかります。

f:id:tsujimotter:20201004185913p:plain:w440

また、 $p < 64$ のとき $p = 2, \; 5, \; 17, \; 29, \; 41$ を除いて解を持つことが（数値計算により）確認できます。

したがって、定理2（tsujimotterの29予想の言い換え）の主張が示されました。

（定理3 $\; \Longrightarrow \;$ 定理2の証明終わり）

実際、数値計算により、たしかに解の個数（3列目）と定理3による評価（5列目〜7列目）が一致していることが確認できます！

ぴったり個数を決定できるなんて、すごいですね！

$p$	modulo	$\#$	$a^2 + b^2$	$p - 6a - 11$	$p - 6a + 1$	$p + 1$
$3$	$\equiv 3 \pmod{4}$	$4$	-	-	-	$4$
$5$	$\equiv 5 \pmod{8}$	$0$	$1^2 + 2^2$	-	$0$	-
$7$	$\equiv 3 \pmod{4}$	$8$	-	-	-	$8$
$11$	$\equiv 3 \pmod{4}$	$12$	-	-	-	$12$
$13$	$\equiv 5 \pmod{8}$	$32$	$(-3)^2 + 2^2$	-	$32$	-
$17$	$\equiv 1 \pmod{8}$	$0$	$1^2 + 4^2$	$0$	-	-
$19$	$\equiv 3 \pmod{4}$	$20$	-	-	-	$20$
$23$	$\equiv 3 \pmod{4}$	$24$	-	-	-	$24$
$29$	$\equiv 5 \pmod{8}$	$0$	$5^2 + 2^2$	-	$0$	-
$31$	$\equiv 3 \pmod{4}$	$32$	-	-	-	$32$
$37$	$\equiv 5 \pmod{8}$	$32$	$1^2 + 6^2$	-	$32$	-
$41$	$\equiv 1 \pmod{8}$	$0$	$5^2 + 4^2$	$0$	-	-
$43$	$\equiv 3 \pmod{4}$	$44$	-	-	-	$44$
$47$	$\equiv 3 \pmod{4}$	$48$	-	-	-	$48$
$53$	$\equiv 5 \pmod{8}$	$96$	$(-7)^2 + 2^2$	-	$96$	-
$59$	$\equiv 3 \pmod{4}$	$60$	-	-	-	$60$
$61$	$\equiv 5 \pmod{8}$	$32$	$5^2 + 6^2$	-	$32$	-
$67$	$\equiv 3 \pmod{4}$	$68$	-	-	-	$68$
$71$	$\equiv 3 \pmod{4}$	$72$	-	-	-	$72$
$73$	$\equiv 1 \pmod{8}$	$80$	$(-3)^2 + 8^2$	$80$	-	-
$79$	$\equiv 3 \pmod{4}$	$80$	-	-	-	$80$
$83$	$\equiv 3 \pmod{4}$	$84$	-	-	-	$84$
$89$	$\equiv 1 \pmod{8}$	$48$	$5^2 + 8^2$	$48$	-	-
$97$	$\equiv 1 \pmod{8}$	$32$	$9^2 + 4^2$	$32$	-	-

p = 8n+1, 8n+5型の共通の事項

定理3の(1)-(i), (ii)を証明するために、 $p = 8n+1, 8n+5$ 型に共通する事項についてまとめておきましょう。

まず、 $\bmod{p}$ の原始根を $g$ とすると、 $\bmod{p}$ の 0 でない元 $1, 2, \ldots, p-1$ は、順番を入れ替えて

$1, g, g^2, g^3, \ldots, g^{p-2}$

と表せます（正確には「上記のどれか１つに合同」の意味）。フェルマーの小定理により $g^{p-1} \equiv 1 \pmod{p}$ で循環することに注意します。また、以下ずっと原始根 $g$ は同じものを固定します。

どちらのケースの $p$ も $4$ で割って $1$ あまるので、 $p-1$ は $4$ で割り切れます。よって $p-1$ 個の数を、以下の4つの剰余類に分類します：

$A = \{ 1, g^4, g^8, \ldots, g^{p-5} \}$
$B = \{g, g^5, g^9, \ldots, g^{p-4}\}$
$C = \{ g^2, g^6, g^{10}, \ldots, g^{p-3}\}$
$D = \{ g^3, g^7, g^{11}, \ldots, g^{p-2}\}$

$A$ に属する数は、すべて $\bmod{p}$ で $X^4$ の形をした数であることに注意すると、今回の問題に関係しそうだということがわかります。

$B$ に属する任意の元 $\beta$ と $C$ に属する任意の元 $\gamma$ の積 $\beta \gamma$ は、ある $D$ の元 $\delta$ が存在して $\beta \gamma = \delta$ と表せます。したがって、剰余類の間の積 $BC = D$ がwell-definedに定まります。

こんな風に演算を定めると、 $\{A, B, C, D\}$ は剰余群をなしますが、その群構造は $\mathbb{Z}/4\mathbb{Z}$ と同型になることに注意します。すなわち、次のような演算が成り立ちます：

$\times$	$A$	$B$	$C$	$D$
$A$	$A$	$B$	$C$	$D$
$B$	$B$	$C$	$D$	$A$
$C$	$C$	$D$	$A$	$B$
$D$	$D$	$A$	$B$	$C$

なお、 $\alpha \in A, \; \beta \in B, \; \gamma \in C, \; \delta \in D$ に対して

$\alpha^{-1} \in A, \;\; \beta^{-1} \in D, \;\; \gamma^{-1} \in C, \;\; \delta^{-1} \in B$

であることにも注意します。

以下の議論を簡単にするための記法をいくつか導入したいと思います。以下、 $\alpha, \alpha', \alpha''$ などの記号を使ったら $A$ の元、 $\beta, \beta', \beta''$ を $B$ の元、 $\gamma, \gamma', \gamma'''$ を $C$ の元、 $\delta, \delta', \delta'''$ を $D$ の元とします。

また、 $(\alpha + \alpha' + 1 \equiv 0)$ のように書いたら

$(\alpha + \alpha' + 1 \equiv 0) := \# \left \{ (\alpha, \alpha') \in A \times A \mid \alpha + \alpha' + 1 \equiv 0 \pmod{p} \right \}$

を表すことにします。同様に

$(\alpha + \beta' + 1 \equiv 0) := \# \left \{ (\alpha, \beta') \in A \times B \mid \alpha + \beta' + 1 \equiv 0 \pmod{p} \right \}$

という感じですね。「合同式の解の個数」をカッコの記号によって省略して表すということですね。

また、合同式は基本的に法 $p$ のものを考えるので、 $\bmod{p}$ については省略してもよいものとします。

ここで $\alpha, \alpha' \in A$ は $\alpha \equiv x^4, \;\; \alpha' \equiv y^4$ と表せるので、元々の問題は $(\alpha + \alpha' + 1 \equiv 0 \pmod{p})$ の個数の計算に帰着できると分かりますね。

実際、 $\alpha \equiv x^4, \;\; \alpha' \equiv y^4$ と表せる $x, y$ の組は、1組の $(\alpha, \alpha')$ に対して $4\times 4 = 16$ 組ありますから、 $N_p$ 自体はちょうど $16$ 倍になることに注意します。

$\begin{align} N_p &:= \# \{ (x, y) \in (\mathbb{F}_p^\times)^2 \mid x^4 + y^4 + 1 \equiv 0 \pmod{p}\} \\ &= 16(\alpha + \alpha' + 1 \equiv 0) \end{align}$

次に、 $\alpha + 1$ が再び $A$ に属するような $\alpha \in A$ の個数を $(00)$ とおきます。

同様に $\alpha + 1$ が $B$ に属するような $\alpha \in A$ の個数を $(01)$ 、 $\alpha + 1$ が $C$ に属するような $\alpha \in A$ の個数を $(02)$ 、 $\alpha + 1$ が $D$ に属するような $\alpha \in A$ の個数を $(03)$ とおきます。

また

$1 + \beta$ について同じように $(10), (11), (12), (13)$
$1 + \gamma$ について同じように $(20), (21), (22), (23)$
$1 + \delta$ について同じように $(30), (31), (32), (33)$

を定義します。

これで共通の記号の準備は終わります。

p = 8n+1型の場合

ここから場合分けして定理3を証明します。 $p = 8n+1$ のとき

$\displaystyle \frac{p-1}{4} = 2n$

なので、 $\frac{p-1}{4}$ が偶数であることに注意します。

$g$ は原始根であることと、フェルマーの小定理より $g^{\frac{p-1}{2}} \equiv -1$ です。ここから

$(g^{\frac{p-1}{8}})^4 \equiv g^{\frac{p-1}{2}} \equiv -1 \pmod{p}$

であり、結果として $-1$ が $A$ に属することがわかります。

このことを使うと、たとえば $(01) = (\alpha + \beta' + 1 \equiv 0)$ であることがわかります。 $(01)$ は

$1 + \alpha \equiv \beta'$

の解の個数ですが、右辺を左辺に写すと

$1 + \alpha + (-1)\beta' \equiv 0$

となります。 $(-1) \in A$ なので、演算表より $AB = B$ であるから $\beta'' = (-1)\beta$ とおくと

$1 + \alpha + \beta'' \equiv 0$

となります。よって、 $(01) = (\alpha + \beta' + 1 \equiv 0)$ が帰結されます。

結局、同様の議論により以下が言えます：

$\begin{cases} (00) = (\alpha + \alpha' + 1 \equiv 0) \\ (01) = (\alpha + \beta' + 1 \equiv 0) \\ (02) = (\alpha + \gamma' + 1 \equiv 0) \\ (03) = (\alpha + \delta' + 1 \equiv 0) \end{cases}$

$\begin{cases} (10) = (\beta + \alpha' + 1 \equiv 0) \\ (11) = (\beta + \beta' + 1 \equiv 0) \\ (12) = (\beta + \gamma' + 1 \equiv 0) \\ (13) = (\beta + \delta' + 1 \equiv 0) \end{cases}$

$\begin{cases} (20) = (\gamma + \alpha' + 1 \equiv 0) \\ (21) = (\gamma + \beta' + 1 \equiv 0) \\ (22) = (\gamma + \gamma' + 1 \equiv 0) \\ (23) = (\gamma + \delta' + 1 \equiv 0) \end{cases}$

$\begin{cases} (30) = (\delta + \alpha' + 1 \equiv 0) \\ (31) = (\delta + \beta' + 1 \equiv 0) \\ (32) = (\delta + \gamma' + 1 \equiv 0) \\ (33) = (\delta + \delta' + 1 \equiv 0) \end{cases}$

ここで、右辺側の記号の対称性から

$(01) = (10), \;\; (02) = (20), \;\; (03) = (30)$

$(12) = (21), \;\; (13) = (31), \;\; (23) = (32)$

が分かります。

実は、もう少しだけ対称性が観察できます。たとえば、合同式

$\alpha + \beta + 1 \equiv 0 \pmod{p}$

の与えられた解に対して、 $\beta \delta \equiv 1$ となる $\delta$ をとります（ $\bmod{p}$ における $\beta$ の逆元を $\delta$ とするわけですね）。

このとき、上記の合同式に対して $\delta$ をかけると

$\delta\alpha + 1 + \delta \equiv 0 \pmod{p}$

が得られますが、 $DA = D$ なので $\delta\alpha = \delta' \in D$ とおきます。すると

$\delta' + 1 + \delta \equiv 0 \pmod{p}$

が得られます。この操作は両辺に $\beta$ をかけることで逆転させることができます。

したがって、

$(01) = (\alpha + \beta + 1 \equiv 0) = (\delta + \delta' + 1 \equiv 0) = (33)$

が帰結されます。

同様の議論によって

$(02) = (22), \;\; (03) = (11), \;\; (12) = (13) = (23)$

が得られます。

以上から、 $16$ 個の変数 $(00)$ 〜 $(33)$ に対して $11$ 個の関係式があるので、 $16 - 11 = 5$ 個の変数 $h, i, k, l, m$ により表せることができます：

$\begin{pmatrix} (00) & (01) & (02) & (03) \\ (10) & (11) & (12) & (13) \\ (20) & (21) & (22) & (23) \\ (30) & (31) & (32) & (33) \end{pmatrix} = \begin{pmatrix} h & i & k & l \\ i & l & m & m \\ k & m & k & m \\ l & m & m & i \end{pmatrix}$

ここから上の表を観察しながら、さらに関係式を作って変数を絞っていきます。

一番上の行の $(00) + (01) + (02) + (03)$ について考察します。これらは定義より $1 + \alpha$ が $A, B, C, D$ のいずれの元であるかに応じた個数を表す変数でした。 $-1 \in A$ を除く $\alpha \in A$ については、 $1 + \alpha$ が $A, B, C, D$ のいずれかに入ります。一方で、 $-1$ だけは、 $1 + (-1) \equiv 0$ となり、これだけは $A, B, C, D$ のいずれの元でもありません。

$A$ に属する元の個数は $\frac{p-1}{4} = 2n$ 個なので、

$(00) + (01) + (02) + (03) = h + i + k + l = 2n - 1$

が成り立ちます。

同様に $1 + \beta, \; 1 + \gamma, \; 1 + \delta$ が $A, B, C, D$ のいずれかの元に入ることを考慮すると

$(10) + (11) + (12) + (13) = i + l + 2m = 2n$

$(20) + (21) + (22) + (23) = 2k + 2m = 2n$

$(30) + (31) + (32) + (33) = l + 2m + i = 2n$

も成り立ちます。（ $B, C, D$ には $(-1)$ は入らないので、 $A$ のときのような例外は発生しません。）

さらに、 $1 + \alpha + \beta + \gamma \equiv 0$ という合同式を考えて、その解の個数 $S$ を2通りの方法で考えます。

上の合同式を $(1 + \alpha) + \beta + \gamma \equiv 0$ のように分けます。これは $1+\alpha$ が $A, B, C, D$ のいずれに入るかによって、4通りに場合分けされます。

$1 + \alpha \in A$ のとき、 $1 + \alpha = \alpha'$ とおくと

$\alpha' + \beta + \gamma \equiv 0$

です。両辺に $\alpha' \alpha'' \equiv 1$ なる元 $\alpha'' \in A$ をかけると、

$1 + \beta\alpha'' + \gamma\alpha'' \equiv 0$

となります。 $BA = B, \; CA = C$ より $\beta\alpha'' \equiv \beta' \in B, \;\; \gamma\alpha'' \equiv \gamma' \in C$ とおくと、

$1 + \beta' + \gamma' \equiv 0$

と表すことができます。

結局、 $1 + \alpha \in A$ であるような解の個数は

$(00) \times (1 + \beta + \gamma \equiv 0)$

ということになりますね。

同様の考察を $1 + \alpha \in B, \;\; 1 + \alpha \in C, \;\; 1 + \alpha \in D$ について行うと、解の個数 $S$ が次のように得られます：

$\begin{align} S =& (00) \times (1 + \beta + \gamma \equiv 0) \\ &+ (01) \times (1 + \alpha + \beta \equiv 0) \\ &+ (02) \times (1 + \delta + \alpha \equiv 0) \\ &+ (03) \times (1 + \gamma + \delta \equiv 0) \end{align}$

変数 $h, i, k, l, m$ を用いて表すと、

$\begin{align} S &= (00) \times (12) + (01) \times (01) + (02) \times (30) + (03) \times (23) \\ &= hm + i^2 + kl + lm \end{align}$

となります。

同様に $(1 + \beta) + \alpha + \gamma \equiv 0$ と組み替えることで、解の個数 $S$ を $1 + \beta$ に対して計算すると

$\begin{align} S = ik + lm + km + m^2 \end{align}$

が得られます。（なお、 $1 + \gamma$ に対して計算しても同じ式が得られるので、計算の必要はありません。）

結局、 $S$ についての2通りの計算により関係式

$\begin{align} hm + i^2 + kl = ik + km + m^2 \end{align}$

が得られました（両辺に $lm$ があったのであらかじめ消去しています）。

以上の議論によって得られた関係式を全てまとめると、次のようになります：

$\begin{cases} h + i + k + l = 2n - 1 \\ i + l + 2m = 2n \\ 2k + 2m = 2n \\ hm + i^2 + kl = ik + km + m^2 \end{cases}$

最後の仕上げです。上記の関係式を使って、 $p = 8n+1$ に関する式を作りましょう。

1番目の式から2番目の式を引きことにより $h = 2m - k - 1$ が得られますが、これを4番目の式に代入して $h$ を消去します。すると

$(2m - k - 1)m + i^2 + kl = ik + km + m^2$

となり、整理すると

$(k - m)^2 + (i^2 + kl - ik - k^2) - m = 0$

となります。

ここで、先ほどの2番目の式から3番目の式を引くと $2k = l + i$ が得られますので、 $i^2 + kl - ik - k^2$ を4倍した上で $k$ を消去します：

$\require{cancel} \begin{align} 4(i^2 + kl - ik - k^2) &= 4i^2 + 2(l + i)l - 2i(l+i) - (l+i)^2 \\ &= 4i^2 + 2l^2 + \cancel{2li} - \cancel{2li} - 2i^2 - l^2 - 2li - i^2 \\ &= l^2 - 2li + i^2 \\ &= (l + i)^2 \end{align}$

ゆえに

$4m = 4(k - m)^2 + (l - i)^2$

が得られました。

ここで、恒等式 $4m = 2(k+m) - 2(k-m) = 2n - 2(k-m)$ を使うと

$2n = 4(k - m)^2 + 2(k-m) + (l - i)^2$

となりますが、これを4倍して両辺に1を足すと

$\begin{align} 8n+1 &= 16(k - m)^2 + 8(k-m) + 1 + 4(l - i)^2\\ &= \left[ 4(k-m) + 1 \right]^2+ 4(l - i)^2 \end{align}$

が導かれます。 $p = 8n+1$ より

$p = 8n+1 = \left[ 4(k-m) + 1 \right]^2+ 4(l - i)^2$

となりますが、

$a = 4(k-m) + 1$
$b = 2(l - i)$

とおけば、これは $p = 8n + 1$ を平方数の和 $a^2 + b^2$ で表す式に他なりません！

フェルマーの2平方和定理より、 $p$ を $p = a^2 + b^2$ と表す方法は、 $a, b$ の符号と入れ替えを除いては一意的です。

上の式は、 $a$ は4M+1型の奇数で $b$ は偶数なので、 $a$ は符号も含めて一意的に定めることができます。

$b$ については、現時点では符号が定まりませんが、これについては別の議論で一意的に定めることができます。今回の用途には不要なので、省略します。

したがって、 $p$ および $a$ を用いて $(00)$ を完全に決定することができます。

$\begin{align} 16(00) &= 16h & \\ &= 16(2m - k - 1) & (\because h = 2m-k-1) \\ &= 32m - 16k - 1 & \\ &= 8n + (24m - 24k) - 1 & (\because 2n - (2k+2m) \; \text{を4回足す}) \\ &= 8n - 6\left[ 4(k-m) + 1 \right] + 6 - 16 & \\ &= 8n - 6a - 10 & (\because a = 4(k-m)+1) \\ &= (8n+1) - 6a - 11 & \\ &= p - 6a - 11 & (\because p = 8n+1) \end{align}$

ゆえに

$\displaystyle (00) = \frac{p - 6a - 11}{16}$

が得られました。

同様に計算すると、 $p, a, b$ を用いて $(00)$ から $(33)$ までの16個の変数を確定させることができます。計算は省略します。

$N_p$ は $(00)$ のちょうど16倍なので定理3の (1)-(i) が示されました。

p = 8n+5型の場合

$p = 8n+5$ の場合も、前節とほぼ同様に進んでいきますが、色々細かい違いが発生します。すべての証明を記述すると大変なので、同様の議論や計算をする箇所を思い切り省略していくことにします。

前節との大きな違いとして $-1 \in C$ であることが挙げられます。（ $p = 8n+1$ のときには $-1 \in A$ でした）

$p\equiv 1 \pmod{4}$ より、 $-1$ は $p$ の平方剰余だから、 $-1 \in A$ または $-1 \in C$ です。以下で、 $-1 \not\in A$ であることを示します。

まず

$(g^{\frac{p-1}{4}})^2 = g^{\frac{p-1}{2}} \equiv -1 \pmod{p}$

なので、 $X = (\pm 1) g^{\frac{p-1}{4}}$ は $X^2 \equiv -1 \pmod{p}$ の相異なる2解となります。

$\pm 1$ は $p$ の平方剰余なので、 $X^4 \equiv -1 \pmod{p}$ の解が存在するかどうかは $g^{\frac{p-1}{4}}$ 自身が平方剰余かどうか調べれば良い。 $\frac{p-1}{4} = 2n+1$ より

$g^{\frac{p-1}{4}} = g^{2n+1}$

となり、指数部分は奇数。したがって、 $(\pm 1) g^{\frac{p-1}{4}}$ 自身は平方剰余ではありません。

以上により、 $X^4 \equiv -1 \pmod{p}$ の解が存在しないことがわかり、 $-1 \not\in A$ であることが結論づけられます。

この事実により、 $(00)$ 〜 $(33)$ と $(\alpha + \alpha' + 1 \equiv 0)$ 〜 $(\alpha + \delta' + 1 \equiv 0)$ との関係が変わってきます。結論から言うと、以下のようになります：

$\begin{cases} (00) = (\alpha + \gamma' + 1 \equiv 0) \\ (01) = (\alpha + \delta' + 1 \equiv 0) \\ (02) = (\alpha + \alpha' + 1 \equiv 0) \\ (03) = (\alpha + \beta' + 1 \equiv 0) \end{cases}$

$\begin{cases} (10) = (\beta + \gamma' + 1 \equiv 0) \\ (11) = (\beta + \delta' + 1 \equiv 0) \\ (12) = (\beta + \alpha' + 1 \equiv 0) \\ (13) = (\beta + \beta' + 1 \equiv 0) \end{cases}$

$\begin{cases} (20) = (\gamma + \delta' + 1 \equiv 0) \\ (21) = (\gamma + \delta' + 1 \equiv 0) \\ (22) = (\gamma + \alpha' + 1 \equiv 0) \\ (23) = (\gamma + \beta' + 1 \equiv 0) \end{cases}$

$\begin{cases} (30) = (\delta + \gamma' + 1 \equiv 0) \\ (31) = (\delta + \delta' + 1 \equiv 0) \\ (32) = (\delta + \alpha' + 1 \equiv 0) \\ (33) = (\delta + \beta' + 1 \equiv 0) \end{cases}$

したがって、私たちが求めるべきは $(02)$ であることがわかります。

関係式も、これらの変更に伴って少しずつ変わっていきます。

$(00) = (22), \; (01) = (32), \; (03) = (12),$

$(10) = (23), \; (11) = (33), \; (21) = (30)$

また、前節と同様に $(00)$ の右辺に $\gamma$ の逆元をかけるなどして、以下の関係式が得られます：

$(00) = (22), \; (01) = (13), \; (03) = (31), \; (10) = (11) = (21)$

以上から、 $(00)$ 〜 $(33)$ はやはり5つの変数 $h, i, k, l, m$ を用いて次のように表せることがわかります：

$\begin{pmatrix} (00) & (01) & (02) & (03) \\ (10) & (11) & (12) & (13) \\ (20) & (21) & (22) & (23) \\ (30) & (31) & (32) & (33) \end{pmatrix} = \begin{pmatrix} h & i & k & l \\ m & m & l & i \\ h & m & h & m \\ m & l & i & m \end{pmatrix}$

また、 $p = 8n+5$ より $(p-1)/4 = 2n+1$ となりますので、 $A, B, C, D$ の要素数はどれも $2n+1$ です。よって、 $-1 \in C$ であることを考慮しつつ、 $1 + \alpha$ が $A, B, C, D$ のいずれかに入るパターンを考えると、次の関係式が得られます。

$(00) + (01) + (02) + (03) = h + i + k + l = 2n + 1$

$(10) + (11) + (12) + (13) = 2m + l + i = 2n+1$

$(20) + (21) + (22) + (23) = 2h + 2m = 2n$

$(30) + (31) + (32) + (33) = 2m + l + i = 2n+1$

ここで、前節と同様に $1 + \alpha + \beta + \gamma \equiv 0$ の解の個数を計算すると

$1 + \alpha$ の行き先に着目した場合： $hm + il + ik + lm$ 個
$1 + \beta$ の行き先に着目した場合： $hm + m^2 + hl + im$ 個

となり、やはり関係式

$il + ik + lm = m^2 + hl + im$

が得られる。

結局、関係式群

$\begin{cases} h + i + k + l = 2n + 1 \\ 2m + i + l = 2n+1 \\ 2h + 2m = 2n \\ m^2 + hl + hi - il - ik - lm = 0 \end{cases}$

が得られたことになります。

ここで、いろいろ計算すると最終的に

$8n+5 = [4(h-m) + 1]^2 + 4(i-l)^2$

が得られます。

$a = 4(h-m) + 1$
$b = 2(i - l)$

とおくと、 $p = 8n+5$ より、 $p$ は2平方和 $a^2 + b^2$ で表されたことになります。前節と同様 $a$ は一意的に定まるので、 $p, a$ を用いて $16(02)$ を表すと

$16(02) = 16k = p - 6a + 1$

となります。すなわち、

$\displaystyle (02) = \frac{p - 6a + 1}{16}$

が得られました。

$N_p$ は $(02)$ のちょうど16倍なので定理3の (1)-(ii) も示されました。

p = 4n+3型の場合

$p = 4n+3$ 型の素数に対しては、証明の仕方ががらっと変わります。というのも、 $p = 4n+3$ の場合は、4乗剰余を用いることなく、平方剰余で議論が済んでしまうからです。

$\bmod{p}$ の原始根を $g$ として、 $(g^i)^4$ を順に並べます。

$\displaystyle 1, g^4, g^8, \ldots, g^{4n}, g^{4n+4}, g^{4n+8}, \ldots, g^{8n}$

$g^{4n+2}= g^{p-1} \equiv 1$ より

$\displaystyle 1, g^4, g^8, \ldots, g^{4n}, g^{2}, g^{4}, \ldots, g^{4n-2}$

となり、 $\bmod{p}$ の平方剰余をすべて回ることになる。

したがって、 $\{1^4, \, 2^4, \, \ldots, \, (p-1)^4 \}$ と $\{1^2, \, 2^2, \, \ldots, \, (p-1)^2 \}$ の間に全単射が存在することが言えます。

すなわち、合同式

$x^2 + y^2 + 1 \equiv 0 \pmod{p}$

の $\bmod{p}$ の解の個数と、合同式

$x^4 + y^4 + 1 \equiv 0 \pmod{p}$

の $\bmod{p}$ の解の個数は等しいことがわかります。

以下では、 $x^2 + y^2 + 1 \equiv 0 \pmod{p}$ の解の個数について議論することにしましょう。

前節までと同様、 $(x^2 + 1) + y^2 \equiv 0 \pmod{p}$ と分けて考えることにします。すると「平方剰余+1」が再び平方剰余になるかどうかが焦点となることが示唆されます。そこで、以下の補題を証明したいと思います：

補題4

$p \neq 2$ である素数とする。このとき、次が成り立つ：

$\displaystyle \sum_{k=1}^{p-1} \left(\frac{k}{p}\right)\left(\frac{k+1}{p}\right) = -1$

この和は一種の「ヤコブスタール和」だと思うのですが、これを計算します。

（補題4の証明）
$\bmod{p}$ の原始根を $g$ とすると

$\displaystyle \begin{align} \sum_{k=1}^{p-1} \left(\frac{k}{p}\right)\left(\frac{k+1}{p}\right) &= \sum_{k=1}^{p-1} \left(\frac{g}{p}\right)\left(\frac{k}{p}\right)\left(\frac{g}{p}\right)\left(\frac{k+1}{p}\right) \\ &= \sum_{k=1}^{p-1} \left(\frac{gk}{p}\right)\left(\frac{gk+g}{p}\right) \\ &= \sum_{k'=1}^{p-1} \left(\frac{k'}{p}\right)\left(\frac{k'+g}{p}\right) \\ \end{align}$

これを繰り返し適用すると $i = 1, \ldots, p-2$ に対し

$\displaystyle \begin{align} \sum_{k=1}^{p-1} \left(\frac{k}{p}\right)\left(\frac{k+1}{p}\right) = \sum_{k=1}^{p-1} \left(\frac{k}{p}\right)\left(\frac{k +g^i}{p}\right) \end{align}$

が成り立つ。 $1, g, g^2, \ldots, g^{p-2}$ は $\bmod{p}$ で $1, 2, \ldots, p-1$ をすべて巡回するので、 $a = 1, 2, \ldots, p-1$ に対して

$\displaystyle \begin{align} \sum_{k=1}^{p-1} \left(\frac{k}{p}\right)\left(\frac{k+1}{p}\right) = \sum_{k=1}^{p-1} \left(\frac{k}{p}\right)\left(\frac{k +a}{p}\right) \end{align}$

が成り立つ。

よって、上式を $a = 1, 2, \ldots, p-1$ に渡ってすべて足し合わせると

$\displaystyle \begin{align} (p-1)\sum_{k=1}^{p-1} \left(\frac{k}{p}\right)\left(\frac{k+1}{p}\right) = \sum_{k=1}^{p-1} \left(\frac{k}{p}\right) \left\{ \left(\frac{k +1}{p}\right) + \left(\frac{k +2}{p}\right) + \cdots + \left(\frac{k + p-1}{p}\right) \right\} \end{align}$

ここで、 $\sum_{k=1}^{p} \left(\frac{k}{p}\right) = 0$ より（原始根のルジャンドル記号 $\left(\frac{g}{p}\right)$ をかけると得られる）、

$\displaystyle \sum_{k=2}^{p} \left(\frac{k}{p}\right) = -1$

であるから

$\displaystyle \begin{align} (p-1)\sum_{k=1}^{p-1} \left(\frac{k}{p}\right)\left(\frac{k+1}{p}\right) &= \sum_{k=1}^{p-1} \left(\frac{k}{p}\right) \left\{ \left(\frac{k +1}{p}\right) + \left(\frac{k +2}{p}\right) + \cdots + \left(\frac{k + p-1}{p}\right) \right\} \\ &= \sum_{k=1}^{p-1} \left(\frac{k}{p}\right)^2 \left\{ \left(\frac{1 +1}{p}\right) + \left(\frac{1 +2}{p}\right) + \cdots + \left(\frac{1 + p-1}{p}\right) \right\} \\ &= \sum_{k=1}^{p-1} (-1) \\ &= -(p-1) \end{align}$

となり、両辺 $p-1$ で割って主張が得られた。

（補題4の証明終わり）

ここで、 $k = 1, \ldots, p-2$ に対して、ルジャンドル記号 $\left(\frac{k}{p}\right)$ と $\left(\frac{k+1}{p}\right)$ の符号が一致するような $k$ の個数を $F$ とする。符号が異なるような $k$ の個数を $E$ とする。すると明らかに

$E + F = p-2$

である。

一方、補題4は「符号が一致する個数より異なる方の個数が1多い」と主張しているので、

$E - F = 1$

である。よって

$\displaystyle E = \frac{p-1}{2} = 2n + 1$

が従います。最後に $p = 4n+3$ であることを使いました。

$\left(\frac{k}{p}\right)$ と $\left(\frac{k+1}{p}\right)$ の符号が異なるときに、以下の2パターンありうる：

$\left(\frac{k}{p}\right)$ が正で、 $\left(\frac{k+1}{p}\right)$ が負
$\left(\frac{k}{p}\right)$ が負で、 $\left(\frac{k+1}{p}\right)$ が正

$k = 1$ のとき正であり、 $k+1 = p-1$ のときに負になる（ $-1$ は $p = 4n+3$ の平方非剰余）ので（始点が正で終点が負なので）、（前者の個数）は（後者の個数）＋１にならなければならない。

シーソーにたとえて説明してみました：

ここにシーソーがあります。最初の状態では左が上がっていて、最後の状態では右が上がっていました。何回切り替わったかは分かりません。

左から右に切り替わった回数を R とし、右から左に切り替わった回数を L としたとき、L と R にはどのような関係があるでしょうか？
— tsujimotter ロマ数本好評発売中!! (@tsujimotter) 2020年10月4日

したがって、

$\displaystyle \#\left\{ k = 1, \ldots, p-2 \;\;\middle|\;\; \left(\frac{k}{p}\right) = 1, \;\; \left(\frac{k+1}{p}\right) = -1 \right\} = n+1$

が得られた。

これはつまり、 $\bmod{p}$ の平方剰余 $k$ が、平方非剰余 $K$ を用いて

$k + 1 \equiv K \pmod{p}$

と表せるような $(k, K)$ の個数が $n+1$ 個であることを主張している。

ここで、 $K$ を左辺に移行して

$k + (-1)K + 1 \equiv 0 \pmod{p}$

とする。 $-1$ は $\bmod{p}$ の平方非剰余なので、ルジャンドル記号の準同型性より $(-1)K$ は $\bmod{p}$ の平方剰余である。

すなわち、固定した $k$ に対して $k \equiv x^2 \pmod{p}, \;\; (-1)K \equiv y^2 \pmod{p}$ を満たす $x, y$ の組が $\bmod{p}$ において $(x, y), (-x, y), (x, -y), (-x, -y)$ の4組あることになる。

したがって、合同式

$x^2 + y^2 + 1 \equiv 0 \pmod{p}$

の $\bmod{p}$ の解の個数は

$4(n+1) = p+1$

であることがわかった。

したがって、 $N_p = p+1$ が得られた。

（定理3 証明終わり）

おわりに

いやー、めっちゃ長かったですね。特に、定理3の (1) の証明が大変でした。

これはガウスによる証明なのですが、 $\alpha + \alpha' + 1 \equiv 0 \pmod{p}$ の解の数え方も天才的ですし、それを実行するための計算量も尋常ではないですね。よくこんなことをやろうと思ったと言う感じがしますね。改めてガウスに対して畏敬の念を覚えました。ガウスやばい！！