![[logo]](https://img.hyuki.net/20220628121544-7a397ed015277339.png)
Web連載「数学ガールの秘密ノート」
登場人物紹介
僕：数学が好きな高校生。
テトラちゃん：僕の後輩。 好奇心旺盛で根気強い《元気少女》。言葉が大好き。
ミルカさん：数学が好きな高校生。 僕のクラスメート。メタルフレームの眼鏡に長い黒髪の《饒舌才媛》。
ここは高校の図書室。いまは放課後。
テトラちゃんと僕は、 ミルカさんが提示した「数論におけるガウスの補題」を理解しようとしているところ（第478回参照）。
ガウスの補題（再掲）（第478回参照）
$p$ を奇素数とする。
$n$ を $p$ と互いに素な整数とする。
$x$ を $p$ で割った余りを $\BAR{x}$ で表す。 そして、 $\frac{p-1}{2}$ 個の正整数 $$ \BAR{1n}\CommaQuad \BAR{2n}\CommaQuad \BAR{3n}\CommaQuad \ldots\CommaQuad \BAR{\tfrac{p-1}{2}n} $$ のうち 《$\frac{p-1}{2}$より$\MARKC{\text{大きいもの}}$の個数》 を $\ell$ とする。 すると、 $$ \LegSym{n}{p} = (-1)^{\ell} $$ が成り立つ。
ただし、 $\tLegSym{n}{p}$ はルジャンドル記号である。
テトラ「なかなか……難しいですね」
$p = 7$ についてガウスの補題を表にしたテトラちゃんはそう言った（第478回参照）。
ミルカ「$p = 11$ の表も作ろう。 そうすれば《右手の指》と《左手の指》が考えられる」
ミルカさんは、両手の指を合わせて胸の前に小さな《鳥かご》を作って言った。
親指は親指に、 人差し指は人差し指に、 ……そして、小指は小指に合わせ、 ふくらませた形だ。
僕は、これを知ってる。 全単射の鳥かごだ（『数学ガール／ゲーデルの不完全性定理』参照）。
テトラ「？」
僕「？」
テトラちゃんと僕は、 大きな疑問符を心に抱きながら、 $p = 11$ についてガウスの補題の表を作っていった。
$p = 11$ でガウスの補題を考える
$$ \begin{array}{|c|ccccc|c|c|c|} \hline n & \BAR{1n} & \BAR{2n} & \BAR{3n} & \BAR{4n} & \BAR{5n} & \ell & (-1)^\ell & \tLegSym{n}{p} \\ \hline 1 & 1 & 2 & 3 & 4 & 5 & 0 & \LegYES & \LegYES \\ \hline 2 & 2 & 4 & \MARKC6 & \MARKC8 & \MARKC{10} & 3 & \LegNO & \LegNO \\ \hline 3 & 3 & \MARKC6 & \MARKC9 & 1 & 4 & 2 & \LegYES & \LegYES \\ \hline 4 & 4 & \MARKC8 & 1 & 5 & \MARKC9 & 2 & \LegYES & \LegYES \\ \hline 5 & 5 & \MARKC{10} & 4 & \MARKC9 & 3 & 2 & \LegYES & \LegYES \\ \hline 6 & \MARKC6 & 1 & \MARKC7 & 2 & \MARKC8 & 3 & \LegNO & \LegNO \\ \hline 7 & \MARKC7 & 3 & \MARKC{10} & \MARKC6 & 2 & 3 & \LegNO & \LegNO \\ \hline 8 & \MARKC8 & 5 & 2 & \MARKC{10} & \MARKC7 & 3 & \LegNO & \LegNO \\ \hline 9 & \MARKC9 & \MARKC7 & 5 & 3 & 1 & 2 & \LegYES & \LegYES \\ \hline 10 & \MARKC{10} & \MARKC9 & \MARKC8 & \MARKC7 & \MARKC6 & 5 & \LegNO & \LegNO \\ \hline \end{array} $$
$\MARKC{\text{緑色の数}}$は$\frac{p-1}{2} = 5$より大きい数を表す。
$\MARKC{\text{緑色の数}}$の個数が$\ell$である。
$x$ を $p$ で割った余りを $\BAR{x}$ で表す。
テトラ「先輩！ あたし、この表で気づいたことがあります！」
僕「うん、僕もだ！」
テトラ「上半分と下半分が、ちょうど裏返しになってますね！」
上半分と下半分が裏返し
ミルカ「その理由はすぐわかる。 テトラが見つけた対称性は、 $$ \BAR{kn} \LEQ \frac{p-1}{2} \LONGBOTHIMPLIES \BAR{k(p-n)} > \frac{p-1}{2} $$ ということだ。これは、 $$ \BAR{k(p-n)} = \BAR{kp - kn} = \BAR{-kn} = p - \BAR{kn} $$ であることからいえる」
テトラ「ああ、はい。確かにそうですね」
僕「もしかして、 $p$ による剰余 $\BAR{x}$ よりも、 絶対的最小剰余 $\HAT{x}$ の方が対称性がよく見えるんじゃないかなあ？ $\BAR{x}$ が $\frac{p-1}{2}$ より大きいかどうかというのは、 $\HAT{x}$ が負になるかどうかだから」
$p = 11$ のときの剰余 $\BAR{x}$ と絶対的最小剰余 $\HAT{x}$ （第477回参照）
$$ \begin{array}{|c|c|ccccc|ccccc|} \hline \BAR{x} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \HAT{x} & 0 & 1 & 2 & 3 & 4 & 5 & -5 & -4 & -3 & -2 & -1 \\ \hline \end{array} $$
ミルカ「そうだな。 そして、 その観察はガウスの補題を証明するときにも効いてくる」
テトラ「それは、どうしてでしょう？」
ミルカ「私たちはいま、ガウスの補題の $\ell$ に関心がある。 $\ell$ は $k = 1,2,\ldots,\frac{p-1}{2}$ に対して、 $$ \BAR{kn} > \frac{p-1}{2} $$ となる $\BAR{kn}$ の個数だ。それは、 $$ \HAT{kn} < 0 $$ となる $\HAT{kn}$ の個数に等しい」
テトラ「なるほどです」
僕「あれ？」
ミルカ「なに？」
僕「いや、話を中断してごめん。 《負になる数の個数》という単語に何かが引っかかっただけ。続けて」
ミルカ「ふむ。 だから、 $\HAT{kn}$ を正負で左右に分けた表を作るのが楽しい。作ってみよう」
ミルカさんはそう言うと、一枚の表を作り始めた。
テトラ「ミミミミルカさん！ これはどういう表ですか？」
ミルカ「$p = 11$ のとき、 $k = 1,2,3,4,5$ として、 絶対的最小剰余 $\HAT{kn}$ の正負に合わせて左右に振り分けた表だよ、テトラ」
テトラ「ええと……」
ミルカ「たとえば、 $n = 2$ で $k = 3$ のとき、 $$ \HAT{kn} = \HAT{3\times 2} = \HAT{6} = \MARKC{-5} < 0 $$ になっている。それを $\MARKC{\HAT{3n}}$ として表に書いた」
テトラ「ああ……左右に振り分けるという意味がわかりました。 $n$ の値ごとに $k = 1,2,3,4,5$ について $\HAT{kn}$ を計算して、
僕たちは手分けをして表を作り上げた。
$p = 11$ のとき、 $\HAT{1n},\HAT{2n},\HAT{3n},\HAT{4n},\HAT{5n}$ を正負で左右に分けた表
$$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \HAT{kn} & \MC5 & \MC4 & \MC3 & \MC2 & \MC1 & & +1 & +2 & +3 & +4 & +5 \\ \hline n=1 & & & & & & & \HH1 & \HH2 & \HH3 & \HH4 & \HH5 \\ \hline n=2 & \HN3 & & \HN4 & & \HN5 & & & \HH1 & & \HH2 & \\ \hline n=3 & \HN2 & & & \HN3 & & & \HH4 & & \HH1 & \HH5 & \\ \hline n=4 & & & \HN2 & \HN5 & & & \HH3 & & & \HH1 & \HH4 \\ \hline n=5 & & & & \HN4 & \HN2 & & & & \HH5 & \HH3 & \HH1 \\ \hline n=6 & \HN1 & \HN3 & \HN5 & & & & \HH2 & \HH4 & & & \\ \hline n=7 & \HN4 & \HN1 & & & \HN3 & & & \HH5 & \HH2 & & \\ \hline n=8 & & \HN5 & \HN1 & & \HN4 & & & \HH3 & & & \HH2 \\ \hline n=9 & & \HN2 & & \HN1 & & & \HH5 & & \HH4 & & \HH3 \\ \hline n=10 & \HN5 & \HN4 & \HN3 & \HN2 & \HN1 & & & & & & \\ \hline \end{array} $$
$x$ を $p$ で割った絶対的最小剰余を $\HAT{x}$ で表す。
ミルカ「そこでこんなふうに指を合わせてみよう」
表に指を合わせる
テトラ「これは？」
ミルカ「どの $n$ を見ても、指に割り当てられる $\HAT{kn}$ にパターンがあることがわかる」
僕「もれもないし、だぶりもない？」
ミルカ「そうだな。《もれなく、だぶりなく》だ」
テトラ「こういうことですか？ たとえば $n = 2$ を見ます。
つまり、左右の違いを無視すると、
そういうことでしょうか？」
指の割り当て（$n = 2$ の場合）
《もれなく、だぶりなく》（$n = 2$ の場合）
僕「だよね。 そしてその《もれなく、だぶりなく》は、 $n = 2$ に限らず、 $n = 1,2,3,4,5,6,7,8,9,10$ のすべてで成り立っている！」
《もれなく、だぶりなく》（$n = 5$ の場合）
ミルカさんは、 両手の指を見ながら話を始めた。
ミルカ「その《もれなく、だぶりなく》は、 集合の分割と表現することができる」
テトラ「集合の分割……集合を分けるということですか」
ミルカ「そうだ。でも、ただ分けるのではなく《もれなく、だぶりなく》分ける。 たとえば、三つの集合 $H,L,R$ を次のように定める。 $$ \begin{array}{cccccccccccccccccc} H &=& \{ & 1, & 2, & 3, & 4, & 5 & \} \\ L &=& \{ & 1, & & 3, & & 5 & \} \\ R &=& \{ & & 2, & & 4 & & \} \end{array} $$ このとき、 $$ L \cup R = H\CommaQuad L \cap R = \varnothing $$ となる。すなわち、 $L$ と $R$ の要素をすべて合わせると、 $H$ の要素がもれなく捕まえられる。 しかも、 $L$ と $R$ に属している要素にはだぶりがない。 このとき、 $L,R$ は $H$ の分割になっているという。 一般には、何個の集合に分割してもかまわない」
テトラ「《もれなく、だぶりなく》分ける、集合の分割。テトラ、理解しました」
僕「$L$ は左手の指への $-\MARKC{\HAT{kn}}$ の割り当て、 $R$ は右手の指への $\HAT{kn}$ の割り当て、 そして $1,2,3,4,5$ は親指から小指までということだね」
ミルカ「まあ、そうだ。 $p = 11$ のときはたまたま $\frac{p-1}{2} = 5$ になるから、 左手と右手に割り振ってみた。いま話した $L,R$ は $p = 11$ で $n = 2$ の場合だ。 $p$ と $n$ を使って一般的に書くなら、 $$ \begin{xalignat*}{1} H &= \SET{1,2,\ldots,\tfrac{p-1}{2}} \\ L &= \SET{-\HAT{kn}\SETM \HAT{kn} < 0, k \in H} \\ R &= \SET{\HAT{kn}\SETM \HAT{kn} > 0, k \in H} \end{xalignat*} $$ ということになる」
僕「おお、なるほど。それで一般的に書けてるね、確かに」
そこで、テトラちゃんが手を挙げた。
テトラ「ちょ、ちょっとお待ちください。 あのですね。テトラは先輩方のお話を理解していると思います。 左手右手の話も、 $H,L,R$ の話も飲み込めています……たぶん。 でも、このお話はガウスの補題につながっていくんでしょうか？ あ、 あたしには、この左手右手の話がルジャンドル記号へつながる道筋が見えていないんですが……」
僕「え？ でも、 テトラちゃんもさっき納得してたんじゃなかった？ ほら、 ガウスの補題に出てくる $\ell$ のことだよ」
テトラ「はい。 ガウスの補題の $\ell$ は、 $\BAR{kn} > \tfrac{p-1}{2}$ となる $\BAR{kn}$ の個数で、 それは $\HAT{kn} < 0$ となる $\HAT{kn}$ の個数です。それは納得しています」
僕「だから、ガウスの補題は絶対的最小剰余を使って、こう言い換えられるはず」
ガウスの補題の言い換え
$p$ を奇素数とする。
$n$ を $p$ と互いに素な整数とする。
$x$ の $p$ による絶対的最小剰余を $\HAT{x}$ で表す。 そして、 $\frac{p-1}{2}$ 個の整数 $$ \HAT{1n}\CommaQuad \HAT{2n}\CommaQuad \HAT{3n}\CommaQuad \ldots\CommaQuad \HAT{\tfrac{p-1}{2}n} $$ のうち 《$\MARKC{\text{負になる数}}$の個数》 を $\ell$ とする。 すると、 $$ \LegSym{n}{p} = (-1)^{\ell} $$ が成り立つ。
ただし、 $\tLegSym{n}{p}$ はルジャンドル記号である。
テトラ「はい……それはわかるんですが《だから、なに？》という気持ちになります。 $p=11$ として左手右手の比喩を使うなら、 《$\MARKC{\text{負になる数}}$の個数》 というのは左手の指に割り当てられた $\MARKC{\HAT{kn}}$ の個数ですよね。 集合の分割になったとしても、 左手に割り当てられる $\MARKC{\HAT{kn}}$ の個数の手掛かりなんて、 まだ何も見つかってないように、 あたしには見えるんです」
確かに、それはそうだ。僕は思った。
$\HAT{kn}$ という数は不思議なパターンを描く。 そのパターンが何かを語っているはずだ。 でもガウスの補題に出てくる $\ell$ へのヒントは見つからない。
僕はミルカさんをちらっと見る。
ミルカさんは僕を見ていた。
僕にはわかる。 この才媛は、 ヒントを言いたくてたまらないのだ。
僕「ねえ、ミ」
ミルカ「《負になる数の個数》を気にしていたな」
僕「ルカさん。え？」
ミルカさんは食い気味に僕に答えてきた。
ミルカ「君はさっき《負になる数の個数》を気にしていたな」
僕「それはそうだよ。だって《負になる数の個数》である $\ell$ がカギなんだから。 $\ell$ がわからなければ、 $(-1)^{\ell}$ もわからない。 証明したい $$ \LegSym{n}{p} = (-1)^{\ell} $$ にもつながらない」
ミルカ「たとえば $p = 11, n = 2$ なら、 $\ell$ は？」
僕「$\ell = 3$ だね」
テトラ「左手の親指、中指、小指ですから」
ミルカ「つまり、こういうことだ。 左手の指に割り当てられた $\ell = 3$ 個の $-1$ を掛け合わせれば、 $$ (-1)^{\ell} $$ が得られる」
テトラ「でも、右手の指には何の意味もありませんよ？」
ミルカ「さあね。 $1$ でも割り当てておけばいいんじゃないかな」
テトラ「？」
僕「おおおおっ！ すべて掛ければいいのか！」
僕は思わず、声を上げてしまった。
テトラ「せ、先輩？」
僕「集合の分割には意味があるね。 《もれなく、だぶりなく》に意味がある！ そうだよ、 だって、 すべてを掛け合わせればオイラーの規準に持ち込める。 $$ \LegSym{n}{p} \equiv n^{\frac{p-1}{2}} \pmod p $$ だって、指は $$ \frac{p-1}{2} $$ 種類なんだから！」
テトラ「あ、あたしにはわかりません……」
僕「まだ完全に証明にはなってないけれど、道筋はわかったと思う。 僕は、集合の分割がガウスの補題の証明に直結する理由を説明できる」
テトラ「はい」
ミルカ「聞こう」
僕の説明
$p$ を奇素数とする。 $n$ を $p$ と互いに素な整数とする。
集合 $H,L,R$ を次のように定める。 $\HAT{x}$ は $x$ の $p$ による絶対的最小剰余を表す。 $$ \begin{xalignat*}{1} H &= \SET{1,2,\ldots,\tfrac{p-1}{2}} \\ L &= \SET{-\HAT{kn}\SETM \HAT{kn} < 0, k \in H} \\ R &= \SET{\HAT{kn}\SETM \HAT{kn} > 0, k \in H} \end{xalignat*} $$
また、 $L$ の要素数を $\ell$ とする。
ここで《$L,R$ は $H$ の分割になっている》と仮定する（これはあとで証明する）。
記号 $\prod$ を用いて集合の要素を用いた積を表すことにする。 たとえば $$ \MARK{\prod_{k\in H}k} = 1\times2\times\cdots\times \tfrac{p-1}{2} $$ となる。
すると、 $$ \begin{xalignat*}{2} \MARK{\prod_{k\in H}k} &= \prod_{x\in L\cup R}\!\!x && \text{$L\cup R = H$より} \\ &= \prod_{x\in L}x \cdot \prod_{x\in R}x && \text{$L\cap R = \varnothing$より} \\ &= (-1)^{\ell}\prod_{x\in L}(-x) \cdot \prod_{x\in R}x && \text{$L$の要素数を$\ell$としたので} \\ &= (-1)^{\ell}\MARKB{\prod_{k\in H}\HAT{kn}} && \text{$L$と$R$の定義から} \\ \end{xalignat*} $$ となる（$\MARK{\heartsuit}$）
ここで $k\in H$ に対して $\HAT{kn}\equiv kn \pmod p$ であるから、 $$ \MARKB{\prod_{k\in H}\HAT{kn}} \equiv \MARKC{\prod_{k\in H}kn} \pmod p $$ である（$\MARKB{\clubsuit}$）。 さらに、 $H$ の要素数が $\frac{p-1}{2}$ なので、 $$ \MARKC{\prod_{k\in H}kn} = n^{\frac{p-1}{2}}\MARK{\prod_{k\in H} k} $$ である（$\MARKC{\spadesuit}$）。
したがって、 $\MARK{\heartsuit}$ と $\MARKB{\clubsuit}$ と $\MARKC{\spadesuit}$ を合わせて、 $$ \MARK{\prod_{k\in H}k} \equiv (-1)^{\ell}\, n^{\frac{p-1}{2}}\MARK{\prod_{k\in H}k} \pmod p $$ となる。 $\MARK{\displaystyle\prod_{k\in H}k}$ は $p$ と互いに素なので、両辺を割ることができて、 $$ 1 \equiv (-1)^\ell \, n^{\frac{p-1}{2}} \pmod p $$ すなわち、 $$ n^{\frac{p-1}{2}} \equiv (-1)^\ell \pmod p $$ が成り立つ。
したがって、オイラーの規準より、 $$ \LegSym{n}{p} \equiv (-1)^{\ell} \pmod p $$ となる。 $p\GEQ 3$ で、両辺が $1$ または $-1$ であることから、 $$ \LegSym{n}{p} = (-1)^{\ell} $$ となる。
テトラ「……」
僕「……」
僕の説明の後、テトラちゃんはずいぶん長いあいだ考えていた。そして言った。
テトラ「理解できた……と思います。 でもあたし、ミルカさんの左手右手の話がなかったら、 きっと、先輩の説明は理解できなかったと思います。 左手が $L$ で右手が $R$ で、 $L$ の要素数が $\ell$ なので、 $$ \prod_{x\in L}x = \prod_{x\in L}((-1)\cdot(-x)) = (-1)^{\ell}\prod_{x\in L}(-x) $$ これがいえるんですね。 $\ell$ 個の $-1$ をくくり出しています。 それから、集合の分割があるから、 $$ \prod_{k\in H}k = \prod_{x\in L\cup R}\!\!x = \prod_{x\in L}x \cdot \prod_{x\in R}x $$ というのも、何とかわかりました」
僕「あとは、 $L$ と $R$ が本当に」
ミルカ「本当に $H$ の分割になっていることの証明は私がやろう」
ミルカさんは、 またまた食い気味に話を続けた。
きっと、話したくてウズウズしてたんだなあ。
僕「どういう方針になるの？」
ミルカ「$L$ と $R$ がどんな集合かを考える。 $$ \begin{xalignat*}{1} H &= \SET{1,2,\ldots,\tfrac{p-1}{2}} \\ L &= \SET{-\HAT{kn}\SETM \HAT{kn} < 0, k \in H} \\ R &= \SET{\HAT{kn}\SETM \HAT{kn} > 0, k \in H} \end{xalignat*} $$ だから、 $H$ の元 $k$ に対し、 $\HAT{kn}$ の符号によって $\ABSX{\HAT{kn}}$ を $L$ と $R$ に振り分けているわけだ。 $\ABSX{\HAT{kn}}$ は $\HAT{kn}$ の絶対値」
僕「いいよ」
テトラ「そうですね」
ミルカ「ここで $H$ から $H$ への写像 $f\colon H\to H$ を $$ f(k) = \ABSX{\HAT{kn}} $$ で定義する。 $$ k\mapsto \ABSX{\HAT{kn}} $$ ということだ。 この写像 $f$ が全単射であることを示せば、 $L,R$ が $H$ の分割であることが示せる」
僕「うん？ よくわからないなあ」
ミルカ「そう？ $\HAT{kn}$ の符号によって $\ABSX{\HAT{kn}}$ を $L$ と $R$ に振り分けている。 つまり $L\cup R$ は $f$ の値域だ。だから、
僕「おお！」
テトラ「こういうことですか。
ミルカ「では証明しよう」
命題
$p$ を奇素数とする。 $n$ を $p$ と互いに素な整数とする。
集合 $H,L,R$ を次のように定める。 $\HAT{x}$ は $x$ の $p$ による絶対的最小剰余を表す。 $$ \begin{xalignat*}{1} H &= \SET{1,2,\ldots,\tfrac{p-1}{2}} \\ L &= \SET{-\HAT{kn}\SETM \HAT{kn} < 0, k \in H} \\ R &= \SET{\HAT{kn}\SETM \HAT{kn} > 0, k \in H} \end{xalignat*} $$
$H$ から $H$ への写像 $f$ を、 $$ f(k) = \ABSX{\HAT{kn}} $$ で定義したとき、写像 $f$ は全単射である。
証明
まず、 $\HAT{kn}\in \SET{-\tfrac{p-1}{2},\ldots,-1,1,\ldots,\tfrac{p-1}{2}}$ なので、 $k\in H$ のとき $f(k)\in H$ である。
（単射であることの証明）
$f(k_1)=f(k_2)$ とすると、 $\ABSX{\HAT{k_1n}}=\ABSX{\HAT{k_2n}}$ である。 $k\in H$ で $\HAT{kn}\equiv kn\pmod p$ であるから、 $\ABSX{\HAT{k_1n}}=\ABSX{\HAT{k_2n}}$ より、 $$ k_1n \equiv k_2n \pmod p \MATAWAREL k_1n \equiv -k_2n \pmod p $$ である。 $n$ は $p$ と互いに素だから、 $$ k_1 \equiv k_2 \pmod p \MATAWAREL k_1 \equiv -k_2 \pmod p $$ である。 ここで、 $k_1,k_2\in H$ から、 $0 < k_1 + k_2 < p$ ゆえに $k_1+k_2\not\equiv 0\pmod p$ なので、 $$ k_1 \equiv k_2 \pmod p $$ であり、 $k_1 = k_2$ となり $f$ は単射である。
（全射であることの証明）
$H$ が有限集合で $f$ が単射であることから、 $f$ は全射である。
したがって、 $f$ は全単射である。
（証明終わり）
ミルカ「これで $L,R$ が確かに $H$ の分割になっていることが示された」
僕「うん、これで僕の説明の《仮定》が満たされたね。 ガウスの補題が証明できた！」
ミルカ「せっかくここまで来たのだから、平方剰余の相互法則について話そう」
瑞谷先生「下校時間です」
ミルカ「！！！」
参考文献
この記事は期間限定で「ただいま無料」となっています。
ひと月500円で「読み放題プラン」へご参加いただきますと、 470本以上の記事がすべて読み放題になりますので、 ぜひ、ご参加ください。
参加済みの方／すぐに参加したい方はこちら
結城浩のメンバーシップで参加 結城浩のpixivFANBOXで参加（第479回終わり）
（2026年8月21日）
![[icon]](https://img.hyuki.net/20220619121014-abd58cfc2ab436f4.png)