第478回 シーズン48 エピソード8

オイラーの規準（後編） ただいま無料

登場人物紹介

僕：数学が好きな高校生。

テトラちゃん：僕の後輩。 好奇心旺盛で根気強い《元気少女》。言葉が大好き。

ミルカさん：数学が好きな高校生。 僕のクラスメート。メタルフレームの眼鏡に長い黒髪の《饒舌才媛》。

ここは高校の図書室。いまは放課後。

テトラちゃんと僕は、 ミルカさんのヒントを受けてオイラーの規準の証明に挑戦していた。

オイラーの規準

$p$ を奇素数とする。

$n$ を $p$ と互いに素な整数とする。このとき、 $$ \LegSym{n}{p} \equiv n^{\frac{p-1}{2}} \pmod p $$ が成り立つ。

ただし、 $\tLegSym{n}{p}$ はルジャンドル記号とする（第477回参照）。

オイラーの規準の証明、その前半はすでに証明できた。 $n$が$\TextYES$ならば $$ n^{\frac{p-1}{2}} \equiv \LegYES\pmod p $$ が証明できたのだ（第477回参照）。

後半は、$n$が$\TextNO$ならば $$ n^{\frac{p-1}{2}} \equiv \LegNO\pmod p $$ であることの証明だ。 僕たちは、証明完了の直前まではたどりついた（第477回参照）。

でも……

オイラーの規準の証明（後半）（$\TextNO$ならば$\LegNO$と合同）

$p$ を奇素数とする。

$n$ を $p$ と互いに素な整数とする。

$m = 1,2,3,\ldots,p-1$ に対して、 $$ n \equiv mm^* \pmod p $$ となる $m^* = 1,2,3,\ldots,p - 1$ が $m$ ごとに唯一存在し、 さらに、 $(m^*)^* = m$ となる。

$n$が$p$を法として$\TextNO$のとき、 どの $m$ に対しても、 $m \NEQ m^*$ となる。

したがって、 $1,2,3,\ldots,p-1$ は、 $m$ と $m^*$ からなる $\frac{p-1}{2}$ 組のペアに分けられることになる。 各ペアの積は $n$ に合同であり、 そのペアが $\frac{p-1}{2}$ 組あるのだから、

$$ n^{\frac{p-1}{2}} \equiv (p-1)! \pmod p $$ となる。

ここで……あれ？

テトラちゃんがミルカさんを止める。

オイラーの規準の証明（後半）（$\TextNO$ならば$\LegNO$と合同）

$p$ を奇素数とする。

$n$ を $p$ と互いに素な整数とする。

$m = 1,2,3,\ldots,p-1$ に対して、 $$ n \equiv mm^* \pmod p $$ となる $m^* = 1,2,3,\ldots,p - 1$ が $m$ ごとに唯一存在し、 さらに、 $(m^*)^* = m$ となる。

$n$が$p$を法として$\TextNO$のとき、 どの $m$ に対しても、 $m \NEQ m^*$ となる。

したがって、 $1,2,3,\ldots,p-1$ は、 $m$ と $m^*$ からなる $\frac{p-1}{2}$ 組のペアに分けられることになる。 各ペアの積は $n$ に合同であり、 そのペアが $\frac{p-1}{2}$ 組あるのだから、

$$ n^{\frac{p-1}{2}} \equiv (p-1)! \pmod p $$ となる。

ここでウィルソンの定理より、 $(p-1)!\equiv-1\pmod p$ なので、 $$ n^{\frac{p-1}{2}} \equiv \LegNO \pmod p $$ が成り立つ。

（証明終わり）

ウィルソンの定理

$p$ が素数のとき、 $$ (p-1)! \equiv -1 \pmod p $$ が成り立つ。

テトラちゃんは、 みるみるうちに $p = 3,5,7$ についてウィルソンの定理を確かめていった。

$p = 3$ のとき、ウィルソンの定理を確かめる

まず、 $p = 3$ のとき、 $$ (p - 1)! = (3 - 1)! = 2! = 2 $$ です。 $2 - (-1) = 3$ で、もちろん $3$ は $3$ の倍数ですから、 $2 \equiv -1 \pmod 3$ となり、 $$ (3 - 1)! \equiv -1 \pmod 3 $$ です。 つまり、 $p = 3$ のとき $$ (p - 1)! \equiv -1 \pmod p $$ は成り立ちます。

$p = 5$ のとき、ウィルソンの定理を確かめる

$p = 5$ のとき、 $$ (p - 1)! = (5 - 1)! = 4! = 1\times2\times3\times4 = 24 $$ です。 $24 - (-1) = 25$ で、 $5$ の倍数ですから、 $24 \equiv -1 \pmod 5$ となります。 つまり、 $p = 5$ のとき $$ (p - 1)! \equiv -1 \pmod p $$ は成り立ちます。

$p = 7$ のとき、ウィルソンの定理を確かめる

$p = 7$ のとき、 $$ (p - 1)! = (7 - 1)! = 6! = 1\times2\times3\times4\times5\times6 = 720 $$ です。 $720 - (-1) = 721 = 7\times103$ で、 $7$ の倍数ですから、 $720 \equiv -1 \pmod 7$ となります。 つまり、 $p = 7$ のとき $$ (p - 1)! \equiv -1 \pmod p $$ は成り立ちます。

問題（ウィルソンの定理の証明）

$p$ が素数のとき、 $$ (p-1)! \equiv -1 \pmod p $$ が成り立つことを証明せよ。

そこでテトラちゃんは両手を頭に乗せて困った顔になる。

コダックの真似をしているわけではない。

$m$ と $m^{-1}$ の表

$$ \begin{array}{|c|cccccc|} \hline m & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline m^{-1} & 1 & 4 & 5 & 2 & 3 & 6 \\ \hline \end{array} $$ $$ mm^{-1} \equiv 1 \pmod p $$

$m = 1,2,3,4,5,6$ で $m$ と $m^{-1}$ とを結ぶ

解答（ウィルソンの定理の証明）

$p$ を素数とする。

$p = 2$ の場合は、 $(2-1)!\equiv -1\pmod 2$ より確かに成り立つ。

$p = 3$ の場合は、 $(3-1)!\equiv -1\pmod 3$ より確かに成り立つ。

以下では $p > 3$ とする。

$p$ が素数であることから、 $m = 1,2,3,\ldots,p-1$ に対して、 $$ mm^{-1}\equiv 1 \pmod p $$ となる $m^{-1} = 1,2,3,\ldots,p - 1$ が $m$ ごとに唯一存在し、 $(m^{-1})^{-1} = m$ となる。

また、 $m = m^{-1}$ になるのは $m^2\equiv1\pmod p$ のときで、 $m^2 - 1 = (m-1)(m+1)$ が $p$ の倍数になるのは、 $p$ が素数であることにより、 $m = 1$ および $m = p-1$ の場合だけである。

したがって、 $2,3,\ldots,p-2$ は、 積が $1$ に合同になる $\frac{p-1}{2}-1$ 組のペアに分けられる。 よって、 $$ 1\times\underbrace{2\times3\times\cdots\times(p-2)}_{\text{$1$に合同}}\times(p-1) \equiv p-1 \pmod p $$ となる。 $p-1\equiv -1\pmod p$ より、 $$ (p-1)!\equiv -1\pmod p $$ が成り立つ。

（証明終わり）

そこで、 ミルカさんが急に席を立ち、声を上げた。

ガウスの補題

$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$ は奇素数。つまり、 $p$ は $2$ 以外の素数だ。
• $n$ は $p$ と互いに素。つまり、 $n$ は $p$ の倍数ではない整数だ。
• $x$ を $p$ で割った余りを $\BAR{x}$ で表す。つまり $\BAR{x}$ は $0,1,2,\ldots,p - 1$ であり、 $x - \BAR{x}$ は $p$ の倍数だ。
• そして $\ell$ は……

テトラちゃんは、基本にどこまでも忠実なのだ。

僕たちは夢中になって $p = 7$ でガウスの補題を確かめた。 $n = 1,2,3,4,5,6$ で考えるのだ。

$p = 7$ でガウスの補題を考える

$$ \begin{array}{|c|ccc|c|c|c|} \hline n & \BAR{1n} & \BAR{2n} & \BAR{3n} & \ell & (-1)^\ell & \tLegSym{n}{p} \\ \hline 1 & 1 & 2 & 3 & 0 & \LegYES & \LegYES \\ \hline 2 & 2 & \MARKC4 & \MARKC6 & 2 & \LegYES & \LegYES \\ \hline 3 & 3 & \MARKC6 & 2 & 1 & \LegNO & \LegNO \\ \hline 4 & \MARKC4 & 1 & \MARKC5 & 2 & \LegYES & \LegYES \\ \hline 5 & \MARKC5 & 3 & 1 & 1 & \LegNO & \LegNO \\ \hline 6 & \MARKC6 & \MARKC5 & \MARKC4 & 3 & \LegNO & \LegNO \\ \hline \end{array} $$

$\MARKC{\text{緑色の数}}$は$\frac{p-1}{2} = 3$より大きい数を表す。

$\MARKC{\text{緑色の数}}$の個数が$\ell$である。

僕とテトラちゃんは、さっと彼女を見る。

ミルカさんは、自分の手を見つめている。

ミルカさんは、両手の指を合わせて胸の前に小さな《鳥かご》を作っていた。

親指は親指に、 人差し指は人差し指に、 ……そして、小指は小指に合わせ、 ふくらませた形だ。

僕は、これを知ってる。 全単射の鳥かごだ（『数学ガール／ゲーデルの不完全性定理』参照）。

テトラちゃんと僕は、 大きな疑問符を心に抱きながら、 $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$である。