証明路開発支援システム(18) - 非専門的シンギュラリティー研究所

ChatGPT で「ガウスの補題」を使った証明を調べてみました。『発見・予想を積み重ねる ―それが整数論』、『はじめての数論　原著第4版』の証明や『ガウスの黄金定理　平方剰余の相互法則で語る数論の世界 (ブルーバックス)』の「ガウスの補題」を使った証明と同様と思われます。ChatGPT によると「ガウスの補題と格子点計数」の証明のようですが「アイゼンシュタインの証明」との違いはよくわかりません。この証明は「証明路」にするのは難しそうですが、何かにはできそうです。

まず「ガウスの補題」のための補題を考えます。

整数 $x$ を整数 $y \ne 0$ で割った余りを $x \bmod y$ とします( $0 \le x \bmod y \le y - 1$ )。

補題 1

$p$ を奇素数、 $a$ を $p$ と互いに素な整数とします。
$S = \left\{1, 2, 3, … , \cfrac{p-1}{2}\right\}$
とおきます。
$g: \mathbb{Z}→S$ を

$x \bmod p ∈ S$ のとき $g(x) = x \bmod p$ 、
$x \bmod p \not ∈ S$ のとき $g(x) = p - (x \bmod p)$

とすると
$\displaystyle \sum_{x \in S} g(ax) = \sum_{x \in S} x$
$\displaystyle \prod_{x \in S} g(ax) = \prod_{x \in S} x$
が成り立ちます。

証明

を
- $x \bmod p ∈ S$ のとき $f(x)$ = $0$ 、
- $x \bmod p \not ∈ S$ のとき $f(x) = 1$
とします。
すると
- $g(x) = (-1)^{f(x)}・(x \bmod p) + pf(x)$
- $g(x) \equiv (-1)^{f(x)}・x \pmod p$
となります。
をとおくとは全単射となります。
- なぜならとすると
  - $g(ax) = g(ay)$
  - $(-1)^{f(ax)}・ax \equiv (-1)^{f(ay)}・ay \pmod p$
  - $(-1)^{f(ax)-f(ay)}・ax \equiv ay \pmod p$
  - $(-1)^{f(ax)-f(ay)}・x \equiv y \pmod p$
  なのでかつとなります。よっては単射となります。
- $S$ は有限集合なので $h$ は全単射となります。
よって
$\displaystyle \sum_{x \in S} g(ax) = \sum_{x \in S} x$
$\displaystyle \prod_{x \in S} g(ax) = \prod_{x \in S} x$
が成り立ちます。

以下は ChatGPT の証明を書き直したものです。

定理 2 (ガウスの補題)

$p$ を奇素数、 $a$ を $p$ と互いに素な整数とします。
$\displaystyle a,2a,\ldots,\frac{p-1}{2}a$
を法 $p$ で最小絶対値の代表
$\displaystyle -\frac{p-1}{2},\ldots,-1,1,\ldots,\frac{p-1}{2}$
に直します。この中で負になるものの個数を $n(a,p)$ とすると
$\displaystyle \left(\frac ap\right)=(-1)^{n(a,p)}$
となります。ここで
$\displaystyle \left(\frac ap\right)$
はルジャンドル記号です。

証明

補題 1 の $f$ 、 $g$ を使って
$\displaystyle \prod_{x \in S} ax \equiv \prod_{x \in S} \left( (-1)^{f(ax)}・g(ax) \right) \equiv \prod_{x \in S} \left( (-1)^{f(ax)} \right)・\prod_{x \in S} g(ax) \equiv \prod_{x \in S} \left( (-1)^{f(ax)} \right)・\prod_{x \in S} x \pmod p$
となります。
よって
$\displaystyle a^{\frac{p-1}{2}} \equiv \left(\prod_{x \in S} ax \right)/\left(\prod_{x \in S} x \right) \equiv \prod_{x \in S} \left( (-1)^{f(ax)} \right) \equiv (-1)^{\sum_{x \in S}f(ax)} \equiv (-1)^{n(a,p)} \pmod p$
となります。
「オイラーの規準」より
$\displaystyle \left(\frac ap\right) \equiv a^{\frac{p-1}{2}} \equiv (-1)^{n(a,p)}\pmod p$
となります。
$\displaystyle \left(\frac ap\right) = 1$ または $\displaystyle \left(\frac ap\right) = -1$ なので
$\displaystyle \left(\frac ap\right) = (-1)^{n(a,p)}$
となります。

定理 3 (平方剰余の相互法則)

$p$ 、 $q$ が $2$ ではない異なる素数のとき、
$\displaystyle \left(\frac{q}{p}\right) \left(\frac{p}{q}\right) = (-1)^{ \frac{(p-1)(q-1)}{4} }$
が成り立ちます。

証明

Step 1

ガウスの補題より
$\displaystyle \left(\frac qp\right)=(-1)^{n(q,p)}$
$\displaystyle \left(\frac pq\right)=(-1)^{n(p,q)}$
となります。したがって
$\displaystyle \left(\frac pq\right) \left(\frac qp\right) = (-1)^{n(p,q)+n(q,p)}$
となります。

残る仕事は
$\displaystyle n(p,q)+n(q,p) \equiv \frac{(p-1)(q-1)}4 \pmod2$
を示すことです。

Step 2 格子点を数える

長方形
$\displaystyle 0 < x < \frac p2,\qquad 0 < y < \frac q2$
の整数格子点を考えます。つまり
$\displaystyle 1\le x\le\frac{p-1}2,\qquad 1\le y\le\frac{q-1}2$
です。全部で
$\displaystyle \frac{(p-1)(q-1)}4$
個あります。

Step 3 直線で分ける

直線
$\displaystyle qx=py$
を引きます。 $p,q$ は互いに素なので、この直線は格子点を通りません。したがって全ての格子点は

上側
下側

のどちらかに入ります。

Step 4 下側の点

下側 $\displaystyle py>qx$ では $\displaystyle y > \frac{qx}{p}$ となるので、各 $x$ に対して
$\displaystyle \left\lfloor \frac{qx}{p} \right\rfloor$
が現れます。
$\displaystyle n(q, p) \equiv \sum_{x=1}^{(p-1)/2} \left\lfloor \frac{qx}{p} \right\rfloor \pmod2$
となることを証明します。

のとき( が法で「正」のとき)
- $r(x) = qx \bmod p$ とします。
- $\displaystyle qx = \left\lfloor \frac{qx}{p} \right\rfloor p + r(x)$
のとき( が法で「負」のとき)
- $r(x) = p - (qx \bmod p)$ とします。
- $\displaystyle qx = \left\lfloor \frac{qx}{p} \right\rfloor p + (p - r(x))$
- $\displaystyle qx \equiv \left\lfloor \frac{qx}{p} \right\rfloor p + p + r(x) \pmod2$
$n(q, p)$ は $qx$ が法 $p$ で「負」になる $x$ の個数なので
$\displaystyle \sum_{x=1}^{(p-1)/2}qx \equiv \sum_{x=1}^{(p-1)/2}\left\lfloor \frac{qx}{p} \right\rfloor p + n(q, p)p + \sum_{x=1}^{(p-1)/2}r(x) \pmod2$
補題 1 より $\displaystyle \sum_{x=1}^{(p-1)/2}r(x) = \sum_{x=1}^{(p-1)/2}x$ となるので
$\displaystyle q\sum_{x=1}^{(p-1)/2}x \equiv \sum_{x=1}^{(p-1)/2}\left\lfloor \frac{qx}{p} \right\rfloor p + n(q, p)p + \sum_{x=1}^{(p-1)/2}x \pmod2$
$\displaystyle (q - 1)\sum_{x=1}^{(p-1)/2}x \equiv \sum_{x=1}^{(p-1)/2}\left\lfloor \frac{qx}{p} \right\rfloor p + n(q, p)p \pmod2$
$\displaystyle 0 \equiv \sum_{x=1}^{(p-1)/2}\left\lfloor \frac{qx}{p} \right\rfloor p + n(q, p)p \pmod2$
$\displaystyle 0 \equiv \sum_{x=1}^{(p-1)/2}\left\lfloor \frac{qx}{p} \right\rfloor + n(q, p) \pmod2$
$\displaystyle n(q, p) \equiv \sum_{x=1}^{(p-1)/2}\left\lfloor \frac{qx}{p} \right\rfloor \pmod2$

Step 5 上側

同様に
$\displaystyle n(p, q) \equiv \sum_{y=1}^{(q-1)/2} \left\lfloor \frac{py}{q} \right\rfloor \pmod2$

Step 6 合計

長方形の格子点は

上側
下側

に完全に分かれるので
$\displaystyle \sum_{x=1}^{(p-1)/2} \left\lfloor \frac{qx}{p} \right\rfloor + \sum_{y=1}^{(q-1)/2} \left\lfloor \frac{py}{q} \right\rfloor = \frac{(p-1)(q-1)}4$
です。これと
$\displaystyle n(p, q)+n(q, p) \equiv \sum_{x=1}^{(p-1)/2} \left\lfloor \frac{qx}{p} \right\rfloor + \sum_{y=1}^{(q-1)/2} \left\lfloor \frac{py}{q} \right\rfloor \pmod2$
より
$\displaystyle n(p, q)+n(q, p) \equiv \frac{(p-1)(q-1)}4 \pmod2$
となります。したがって
$\displaystyle (-1)^{n(p, q)+n(q, p)} = (-1)^{\frac{(p-1)(q-1)}4}$
よって
$\displaystyle \boxed{\left(\frac pq\right) \left(\frac qp\right) = (-1)^{\frac{(p-1)(q-1)}4}}$
が従います。

他の証明

ChatGPT によると

この証明の核心

証明の本質は、
1. ガウスの補題によってルジャンドル記号を「負になる倍数の個数」に置き換える。
2. その個数を格子点の個数として解釈する。
3. 長方形を直線 $qx=py$ で二分することで、二つの個数の和が長方形全体の格子点数になることを示す。
という、数論を幾何学的な格子点計数へ翻訳する点にあります。

以下のような証明があるようです。

他の代表的な証明

平方剰余の相互法則には、ガウス自身だけでも複数の証明を与えており、その後もさまざまな証明が見つかっています。代表的なものとしては次のような方法があります。

ガウスの補題と格子点計数（上で説明した古典的な証明）

アイゼンシュタインの証明（床関数の和を直接計算する方法）

ヤコビ和・ガウス和を用いる解析的な証明

有限体の性質を利用する証明

代数的整数論（円分体など）による証明

フーリエ解析や指標和を利用する現代的な証明

特に、ガウスの補題による証明とアイゼンシュタインの証明は非常に近い関係にあり、多くの教科書ではこの二つを並べて扱っています。