第477回 シーズン48 エピソード7

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

図書館にて

テトラ「判別式ができましたね！　しかも、 《実数の世界》と《$p$ を法とする世界》は、 判別式の形がそっくりです！」

ミルカ「ふむ」

僕「……」

テトラ「すごいですっ！　すごいですっ！　《実数の世界》では $$ b^2-4ac\GEQ0 $$ で実数解の存在がわかって、 《$p$ を法とする世界》ではルジャンドル記号を使えば $$ \LegSym{b^2-4ac}{p}\GEQ0 $$ で整数解の存在がわかるなんて！　こんなに素敵な関係があるんですね！」

僕「うーん……」

テトラ「あれ？　先輩は、どうしてうなってらっしゃるんですか？」

僕「その二つの式はずいぶん違うような気がするんだ」

テトラ「そんなことありませんよ。どちらも $b^2-4ac$ という同じ形の式で表されています。 もちろん《$p$ を法とする世界》では $p$ が出てきますけど、 それは表記だけの問題ですよね？」

僕「そうなんだろうか……うーん」

ミルカ「うなってないで、テトラに伝わるように言語化する」

僕「つまりね、 $b^2 - 4ac$ はいいんだよ。与えられた係数 $a,b,c$ から計算できるから。 $b$ を $2$ 乗して、 $4ac$ を引く。何も難しくない。 問題はこのルジャンドル記号の方」

テトラ「え？　でもミルカさんが定義をちゃんと書いてくださいましたよ。 与えられた整数が《$p$ を法とする平方剰余》かどうかを判定する記号ですよね？　 いわば《$p$ を法とする世界》における平方数判定装置です」

僕「うん。定義ははっきりしている。 でも、ねえ、テトラちゃん。 $p$ と $a,b,c$ が与えられたとき、 テトラちゃんはどうやって $$ \LegSym{b^2-4ac}{p} $$ の値を求めるの？」

テトラ「どうやってと言われましても……根気よく調べれば、 すぐ求められますよね。 $b^2 - 4ac$ を計算すると整数が得られます。 あとは、 $$ m = 1,2,3,\ldots,p-1 $$ を順番に使って $m^2$ を計算して、 $$ b^2 - 4ac \equiv m^2 \pmod p $$ になるかどうかを調べるだけです。 具体的には《$b^2 - 4ac$ を $p$ で割った余り》と《$m^2$ を $p$ で割った余り》が等しくなるような $m$ を探すだけです。

• そういう$m$が見つかれば、$b^2 - 4ac$は$p$を法とする$\TextYES$です。
• そういう$m$が見つからなければ、$b^2 - 4ac$は$p$を法とする$\TextNO$です。

僕「うん、それはそう。 確かに実際に計算できる。 でも、それは$p$が大きいときには現実的じゃないよね？　$\TextYES$なら途中で$m$が見つかるからまだいいけど、 でも、$\TextNO$だったら$m = 1,2,3,\ldots,p-1$をすべて試さなくちゃわからない」

テトラ「あ……でも、根気よくやれば！」

僕「それに、そこまで根気よく試すのなら、 最初から $x = 0,1,2,3,\ldots,p-1$ を使って $$ ax^2 + bx + c \equiv 0 \pmod p $$ が成り立つかどうか試すのと、 変わりないような気もする。 変わりないというのは言い過ぎだけど、 根気よく試してようやく求まるのを判別式と呼ぶのは引っかかるんだ」

テトラ「なるほどです……」

僕「テトラちゃんはさっき、 $$ x^2 + x + 1\equiv 0 \pmod 7 $$ に整数解があるかどうかを調べるときに、 $x = 0,1,2,3,4,5,6$ を根気よく代入していたよね。 あのときも、 それが気になっていたんだ。 《$p$ を法とする世界》だから、根気よく代入して試せるけど、 これでいいのかなって（第476回参照）」

テトラ「確かに《$7$ を法とする世界》なら、 $7$ 回代入すればすべて試せますが、 $p$ が大きいときはすごいことになっちゃいますね……」

僕「ねえミルカさん、言いたいことがあったら言っていいよ」

ミルカ「オイラー先生の話をしよう。 いわゆるオイラーの規準（クライテリオン）の話だ」

オイラーの規準

僕「クライテリオン？　クライテリアじゃなく？」

テトラ「criterion（クライテリオン）はcriteria（クライテリア）の単数形ですね」

僕「あ、そうか」

ミルカ「日本語ではオイラーの規準（きじゅん）や、 オイラーの判定法などという。 もっとも、オイラー先生自身がそう呼んでいるわけではない。 これは、18世紀にオイラー先生が書いた論文に書かれている定理だ。 この定理を使えば、平方剰余が比較的楽に計算できる」

テトラ「え？　どういうことでしょうか？」

僕「え？　こんなの、本当に成り立つの？」

ミルカ「ルジャンドル記号 $\LegSym{n}{p}$ の値が $\LegYES$ か $\LegNO$ かは、 $n$が$p$を法として$\TextYES$か$\TextNO$かに対応している。 その値は実は $$ n^{\frac{p-1}{2}} $$ に合同だという。 それがオイラーの規準だ」

僕「おもしろい！」

テトラ「そんなことがいえるんですか！」

ミルカ「私たちが最初に確かめることは決まっている」

テトラ「《小さな $n$ で確かめる》んですね！　テトラ、すぐにやります！　まず、 $p = 7$ で $n = 1$ としたとき……」

$p = 7, n = 1$ でオイラーの規準を確かめる

テトラ「奇素数 $p = 7$ で $n = 1$ でオイラーの規準を確かめてみます。 まず、 $n = 1$ は $7$ を法として平方剰余です。 $1^2 = 1$ なので当然です」

僕「さっき、表も作ったよね（第476回参照）」

テトラ「はい。ですから、 $p = 7, n = 1$ のとき、 $$ \LegSym{n}{p} = \LegSym{1}{7} = \LegYES $$ が成り立ちます。一方、 $$ n^{\frac{p-1}{2}} = 1^\frac{7-1}{2} = 1^3 = \LegYES $$ になりますから、確かに $p = 7, n = 1$ のとき、 $$ \LegSym{n}{p} \equiv n^{\frac{p-1}{2}} \pmod p $$ は成り立ちますね」

$p = 7, n = 2$ でオイラーの規準を確かめる

僕「$p = 7, n = 2$ のときは、 $$ \LegSym{n}{p} = \LegSym{2}{7} = \LegYES $$ になって、 $$ n^{\frac{p-1}{2}} = 2^\frac{7-1}{2} = 2^3 = 8 \equiv \LegYES \pmod 7 $$ となる。うん、 $p = 7, n = 2$ のときも、ちゃんと $$ \LegSym{n}{p} \equiv n^{\frac{p-1}{2}} \pmod p $$ は成り立ってる。すごいなあ」

$p = 7, n = 3$ でオイラーの規準を確かめる

ミルカ「$\TextNO$の場合も確かめよう」

テトラ「はい。$n = 3$は$p = 7$を法として$\TextNO$です。 $2$ 乗して $3$ と合同になる整数は存在しないということです。 ですから、 $p = 7, n = 3$ のとき、 $$ \LegSym{n}{p} = \LegSym{3}{7} = \LegNO $$ です。一方、 $$ n^{\frac{p-1}{2}} = 3^\frac{7-1}{2} = 3^3 = 27 \equiv \LegNO \pmod 7 $$ になります。 $7$ の倍数を考えると、 $7\times 4 = 28$ ですから、 $27$ はあと一歩で $7$ の倍数。つまり $\LegNO$ に合同です。 ということは、 $p = 7, n = 3$ のとき、 $$ \LegSym{n}{p} \equiv n^{\frac{p-1}{2}} \pmod p $$ になっていますね。 $\TextNO$のとき両辺とも$\LegNO$に合同ということです」

証明の前に

僕「それにしても、驚きだなあ」

ミルカ「君は、その驚きを言語化する」

僕「その言い回し、気に入ってるの？」

ミルカ「いいから」

僕「$n$ が $\TextYES$か$\TextNO$かは、 テトラちゃんがさっき言ってたように、 $m = 1,2,3,4,5,6$ を使って $n \equiv m^2 \pmod 7$ になるかどうかをぜんぶ調べればわかる。 もちろん、それはそう。 でもそんなことをしなくても $\HAT{n^{3}}$ を計算すれば一発でわかるなんて、 それはやっぱり驚きだよ。

• $\HAT{n^{3}} = \LegYES$なら$n$は$7$を法として$\TextYES$。
• $\HAT{n^{3}} = \LegNO$なら$n$は$7$を法として$\TextNO$。

ミルカ「ふうん……」

テトラ「あの……あのですね。すごく恥ずかしい話なんですが、 あたしが毎回考えてしまうこと話してもいいですか。 あのですね、あたしは $$ n^{\frac{p-1}{2}} $$ を見ると、 $n$ の $\frac{p-1}{2}$ なんて計算して、整数になるの？　とぎょっとします。 分数乗なんて！　と一瞬だけ思ってしまうんです。 でも $p$ は奇素数ですから、 $p-1$ は必ず偶数。 ですから、 $\frac{p-1}{2}$ は必ず整数になるんですよね……たとえば、 $p = 7$ なら、 $p - 1 = 6$ で偶数で、 $\frac{p-1}{2} = 3$ で整数です。 はいっ！　お馬鹿なテトラのお馬鹿な話でしたっ！」

僕「テトラちゃんは馬鹿じゃないよ」

ミルカ「馬鹿な話でもないな。

• $p - 1$ の半分は $\frac{p-1}{2}$ だし、
• $\frac{p-1}{2}$ の $2$ 倍は $p-1$ だ。

テトラ「？」

僕「？」

テトラ「それはそうですね。 $\frac{p-1}{2}$ を $2$ 倍すると、 $p - 1$ になります」

僕「うわ！！　そうか。 $\HAT{n^3}$ が必ず $\LegYES$ か $\LegNO$ になることは、 すぐに証明できるんだね！」

オイラーの規準の証明（前半）

ミルカ「そうだな。君がいま頭の中で証明したことはこれだろう」

テトラ「頭の中で……証明？」

僕「うん、そうだよ。ミルカさんの一言で気づいた。 これはフェルマーの小定理からすぐに証明できる」

テトラ「あ、そういえばオイラーの規準の式とそっくりです！」

僕「そうだね。 $2$ 乗すればいいんだ」

テトラ「オイラーの規準は、 フェルマーの小定理のハーフバージョンだったんですね！　フェルマーの小定理でそのまま証明できました！」

ミルカ「いや、オイラーの規準の証明はまだだ」

テトラ「え？」

僕「いまのは、 $$ n^{\frac{p-1}{2}} $$ が $\LegYES$ または $\LegNO$ に合同になるといっただけで、 平方剰余との関係はまだ何もいってないからね」

テトラ「あ……確かに」

僕「でも、すぐに証明できそうだよ」

ミルカ「そう？」

僕「うん、できるできる。 まず、$n$が$p$を法として$\TextYES$だとする。すると……」

テトラ「なるほどです。$\TextYES$ならば$\LegYES$の証明ができました！」

僕「ほらね」

ミルカ「オイラーの規準の証明、その前半だな」

僕「うん、そうだよ。 いまのは$\TextYES$のときに$n^{\frac{p-1}{2}}$が$\LegYES$に合同になる証明。 残りの半分は$\TextNO$のときに$\LegNO$に合同になる証明」

テトラ「なるほど。両方いう必要があるのですね」

ミルカ「そしてそちらは少しやっかいだ」

僕「確かに、難しいな……」

ミルカ「では、証明しよう」

テトラ「お待ちください」

ミルカ「うん？」

テトラ「オイラーの規準、後半の証明は知りたいんですが、 もうちょっと考えたいです。何かヒントがほしいです！」

ミルカさんのヒント

ミルカ「私たちはいま、 $n$ に対して $$ n \equiv m^2 \pmod p $$ すなわち $$ n \equiv mm \pmod p $$ を満たす $m$ の存在に関心がある」

僕「……」

テトラ「……」

ミルカ「$m^2$ すなわち $mm$ の部分を少し変えて、 $m$ と $m^*$ の積にする。 $$ n \equiv mm^* \pmod p $$ を満たす $m$ と $m^*$ というペアの存在に関心を向けよう」

テトラ「ミルカさん？　そのような $m$ と $m^*$ のペアは、 どんな $n$ に対しても存在しますよね？　だって、 $m=1$ として $m^*=n$ とすれば、 $mm^* = 1n = n$ ですから、いつだって、 $$ n \equiv mm^* \pmod p $$ が成り立ちます」

僕「もっといえるよ。 $m = 1,2,\ldots,p-1$ のどれを選んでも、積が $n$ と合同な $m$ と $m^*$ のペアが作れる。 だって、 $m$ は $p$ と互いに素なんだから、 $$ mm^{-1} \equiv 1 \pmod p $$ という $m^{-1}$ が存在するよね。 ということは、 $$ m^* = m^{-1}n $$ とおけば、 $$ mm^* = mm^{-1}n \equiv n \pmod p $$ になる。つまり $m = 1,2,\ldots,p-1$ のどれを選んでも $$ n \equiv mm^* \pmod p $$ にできる」

テトラ「えっえっ？」

ミルカ「空中戦にならないように、 $p = 7$ で $m = 1,2,3,4,5,6$ に対して、 $m^{-1}$ の表を作ろう」

テトラ「あっ、はい。 $m$ に掛けると $1$ と合同になるのが $m^{-1}$ ですね？」

ミルカ「そう。《$p$ を法とする世界の逆数》だ」

テトラ「はい、できました。検算もしました」

ミルカ「この表を使って、 $n = 1,2,3$ として $n \equiv mm^* \pmod 7$ となる $m$ と $m^*$ の表を作ろう」

テトラ「ところどころ、$\GREENTEXT{緑色の数}$がありますね。 $m = m^*$ になるところです」

僕「なるほど。表の中に$\GREENTEXT{緑色の数}$が出てくるときの$n$は$\TextYES$になるわけだ。 だって $m = m^*$ だったら、 $n \equiv m^2$ となるわけだから」

ミルカ「オイラーの規準、その後半は$\TextNO$の場合だ。それを証明するために、 $\GREENTEXT{緑色の数}$が出てこない表に注目する」

僕「うーん……」

テトラ「何かわかるんでしょうか？」

ミルカ「$\TextNO$の場合には、 $m \not\equiv m^*$ になるから、 ペアは必ず $\frac{p-1}{2}$ 組できる ことになる」

僕「なるほど。 $p = 7$ で $n = 3$ なら、こういうことだね」

テトラ「$1$ のパートナーは $3$ で、 $2$ のパートナーは $5$ で、 $3$ のパートナーは $1$ という $3$ 組ができる？」

僕「これ、 $1$ から $p-1$ までぜんぶ掛けたら（・・・・・・・） $$ n^{\frac{p-1}{2}} $$ に合同になるよね！　 $1$ 組のペア $mm^*$ が $n$ に合同で、 そういうペアが $\frac{p-1}{2}$ 組あるんだから！」

ミルカ「その通り。そして、それは、 $$ 1\times 2 \times 3\times \cdots \times (p-1) = (p-1)! $$ に合同だ」

僕「わかった！　 これで後半が証明できる！」

参考文献

• Leonhard Euler, Theoremata circa divisores numerorum (Theorems on divisors of numbers), E134
• Leonhard Euler, Theoremata circa residua ex divisione potestatum relicta (Theorems about the remainders left by division by powers), E262
• 雪江明彦『整数論1　初等整数論から $p$ 進数へ』
• 高木貞治『初等整数論講義 第2版』
• 結城浩『数学ガール／フェルマーの最終定理』