第473回 シーズン48 エピソード3

フェルマーの小定理（前編） ただいま無料

図書室

僕「テトラちゃん？」

テトラ「あっ……先輩！　いらしてたんですね」

僕「いま来たところ。 それは……村木先生からの《カード》かな？」

テトラ「はい、そうです」

僕「どんな謎？　思わせぶりなパズルかな？」

テトラ「パズルというわけではありませんね……今回は数学の問題。 ギミックなしですっ！」

僕「これはフェルマーの小定理だよね？」

テトラ「はい、そうです」

僕「でも、フェルマーの小定理なら、以前いっしょに証明したことなかったっけ？」

テトラ「ありました。それはよくわかっています。 あのときは数学的帰納法と二項定理を使って証明しました（第399回参照）」

僕「そうだったね」

テトラ「でも、あたしはこの機会に、 あれとは別の証明を見つけることができないかと考えています」

僕「おお、それはすごい！」

テトラ「あたしは、 このフェルマーの小定理はいったい何を言ってるのか、 もっと深く知りたいと思ったからです。 あたしが思い描いているイメージにぴったりくる証明は考えられないか……と思いました」

僕「すごいなあ。 テトラちゃんが思い描いているフェルマーの小定理のイメージって、どういうもの？」

テトラ「い、いえっ、そんなに大した話ではありません。 あたしは、ただ、 あたしが感じている不思議ポイントを解消したいというだけなんです……」

僕「テトラちゃんが感じているフェルマーの小定理の不思議ポイント、教えてよ」

テトラ「は、はい……では、 あたしが考えていた道すじに沿ってお話ししてもいいでしょうか？」

僕「もちろん！」

小さな数で考える

テトラ「で、ではお話しします。 まず、この《カード》を見たとき、いつもながらあたしはドキドキしました。 難しそうに見えるからです。『これは知ってる。《フェルマーの小定理》だ。証明もしたことある』 と思ってもダメです。やっぱりドキドキします」

僕「まあ、確かにね。 でも（・・）、 あたしは（・・・・）」

テトラ「でも、あたしは……先輩、あたしのセリフを予測するのやめてくださいね」

僕「ごめんごめん」

テトラ「でも、 あたしは《小さな数で確かめる》ことをすれば落ち着くことを知っています。 具体的な数で根気よくやってみれば、 見かけの難しさはちゃんと消えてくれるんです。 その代わり、本当に難しいところが現れてくるんですけれど……」

僕「なるほどね。ともかくテトラちゃんは具体的に試してみた？」

テトラ「はい。《フェルマーの小定理》に書かれている言葉をそのままなぞりながら進みます。 『$p$ は素数』 というのですから、 $$ p = 2,3,5,7,11,\ldots $$ のどれかを選んで試すことができます。たとえば、 $$ p = 7 $$ として試すことにします」

僕「うん」

テトラ「それから、 『$n$ は $p$ と互いに素な整数』 というのですから、 『$n$ と $p$ の最大公約数は $1$』 ということになります。 それが《$n$ と $p$ は互いに素》という意味ですから。 $n$ と $p$ の最大公約数を $\GCD{n}{p}$ と書くことにすると、 $n$ と $p$ が互いに素というのは、 $$ \GCD{n}{p} = 1 $$ と書けます。 いま $p = 7$ として考えているので、 $$ \GCD{n}{7} = 1 $$ という $n$ を何か選ぶことにします。 たとえば、 $$ n = 2 $$ を選ぶことにしました」

僕「テトラちゃん、さくさく進むね」

テトラ「このあたりはいつも通る道ですからっ！　出てきた言葉の定義を確認して、 その具体例を作って試してみる。具体例を作ることで、 自分がその言葉の定義をちゃんと理解していることを試す。 まさに《定義は理解の試金石》ですっ！」

僕「確かに！」

テトラ「そして《フェルマーの小定理》の式がこれです。 $$ n^{p-1}\equiv 1\pmod p $$ これを $p = 7$ で $n = 2$ として書くなら、 $$ 2^{7-1}\equiv 1\pmod 7 $$ となって、文字が消えました。 こうなれば、こわくありません。 具体的に計算すれば、成り立つかどうか確かめられますから。 まず $2^{7-1}$ を計算すると、 $$ 2^{7-1} = 2^6 = 64 $$ になります。 そして $\pmod 7$ ですから、 あたしたちは《$7$ を法とする世界》で考えています。 $$ 64 \div 7 = 9\,\text{余り}\,1 $$ ですから、 $64$ を $7$ で割った余りは $1$ です。 したがって、確かに、 $$ 2^{7-1}\equiv 1\pmod 7 $$ は成り立ちます。 これで、 $p = 7$ で $n = 2$ のとき、 $$ n^{p-1}\equiv 1\pmod p $$ が成り立つことが確かめられました」

僕「うんうん。これがテトラちゃんのいう《フェルマーの小定理》のイメージなの？」

テトラ「え？　あっ、違います違います。 これはあたしが胸のドキドキを鎮めるための儀式みたいなものです。 《小さな数で考える》や《具体的な数を当てはめてみる》ということですっ！」

僕「ここからテトラちゃんのイメージが展開するんだね」

さまざまな $n$ で試してみる

テトラ「いまあたしが試したのは $p = 7$ で $n = 2$ の場合だけでした。 でも、《フェルマーの小定理》がいうのは、

• $p$ が、どんな素数であっても……
• $n$ が、 $p$ と互いに素などんな整数であっても……
• $n^{p-1} \equiv 1 \pmod p$ が成り立つ！

僕「……」

テトラ「$p = 7$ は素数ですから、 $\GCD{n}{p} = \GCD{n}{7} = 1$ となる $n$ を探すのは難しくありません。 だって、 $p$ の倍数でない整数 $n$ はすべて $\GCD{n}{7} = 1$ となるわけですから」

僕「そうだね。 $p$ は素数だから素因数は $p$ だけ。 $\GCD{n}{p} = 1$ ということは $n$ は $p$ を素因数に持たない。 いいかえると $n$ は $p$ の倍数ではない」

テトラ「はい。そういうことです。なので、 $p = 7$ と $n = 1,2,3,4,5,6$ で $$ n^{p-1} \equiv 1 \pmod p $$ が成り立つことを試してみます」

僕「ねえ、テトラちゃん。いま繰り返して $3$ を掛けたけど、 $$ 3^3 \equiv 6 \pmod 7 $$ まで来たなら、両辺を $2$ 乗して $3^6 \equiv 36 \pmod 7$ が得られて、 すぐに $$ 3^6 \equiv 1 \pmod 7 $$ まで行けたんじゃない？」

テトラ「はい、でも……」

僕「$a \equiv b \pmod p$ のとき、 $a^2 \equiv b^2 \pmod p$ なのは証明できるよ。 だって $a - b$ が $p$ の倍数なら、 $a^2 - b^2 = (a+b)(a-b)$ も $p$ の倍数だからね」

テトラ「たしかに、その方が $3^{7-1}\equiv 1 \pmod 7$ については早く確かめられます。 それは先輩のおっしゃる通りです。 でも、先ほどあたしは、意識的に $3$ を繰り返し掛けようと思ったんです」

僕「それはまたどうして？」

テトラ「はい、 それは、 $$ \MARK1\to \MARK3\to \MARK2\to \MARK6\to \MARK4\to \MARK5\to \MARK1 $$ という《ジャンプ》の繰り返しを見たかったからです」

僕「ははあ、なるほどね！　《$n$ 倍して $p$ で割った余りをとる》という計算を《ジャンプ》に見立てたわけだ」

《ジャンプ》の繰り返しを観察する

テトラ「実はさっきまでこんな表を作っていたんです。 これは《$7$ を法とする世界の $n^k$》の表です」

僕「あっ、これは楽しい！」

テトラ「楽しいですよね！　繰り返しのパターンが見えてくるようです。 $n$ を掛けるたびに次の数に《ジャンプ》する様子はこうなります」

僕「うんうん、パターンが見えてくるね」

テトラ「ここ！　ここにあたしが感じる不思議ポイントがあります。 $n$ はみんなばらばらに見えるのに、 $\MARK1$ からはじめて $6$ 回《ジャンプ》したとき、 みんなそろって $\MARK1$ に着地してますよね。 これがすごく不思議です」

僕「確かにテトラちゃんのいう通りだね。 それで、この不思議ポイントからテトラちゃんは《フェルマーの小定理》の証明まで行きたいということ？　 数学的帰納法と二項定理を使った証明とは別の証明に」

テトラ「は、はい。できれば。 この《ジャンプ》の繰り返しパターンから行きたいと思いました」

僕「うん」

テトラ「あたしが考えていたのはいわゆる鳩の巣論法です」

僕「おっと、いきなり大技が出てきたね」

鳩の巣論法

テトラ「《$p$ を法とする世界》で $1$ から始めて $n$ を何度も掛けていきます。 つまり、さっきの《ジャンプ》です。 $$ 1\to n\to n^2\to n^3\to \ldots $$ これは無限に続けられますけれど、 $p$ を法として考えていますので、 《ジャンプ》した着地先は必ず、 $0,1,\ldots,p-1$ の $p$ 個の数のどれかになるはずです。 つまり鳩の巣が $p$ 個ある設定です！　なので、 《ジャンプ》していれば、いつかは $1$ に戻ってくるはずですね？」

僕「いや、それはおかしいよ。テトラちゃんのいう《ジャンプ》した着地先が $p$ 個のどれかになるのは正しい。 $n$ 倍して $p$ で割った余りだから。 でもだからといって、それだけの理由で $1$ に戻ってくるとまではいえないよね。 $1$ 以外のところだけを飛び回るループになるかもしれない、と反論できちゃうから。 有限個をぐるぐるジャンプした着地先のどこかに $1$ があることをいわなくちゃいけない」

テトラ「……確かにそうですね。有限個のどこかに着地するからといって、 それだけでは $1$ に着地するとはいえません……で、でも必ず $1$ には着地するんですよ！」

僕「さっきテトラちゃんが持ち出してきた《鳩の巣論法》でいえたことを合同式の形で書いてみようよ。 $1$ から始めて $n$ 倍する《ジャンプ》を繰り返す。 $$ 1 \to n \to n^2 \to n^3 \to \ldots $$ これを $p$ を法とする世界で考えると、以前着地した経験があるところに再着地するといってたわけだ。 つまり、 $0$ 以上の整数 $j$ と $k$ が存在して、 $j < k$ でしかも $$ n^j \equiv n^k \pmod p $$ が成り立つ。鳩の巣論法からいえるテトラちゃんの主張はこれだね。そしてここまでは正しい」

テトラ「これは《$j$ 回目のジャンプで着地した巣》と《$k$ 回目のジャンプで着地した巣》が同じということですね」

僕「そうそう。 $j < k$ という条件で再（・）着地になるわけだ。 でもテトラちゃんが言いたかったのは、 $$ n^d \equiv 1 \pmod p $$ という正整数 $d$ が存在することだよね？」

テトラ「確かにそうです！　 $d$ 回目の《ジャンプ》で $1$ に着地するんですから……あっ、 わかりました。わかりました！ $$ n^j \equiv n^k \pmod p $$ の両辺を $n^k$ で割り算すればいいんですよ！ そうすれば、 $$ n^{j-k}\equiv 1 \pmod p $$ が成り立ちますから！　これでいいですね！」

僕「うん、それで正解なんだけど、そこで割り算ができる理由をいう必要があるね。 ちょうど等式のときにゼロ割りではないことを宣言するのと同じ理由が要る」

テトラ「ああ……忘れていました。合同式での割り算には条件があるんでした。 法 $p$ と互いに素な数でなければ割っては駄目です。 でもっ！　いまはっ！　大丈夫ですっ！　なぜなら《フェルマーの小定理》では $n$ は $p$ と互いに素という条件がありますから！」

僕「テトラちゃんのいう通り。 $n$ は $p$ と互いに素だから $$ n^j \equiv n^k \pmod p $$ の両辺を $n$ で割り算できる。 繰り返して $k$ 回割り算すれば $$ n^{j-k} \equiv n^{0} \pmod p $$ になって、めでたく $$ n^{j-k} \equiv 1 \pmod p $$ がいえた。 $d = j-k$ と置けば、 $j > k$ という条件から $d > 0$ であり、 $$ n^{d} \equiv 1 \pmod p $$ が成り立つ」

テトラ「これで証明ができましたねっ！」

僕「いやいや、テトラちゃん。 ここまでで証明できた命題はこれだよ」

テトラ「確かに！　 $d$ 回ジャンプすれば $1$ に着地することはいえました。 でも、 $p - 1$ 回ジャンプしたときに $1$ に着地することは、 まだいえてません……難しいですね」

僕「いや、でも、さっきテトラちゃんが作ってくれた表を単純化すると、 パターンが見やすくなるから、そこからヒントが得られる」

テトラ「パターンがあるのはわかります。 $2,4,1$ の繰り返しや、 $6,1$ の繰り返しなどがありますから。でもその先がわかりません」

僕「こんなふうに $\MARK1$ で終わる $\fbox{まとまり}$ を考えるとすっきりするはず。 これは $p = 7$ のときだから横に $1,2,3,4,5,6$ のマス目がある。 $p-1$ 個だね」

テトラ「$d$ 回ジャンプすれば $1$ に着地する。 $p-1$ 回ジャンプしたときに $1$ に着地することはどうすればいえるか……」

僕「……」

テトラ「証明はわからないんですが、 どういうパターンなのかはわかりました。 同じ $\fbox{まとまり}$ が繰り返すんですが、 $\fbox{まとまり}$ のなかにある数の個数は $1$ 個か、 $2$ 個か、 $3$ 個か、 $6$ 個のどれかになります。 そしてそれは、 $p - 1 = 6$ の約数ですね！」

僕「うん、だから、あとはこれを証明できれば、 《フェルマーの小定理》が証明できる」

テトラ「あとはこれを証明すればいい？」

僕「そういうことだね。すでにこのような $d$ が必ず存在することは示した。 $d$ が $p-1$ の約数なら、 $d$ 回ジャンプするごとに $1$ に着地するんだから、 $p-1$ 回目のジャンプでも $1$ に着地するわけだ。 ちゃんと書くなら、 $d$ が $p-1$ の約数ということは、 $p - 1 = dm$ という $m$ が存在するということで、 そのとき、 $$ n^{p-1} = n^{dm} = (n^d)^m $$ になるから、 $n^d \equiv 1 \pmod p$ より、 $(n^d)^m \equiv 1 \pmod p$ になって、 $$ n^{p-1} \equiv 1 \pmod p $$ になる。 だから、 $d$ が $p-1$ の約数であることを示すのがラスボスだよ！」

テトラ「ラスボス！」