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

オイラーの規準（後編）

図書館にて

僕「あれ？　ちょっと待って。 $\LegNO$ にならないぞ？　僕たちは、 $$ n^{\frac{p-1}{2}} \equiv (p-1)! \pmod p $$ にたどり着いた。 でも、僕たちのゴールは、 $$ n^{\frac{p-1}{2}} \equiv \LegNO \pmod p $$ だよね？」

テトラ「そうですよね」

ミルカ「あと一歩だ。ここでウィルソンの定理を使えば済む。 つまり」

テトラ「ちょ、ちょっと待ってください！」

ミルカ「うん？」

テトラ「証明のゴールまであと一歩。 ということは、いまミルカさんがおっしゃろうとしているのは、 こういうことでしょうか。 $$ (p-1)! \equiv \LegNO \pmod p $$ が成り立つ？」

ミルカ「テトラ、その通りだ。 その命題はウィルソンの定理と呼ばれている。 MacTutorによれば、 証明をしたのはラグランジュ とのことだ。 これでオイラーの規準の証明が終わった」

僕「うーん……最後の一歩で、 定理がどこからか降ってきて解決というのは、 ちょっと……何て言ったらいいか……」

テトラ「ストレスフル？」

ミルカ「欲求不満？」

僕「まあ、そんなところ」

ミルカ「だったら、ウィルソンの定理を証明すればいい」

テトラ「証明？」

ウィルソンの定理を証明する

ミルカ「あらためてウィルソンの定理を述べるとこうなる」

僕「主張自体はシンプルで綺麗だね。証明か……」

テトラ「あ、あの……もしかして、 あたしにもこのウィルソンの定理は証明できますか？」

ミルカ「いまのテトラなら、証明できてもおかしくはない」

テトラ「わかりました。 では、いつも通りに《具体例で確かめる》ところから始めます！　 まず、 $p = 2$ のときですね。 $p = 2$ なら $$ (p - 1)! = (2 - 1)! = 1! = 1 $$ です。 $2$ を法として、 $1$ と $-1$ は……ええと……はい、合同です。 なので、確かに $p = 2$ のとき、 $$ (p-1)! \equiv -1 \pmod p $$ は成り立ちます」

ミルカ「テトラは、 $1\equiv -1 \pmod 2$ はなぜ成り立つかを一言でいう」

テトラ「はい。 $a \equiv b \pmod m$ というのは、 $a - b \equiv 0 \pmod m$ ということで、 つまり $a - b$ が $m$ の倍数ということです。 ここで $1 - (-1) = 2$ で、もちろん $2$ は $2$ の倍数です。 ですから、 $$ 1 \equiv -1 \pmod 2 $$ です。はい、あたし、だいぶ合同の計算に慣れてきたみたいです！」

僕「いま、テトラちゃんの計算を見ていて気づいたんだけど、 $$ p - 1\equiv -1\pmod p $$ はいつも成り立つよね。 だって、 $$ (p-1) - (-1) = p $$ だから、 $(p-1) - (-1)$ は $p$ の倍数だ」

テトラ「そうですね。《$p$ を法とする世界》で、 $p$ は $0$ に合同ですし、 $p-1$ は $-1$ に合同です」

僕「ということは、ウィルソンの定理を証明する代わりに、 $$ (p-1)! \equiv p-1 \pmod p $$ を証明してもいいわけだね」

テトラ「それはそうですが……あまり違いがないような」

僕「そんなことないよ。だって $p-1$ は $p$ と互いに素だから、 $p-1$ で割って、 $$ (p-2)! \equiv 1 \pmod p $$ を証明すればいいことになる。もっといえば、 $$ 2\times3\times\cdots\times(p-3)\times(p-2) \equiv 1 \pmod p $$ を証明すればいい」

テトラ「それで話は簡単になっているんでしょうか」

僕「なっているよ。うん、これで証明までいけそうだ」

テトラ「ええ……？」

ミルカ「ヒントがだいぶ多いな」

僕「うん、僕はわかったと思う。証明を書き下ろせる準備までできた」

テトラ「あたしは……わかりません。 $p-1$ が $-1$ に合同であるということも、 $(p-2)!$ が $1$ に合同であることを示せばいいこともわかります。 でも、そういうヒントをいただいても、 ウィルソンの定理を証明するとなると……さっぱりです」

僕「オイラーの規準を証明するとき、 ミルカさんからもらったヒントがあった。 それも重要だね」

テトラ「ミルカさんからいただいたヒントというのは、 $$ n \equiv mm^* \pmod p $$ を満たす $m$ と $m^*$ というペアの存在を意識することでした（第477回参照）」

ミルカ「対合（ついごう）」

テトラ「ついごう？」

ミルカ「対合（たいごう）というときもある。 $f\circ f$ が恒等写像になる全単射 $f$ を一般に対合という」

僕「あ、名前があるんだ」

テトラ「す、すみません。具体的には？」

ミルカ「$P = \SET{1,2,\ldots,p-1}$ とおく。 $n$ を $P$ の要素として、 $$ n\equiv mm^*\pmod p $$ となるペア $m$ と $m^*$ を考える」

テトラ「はい、それはわかります」

ミルカ「そのときの ${}^*$ を《$m$ から $m^*$ を得る写像》と考えると、 写像 ${}^*$ は対合になる。なぜなら写像 ${}^*$ は $P$ から $P$ への全単射で、 しかも ${}^*{}^*$ は恒等写像になるからだ」

僕「二回繰り返すと元に戻るということだね。 $(m^*)^* = m$ だから」

テトラ「あたしは、まだ話が飲み込めていないようです。 対合のお話も理解しているんですが、ウィルソンの定理にどうつながるか、 まださっぱりわかりません」

僕「僕が考えたこと、話してもいい？」

テトラ「はい……」

僕「僕は $mm^* \equiv n \pmod p$ の特別な場合として、 $mm^* \equiv 1 \pmod p$ を考えた。 このときは、 $m^*$ のことを $m^{-1}$ と書いた方がピンとくるね」

テトラ「あ、はい。 それについては表も作りましたよね。 《$p$ を法とする世界の逆数》です。 この表で縦の列に並んだ二つの数を掛け合わせれば $1$ に合同になります（第477回参照）」

僕「そこでね、 $$ 1,2,3,4,5,6 $$ と数を並べて、自分の逆数となるパートナーと手を結ぶ。 すると、こうなるよね」

テトラ「はい、わかります。 $1$ は自分自身と、 $2$ は $4$ と、 $3$ は $5$ と、 $6$ は自分自身と手を結びます。 手を結んだパートナーと掛け合わせれば $1$ と合同になります……えっ？　あっ、あっ、あっ！」

僕「もうわかったよね」

ミルカ「テトラのアハ体験だな」

テトラ「わかりました！　 $1,2,3,4,5,6$ を掛け合わせるときに、 ペアをまとめるんですね。 $$ 1\times2\times3\times4\times5\times6 = 1 \times \underbrace{2\times4}_{\text{ペア}} \times \underbrace{3\times5}_{\text{ペア}} \times 6 $$ となって、ペアの積は $1$ と合同ですから、 $$ 1\times2\times3\times4\times5\times6 \equiv 6 \pmod 7 $$ になります。 $6 \equiv -1 \pmod 7$ ですから、結局 $$ 1\times2\times3\times4\times5\times6 \equiv -1 \pmod 7 $$ です。これは $p = 7$ のとき $$ (p-1)! \equiv -1 \pmod 7 $$ になってますね！」

ミルカ「それでいい」

僕「これでウィルソンの定理が証明できる！　すっきりだ！」

テトラ「証明、できましたね……」

僕「できたね！」

テトラ「《$p$ を法とする世界》には不思議なおもしろさがありますね。 $p-1$ が $-1$ に見立てられるところもおもしろいですし……」

ミルカ「ではここで、さらにおもしろい命題を考えよう」

テトラ「何ですか？」

ミルカ「数論におけるガウスの補題と呼ばれているものだ」

僕「ガウスの補題……」