https://tsujimotter.hatenablog.com/entry//3rd-proof-of-reciprocity-law

お久しぶりです。
今日のテーマは、平方剰余の相互法則の証明についてです。

平方剰余の相互法則を最初に証明したのはガウスです。
彼はこの定理を「黄金定理」と呼ぶほど大切にしており、生前に6つ、没後に発表されたものも含めて7つの異なる証明を与えました。これらは「第Ⅰ証明」から「第Ⅶ証明」と呼ばれています。

作者:倉田令二朗
日本評論社

このブログでも以前から、平方剰余の相互法則に関する話題を取り上げてきました。
たとえば、証明に関しては

などです。

私自身もこの定理が好きで、特に類体論との関わりから第Ⅵ証明を中心に勉強してきました。
一方で、それ以外の証明にはあまり注意を払っておらず、以前に読んだときもどうも腑に落ちない部分が多かったのです。

しかし最近になって、「どうせ一度の人生だし、全ての証明を理解してみたい」と思い立ち、改めて読み直してみました。すると、一度理解してしまえば案外わかりやすく、しかもとても面白いことがわかりました。

なかでも第Ⅲ証明は、そのシンプルさからウェブ上でも多く解説されています。そのため、自分が取り上げる必要はないと思っていたのですが、実際に理解してみると「これは面白い！」と感じる部分がありました。その魅力をぜひ紹介したいと思います。

というわけで、今回のブログでは平方剰余の相互法則の第Ⅲ証明の概略を紹介します。

正確に言うと、ここで扱うのはガウスの第Ⅲ証明そのものではなく、後に平易化された証明です。

参考にしたのはこちらの本です：

作者:西来路文朗,清水健一
講談社

平方剰余の相互法則とは

基本的なところからおさらいしたいと思います。

素数 $p$ を法とする合同式

$x^2 \equiv a \pmod{p}$

に対して、整数解 $x$ が存在するとき、 $a$ は $p$ の平方剰余であるといいます。逆に解 $x$ が存在しないとき、 $a$ は $p$ の平方非剰余であるといいます。

これらのことをより簡便に表現するのが次で定義されるルジャンドル記号です：

$\displaystyle \newcommand{\le}[2]{\left(\frac{{#1}}{{#2}}\right)} \le{a}{p} = \begin{cases} +1 & (a \, \text{は}\, p \, \text{の平方剰余}) \\ -1 & (a \, \text{は}\, p \, \text{の平方非剰余}) \end{cases}$

ここで2つの相異なる奇素数 $p, q$ を持ってきて、対称的なルジャンドル記号を考えます：

$\displaystyle \le{p}{q}, \;\; \le{q}{p}$

これらの定義は

$x^2 \equiv p \pmod{q}$

$x^2 \equiv q \pmod{p}$

という合同式に解があるかどうかなので、法が異なる2つの合同式の間には何の関係もないように思えます。

しかしながら、数学の世界は面白いもので、次のような美しい関係が成り立ちます。

平方剰余の相互法則

任意の相異なる奇素数 $p, q$ に対して、次が成り立つ：

$\displaystyle \le{p}{q} \le{q}{p} = (-1)^{\frac{(p-1)(q-1)}{4}} \tag{1}$

右辺が少し気持ち悪い人は、相異なる奇素数 $p, q$ の少なくとも1つが4n+1型であるときに

$\displaystyle \le{p}{q} = \le{q}{p}$

が成り立つとしてもいいでしょう。これは極めて綺麗な等式ですね。

証明のアイデア「格子点を数える」

証明のアイデアは、長方形内の格子点の個数を数えるというものです。

奇素数 $p, q$ に対して、4点

$\displaystyle (0, 0), \;\; \left(\frac{p}{2}, 0\right), \;\; \left(0, \frac{q}{2}\right), \;\; \left(\frac{p}{2}, \frac{q}{2}\right)$

を頂点に持つ長方形を考えます。この長方形の（境界を含まない）内側で「XY座標がどちらも整数であるような点（以下、格子点）」の個数を2通りの方法で数えましょう。

①1つめはシンプルに数えるというものですが、 $0 < x < p, \;\; 0 < y < q$ の範囲の格子点 $(x, y)$ の数は

となります。

②もう一つは、直線

$\displaystyle y = \frac{q}{p} x$

を引いて考えるというものです。この直線は先ほどの長方形の対角線になりますね。

さて、 $p, q$ は素数なので、この直線の上には格子点は存在しません。

仮に格子点が存在したとします。その座標を $(x_0, y_0)$ とすると、 $y_0 = \frac{qx_0}{p}$ が整数より $qx_0$ が $p$ で割り切れることになってしまいます。
しかしながら、 $q$ は $p$ で割り切れず、 $x < p$ より $x$ は $p$ で割り切れないので、矛盾します。

したがって、格子点は直線の下の三角形か、直線の上の三角形の上のいずれかの内部に存在します。

よって、格子点の個数には

の関係が成り立ちます。

最後のひと押しですが、直線の下の三角形内の格子点の個数を用いると、ルジャンドル記号が次のように得られます（ここが証明のキーポイントなので次節で詳しく説明します）：

また、同様に直線の上の三角形内の格子点の個数から

が得られます。

以上により

が得られ、これが平方剰余の相互法則となります。

「え、こんなんでいいの！？」
と思うような証明ですが、大変面白いですね！！

キーポイントは、三角形内の格子点の個数を使ってルジャンドル記号が書けるという式 $(2)$

ですね。これがあるからこそ格子点の個数を数えるという発想に至るわけです。

これが成り立つ仕組みについて考えていきたいと思います。

具体例による式 (2) の確認

なお、今回の例として出した図

は、相異なる奇素数を $p = 23, \; q = 11$ とした例となっています。

直線の下の三角形の格子点の個数は

なので

となりますが、これは

$\displaystyle \le{11}{23} = -1$

の結果と一致します。

確かに、式 $(2)$ が成り立っていることが確認できますね！

証明のキーポイントとガウスの補題

記事の最後に、証明のキーポイントである

を解説したいと思います。

証明の細部を追うのは面倒なので、今回の記事では大雑把にどういう理屈で示せるのかという概略に留めます。
（詳しくは参考文献の書籍「ガウスの黄金定理」を参照ください。）

式 $(2)$ は以下の3ステップで示せます。

ステップ1：

対角線 $\displaystyle y = \frac{q}{p} x$ の下の格子点の個数は

で表されます（理屈はこの後説明）。

記号 $[\cdot]$ はあの有名なガウス記号です。実数 $x$ に対して、 $x$ を超えない最大の整数を $[x]$ で表します。 $x$ の整数部分といってもよいでしょう。

証明の中に、ガウス記号 $[\cdot]$ が登場するのも面白いなと思います。何を隠そう、この記号がガウス記号と呼ばれるのは、ガウスがまさにこの証明のために使ったからです。面白いですね！

なお、式 $(4)$ のガウス記号の中身 $\displaystyle \frac{q}{p}$ はただの分数です。ルジャンドル記号が似たような形なので紛らわしいですね・・・。

式 $(4)$ が成り立つ理由を説明します。まず、適当に $x$ を1つ選び、直線 $y = \frac{p}{q}x$ 以下の格子点の個数を数えます。

これは $y$ の整数部分にほかなりませんので

$\displaystyle \left[\frac{xq}{p}\right]$

となります。これを $x = 1, 2, \ldots, \frac{p-1}{2}$ で足し合わせることで、下の三角形内の格子点の個数、すなわち式 $(4)$ が得られます。

ステップ2：

ステップ2は「ガウスの補題」と呼ばれる定理です。

定理（ガウスの補題）

$p$ を奇素数、 $a$ を $p$ と互いに素な整数とする。
$a$ に $\displaystyle x = 1, 2, 3, \ldots, \frac{p-1}{2}$ を掛けて得られる数

$\displaystyle 1\cdot a, \;\; 2\cdot a, \;\; 3\cdot a, \;\; \ldots, \;\; \frac{p-1}{2} \cdot a$

を $p$ で割るとき、あまりが $\displaystyle \frac{p-1}{2}$ より大きい数の個数を $t$ とすると

$\displaystyle \le{a}{p} = (-1)^{t}$

が成り立つ。

「いったいなんだこの定理は！？」と思うかもしれませんが、これはフェルマーの小定理

$a^{p-1} \equiv 1 \pmod{p}$

の証明の発展系だと思うとよいので、フェルマーの小定理の証明を思い出しましょう。

フェルマーの小定理は、 $a$ に $p-1$ 個の数 $x = 1, 2, 3, \ldots, (p-1)$ を掛けて得られる数

$\displaystyle 1\cdot a, \;\; 2\cdot a, \;\; 3\cdot a, \;\; \ldots, \;\; (p-1) \cdot a$

を $p$ で割ったあまりの集合と

$\displaystyle 1, \;\; 2, \;\; 3, \;\; \ldots, \;\; (p-1)$

が等しいことから示されます。

つまり、最初の集合をすべて掛けたものと、二つ目の集合をすべて掛けたものが等しいことより

$1\cdot 2 \cdot 3 \cdot \cdots \cdot (p-1) a^{p-1} \; \equiv \; 1\cdot 2 \cdot 3 \cdot \cdots \cdot (p-1) \pmod{p}$

が成り立ちます。両辺に $1\cdot 2 \cdot 3 \cdot \cdots \cdot (p-1)$ の逆元を掛けることでフェルマーの小定理を得ます。

さて、これと同じことを半分の集合

$\displaystyle A = \left\{1, \;\; 2, \;\; 3, \;\; \ldots, \;\; \frac{p-5}{2}, \;\; \frac{p-3}{2}, \;\; \frac{p-1}{2} \right\}$

に対して実行したのがガウスの補題だと思えます。

$\displaystyle \frac{p-1}{2}$ より大きい数からなる残りの集合

$\displaystyle B = \left\{\frac{p+1}{2}, \;\; \frac{p+3}{2}, \;\; \frac{p+5}{2}, \;\; \ldots, \;\; (p-3), \;\; (p-2),\;\; (p-1)\right\}$

は、法 $p$ のもとで

$\displaystyle B' = \left\{-\frac{p-1}{2}, \;\; -\frac{p-3}{2}, \;\; -\frac{p-5}{2}, \;\; \ldots, \;\; -3, \;\; -2, \;\; -1\right\}$

のように表すことができます（ $x \in B$ に対して $x-p$ とおけばよい）。つまり、 $A$ の元にマイナスをつけたものが $B'$ だというわけですね。

さて、 $A$ の元を1つずつ $a$ に掛けて得られる

$\displaystyle 1\cdot a, \;\; 2\cdot a, \;\; 3\cdot a, \;\; \ldots, \;\; \frac{p-3}{2}\cdot a, \;\; \frac{p-1}{2}\cdot a$

を考えます。これらは法 $p$ のもとで $A$ に属するか、 $B$ に属するかのいずれかです。 $B$ に属する数の個数が $t$ というわけです。

ここで、 $B$ に属する場合は $B'$ の表現をして $(-1)$ 倍することで $A$ の元にすることができます。

これによって、 $A$ の元を列挙することができて、なおかつ、 $(-1)$ 倍の個数は $t$ に一致します。つまり

$\displaystyle 1\cdot 2 \cdot \cdots \cdot \frac{p-1}{2} \cdot a^{\frac{p-1}{2}} \; \equiv \; (-1)^t \cdot 1\cdot 2 \cdot \cdots \cdot \frac{p-1}{2} \pmod{p}$

が成り立ちます。両辺に $1\cdot 2 \cdot \cdots \cdot \frac{p-1}{2}$ の逆元を掛けることで

$\displaystyle a^{\frac{p-1}{2}} \; \equiv \; (-1)^t \pmod{p}$

が得られます。また、オイラーの規準

$\displaystyle a^{\frac{p-1}{2}} \; \equiv \; \le{a}{p} \pmod{p}$

によって

$\displaystyle \le{a}{p} \; \equiv \; (-1)^t \pmod{p}$

が得られます。これが目的の合同式でした。

ステップ3：

ステップ1で得られたガウス記号がたくさん出てくる数

$\displaystyle \left[\frac{q}{p}\right] + \left[\frac{2q}{p}\right] + \left[\frac{3q}{p}\right] + \cdots + \left[\frac{(\frac{p-1}{2})q}{p}\right]$

とステップ2で登場したガウスの補題で登場する指数

$\displaystyle t$

の間に

$\displaystyle \left[\frac{q}{p}\right] + \left[\frac{2q}{p}\right] + \left[\frac{3q}{p}\right] + \cdots + \left[\frac{(\frac{p-1}{2})q}{p}\right] \equiv t \pmod{2}$