平方剰余の相互法則(3) - エレファント・コンピューティング調査報告

以下の本を参照して平方剰余の相互法則の証明を調べてみたいと思います。

「平方剰余の相互法則ガウスの全証明」
「数論への出発増補版」
「整数論」(共立講座 21世紀の数学)

ガウスは平方剰余の相互法則の7通りの証明を与えたそうで「平方剰余の相互法則ガウスの全証明」にはそのI～VIIの証明があります。Vの証明は「ガウスの補題」を使ってある集合の元の個数が偶数か奇数かを調べるという方法です。「整数論」(共立講座 21世紀の数学)の証明も同様の方法と考えられます。IIIの証明は「ガウス記号」を使う方法ですが、これも「ガウスの補題」を使うもののようです。IV、VI、VIIの証明は「ガウスの和」を使う方法です。「数論への出発増補版」はVIIの証明に近いもののようです。

まず「ガウスの補題」を見ていきたいと思います。

$F_p^* = \{1, 2, 3, … , p-1\}$ は巡回群になります。 $r$ を $F_p^*$ の生成元とします。 $F_p^* = \{r^i | i = 0, 1, 2, … , p-2\}$ 、 $r^{ \frac{p-1}{2} }= -1$ となります。

【ガウスの補題1】

$F_p^*$ の部分集合 $\{1, 2, 3, … , \frac{p-1}{2}\}$ を $S$ とおきます。 $a$ を $S$ の元とすると、

$ax∈F_p^*-S$ となるような $x∈S$ の個数が偶数 ⇔ $a$ は法 $p$ に関する平方剰余

[証明]
$f: F_p^*→\{0, 1\}$ を $x∈S$ のとき $f(x)$ = $0$ 、そうでないとき $f(x) = 1$ とします。 $g: F_p^*→S$ を $x∈S$ のとき $g(x) = x$ 、そうでないとき $g(x) = -x$ とします。すると $x = (-1)^{f(x)}・g(x)、g(x) = (-1)^{f(x)}・x$ となります。 $h: S→S$ を $h(x) = g(ax)$ とおくと $h$ は全単射となります。なぜなら $h(x) = h(y)$ とすると $g(ax) = g(ay)$ 、 $(-1)^{f(ax)}・ax = (-1)^{f(ay)}・ay、(-1)^{f(ax)-f(ay)}・ax = ay$ となりますが、これが成り立つのは $f(ax) = f(ay)$ かつ $x = y$ のときだけです。 $S$ のすべての元 $x$ についての積 $\prod ax = \prod ( (-1)^{f(ax)}・g(ax)) = \prod ( (-1)^{f(ax)})・\prod g(ax)$ を考えると $h$ は全単射なので $\prod g(ax) = \prod x$ ですから $\prod ( (-1)^{f(ax)}) = (\prod ax)/(\prod x) = a^{\frac{p-1}{2}}$ となります。
$F_p^*$ の元 $x$ に対して $x = r^{e(x)}$ となるように $e(x)$ を決めます。 $\prod ( (-1)^{f(ax)}) = a^{\frac{p-1}{2}} = (r^{e(a)})^{\frac{p-1}{2}} = (r^{\frac{p-1}{2}})^{e(a)} = (-1)^{e(a)}$ となります。よって
$\{x∈S | f(ax) = 1\} の元の個数が偶数 ⇔ e(a) は偶数$
となって主張が成り立ちます。
[証明終わり]

【ガウスの補題2】

$F_p^*$ を共通部分のない2つの部分集合 $S$ と $-S$ に分割します。 $-S$ はある $S$ の元 $a$ に対して $-a$ であるもの全体の集合とします。
このとき $a$ を $S$ の元とすると、

$ax∈-S$ となるような $x∈S$ の個数が偶数 ⇔ $a$ は法 $p$ に関する平方剰余

[証明]
$F_p^*$ の元 $a$ に対して $P(a) = \{a, -a\}$ とおきます。 $X = \{P(1), P(2), … , P(\frac{p-1}{2})\}$ とおきます。 $F_p^*$ の元 $a$ に対して $X$ から $X$ への写像で、 $P(n)$ を $P(an)$ に写すものは全単射となります。したがって $S$ の元を $s(1)$ , $s(2)$ , … , $s(\frac{p-1}{2})$ とすると、 $F_p^*$ の元 $a$ に対して $\{P(as(1)), P(as(2)), … , P(as(\frac{p-1}{2}))\} = X$ となります。 $as(i)$ が $-S$ に含まれる $i$ の個数を $n$ とすると
$a^{\frac{p-1}{2}} = (as(1)as(2)…as(\frac{p-1}{2})) / (s(1)s(2)…s(\frac{p-1}{2})) = (-1)^n$
となります。よって
$\{x∈S | f(ax) = 1\} の元の個数が偶数 ⇔ e(a) は偶数$
となります。
また $F_p^*$ の元 $x$ に対して $x = r^{e(x)}$ となるように $e(x)$ を決めると
$a^{\frac{p-1}{2}} = (r^{e(a)})^{\frac{p-1}{2}} = (r^{\frac{p-1}{2}})^{e(a)} = (-1)^{e(a)}$
となります。
[証明終わり]

ガウスの補題を使って平方剰余の相互法則を証明します。その前にガウスの補題の図を描いてみます。

以下の表は縦に $x$ 、横に $y$ をとったとき $xy$ を $47$ で割った余りが $24$ 以上のとき■、そうでないとき□としたものです。いちばん左の列がは■の個数が偶数のとき●、奇数のとき○としたものです。ガウスの補題により●のとき $x$ が法 $47$ に関する平方剰余となります。

●	0001	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□
●	0002	□	□	□	□	□	□	□	□	□	□	□	■	■	■	■	■	■	■	■	■	■	■	■
●	0003	□	□	□	□	□	□	□	■	■	■	■	■	■	■	■	□	□	□	□	□	□	□	□
●	0004	□	□	□	□	□	■	■	■	■	■	■	□	□	□	□	□	□	■	■	■	■	■	■
○	0005	□	□	□	□	■	■	■	■	■	□	□	□	□	□	■	■	■	■	□	□	□	□	□
●	0006	□	□	□	■	■	■	■	□	□	□	□	■	■	■	■	□	□	□	□	■	■	■	■
●	0007	□	□	□	■	■	■	□	□	□	□	■	■	■	□	□	□	■	■	■	■	□	□	□
●	0008	□	□	■	■	■	□	□	□	■	■	■	□	□	□	■	■	■	□	□	□	■	■	■
●	0009	□	□	■	■	■	□	□	■	■	■	□	□	□	■	■	□	□	□	■	■	□	□	□
○	0010	□	□	■	■	□	□	□	■	■	□	□	■	■	■	□	□	■	■	□	□	□	■	■
○	0011	□	□	■	■	□	□	■	■	□	□	■	■	□	□	■	■	■	□	□	■	■	□	□
●	0012	□	■	■	□	□	■	■	□	□	■	■	□	□	■	■	□	□	■	■	□	□	■	■
○	0013	□	■	■	□	□	■	■	□	□	■	□	□	■	■	□	□	■	■	□	■	■	□	□
●	0014	□	■	■	□	□	■	□	□	■	■	□	■	■	□	□	■	□	□	■	■	□	■	■
○	0015	□	■	■	□	■	■	□	■	■	□	■	■	□	□	■	□	□	■	□	□	■	□	□
●	0016	□	■	□	□	■	□	□	■	□	□	■	□	□	■	□	□	■	□	□	■	□	□	■
●	0017	□	■	□	□	■	□	■	■	□	■	■	□	■	□	□	■	□	■	■	□	■	■	□
●	0018	□	■	□	■	■	□	■	□	□	■	□	■	■	□	■	□	■	■	□	■	□	□	■
○	0019	□	■	□	■	□	□	■	□	■	□	□	■	□	■	□	□	■	□	■	□	□	■	□
○	0020	□	■	□	■	□	■	■	□	■	□	■	□	■	■	□	■	□	■	□	■	■	□	■
●	0021	□	■	□	■	□	■	□	■	□	□	■	□	■	□	■	□	■	□	□	■	□	■	□
○	0022	□	■	□	■	□	■	□	■	□	■	□	■	□	■	□	□	■	□	■	□	■	□	■
○	0023	□	■	□	■	□	■	□	■	□	■	□	■	□	■	□	■	□	■	□	■	□	■	□

【ルジャンドルの記号】

ここで以前説明した拡張された記法を使います。 $p$ が $2$ ではない素数のとき、

$a$ が $p$ の倍数のとき $\left(\cfrac{a}{p}\right) = 0$
$a$ が $p$ の倍数ではなく、 $a$ が法 $p$ に関する平方剰余であるとき $\left(\cfrac{a}{p}\right) = 1$
$a$ が $p$ の倍数ではなく、 $a$ が法 $p$ に関する平方剰余ではないとき $\left(\cfrac{a}{p}\right) = -1$

【 $\left(\cfrac{a}{p}\right)$ の性質】

$p$ を $2$ ではない素数、 $a$ を整数とします。

(1) $a≡b \ (\mathrm{mod} \ p)$ ならば $\left(\cfrac{a}{p}\right) = \left(\cfrac{b}{p}\right)$
(2) $\left(\cfrac{ab}{p}\right) = \left(\cfrac{a}{p}\right)\left(\cfrac{b}{p}\right)$

【平方剰余の相互法則】

$p$ , $q$ が異なる $2$ ではない素数のとき、( $p$ , $q$ は奇数なので、 $4$ で割ると $1$ 余るか $3$ 余るかのどちらかとなります)

$p$ を $4$ で割ると $1$ 余るか、または、 $q$ を $4$ で割ると $1$ 余るときは、 $\left(\cfrac{p}{q}\right) = \left(\cfrac{q}{p}\right)$ 、
$p$ を $4$ で割ると $3$ 余り、かつ、 $q$ を $4$ で割ると $3$ 余るときは、 $\left(\cfrac{p}{q}\right) = -\left(\cfrac{q}{p}\right)$ 、

すなわち $\left(\cfrac{p}{q}\right) \left(\cfrac{q}{p}\right) = (-1)^{ \frac{(p-1)(q-1)}{4} }$ が成り立ちます。

[証明]
「整数論」(共立講座 21世紀の数学)のやり方で証明します。以下の表は縦に $x = 1, 2, … , \frac{p-1}{2}$ 、横に $y = 1, 2, … , \frac{q-1}{2}$ をとったときに

■は $\frac{q}{p}x < y < \frac{q}{p}x + \frac{1}{2}$
▲は $\frac{p}{q}y < x < \frac{p}{q}y + \frac{1}{2}$
□は $y > \frac{q}{p}x + \frac{1}{2}$
△は $x > \frac{p}{q}y + \frac{1}{2}$

としたものです。(この表では $p = 47, q = 41$ )

0001	■	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□
0002	△	■	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□
0003	△	△	■	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□
0004	△	△	△	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□
0005	△	△	△	▲	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□
0006	△	△	△	△	▲	□	□	□	□	□	□	□	□	□	□	□	□	□	□	□
0007	△	△	△	△	△	▲	□	□	□	□	□	□	□	□	□	□	□	□	□	□
0008	△	△	△	△	△	△	■	□	□	□	□	□	□	□	□	□	□	□	□	□
0009	△	△	△	△	△	△	△	■	□	□	□	□	□	□	□	□	□	□	□	□
0010	△	△	△	△	△	△	△	△	■	□	□	□	□	□	□	□	□	□	□	□
0011	△	△	△	△	△	△	△	△	△	■	□	□	□	□	□	□	□	□	□	□
0012	△	△	△	△	△	△	△	△	△	△	□	□	□	□	□	□	□	□	□	□
0013	△	△	△	△	△	△	△	△	△	△	▲	□	□	□	□	□	□	□	□	□
0014	△	△	△	△	△	△	△	△	△	△	△	▲	□	□	□	□	□	□	□	□
0015	△	△	△	△	△	△	△	△	△	△	△	△	▲	□	□	□	□	□	□	□
0016	△	△	△	△	△	△	△	△	△	△	△	△	△	■	□	□	□	□	□	□
0017	△	△	△	△	△	△	△	△	△	△	△	△	△	△	■	□	□	□	□	□
0018	△	△	△	△	△	△	△	△	△	△	△	△	△	△	△	■	□	□	□	□
0019	△	△	△	△	△	△	△	△	△	△	△	△	△	△	△	△	■	□	□	□
0020	△	△	△	△	△	△	△	△	△	△	△	△	△	△	△	△	△	□	□	□
0021	△	△	△	△	△	△	△	△	△	△	△	△	△	△	△	△	△	▲	□	□
0022	△	△	△	△	△	△	△	△	△	△	△	△	△	△	△	△	△	△	▲	□
0023	△	△	△	△	△	△	△	△	△	△	△	△	△	△	△	△	△	△	△	▲

■▲□△は $\frac{p-1}{2} \times \frac{q-1}{2}$ の長方形を全部埋めて、重複はありません。また□と△の個数は同じです。これを $c$ とおきます。■の個数は $\frac{q}{p}x < y < \frac{q}{p}x + \cfrac{1}{2}$ を満たす $x$ , $y$ の組の個数なので、 $\frac{1}{2} < \frac{q}{p}x - (y - 1) < 1$ より $\frac{q}{p}x$ の整数部分が $\frac{1}{2}$ と $1$ の間にある $x$ の個数となります。これを $a$ とおきます。 $f: F_p^*→\{0, 1\}$ を $x∈S = \{1, 2, 3, … , \frac{p-1}{2}\}$ のとき $f(x) = 0$ 、そうでないとき $f(x) = 1$ とすると■の個数は $f(qx) = 1$ となる $x$ の個数となります。
ガウスの補題より $(-1)^a = (-1)^{(\sum f(qx))} = \left(\cfrac{q}{p}\right)$ となります。 ▲の個数は $\frac{p}{q}y < x < \frac{p}{q}y + \frac{1}{2}$ を満たす $x$ , $y$ の組の個数なので、これを $b$ とおくと、上の議論で $p$ と $q$ を入れ替えて $(-1)^b = \left(\cfrac{p}{q}\right)$ となります。
$a + b + 2c = \frac{(p-1)(q-1)}{4}$ より $\left(\cfrac{p}{q}\right) = \left(\cfrac{q}{p}\right) = (-1)^{a+b} = (-1)^{ \frac{(p-1)(q-1)}{4} }$ となります。
[証明終わり]

【ガウスの補題1】

【ガウスの補題2】

【ルジャンドルの記号】

【の性質】

【平方剰余の相互法則】

【 $\left(\cfrac{a}{p}\right)$ の性質】