第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$ になることは、 すぐに証明できるんだね！」

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

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