第474回 シーズン48 エピソード4

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

フェルマーの小定理

僕「うん、 $n^0,n^1,n^2,\ldots$ をそれぞれ $p$ で割った余りを観察すれば、 テトラちゃんが見つけたような予想ができる。 でもそれはあくまで予想だ。 でも、これを証明できれば、 《フェルマーの小定理》が証明できたことになる」

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

僕「そういうことだね。 すでに《鳩の巣論法》でこの $d$ が必ず存在することは示した（第473回参照）。 だから、 $d$ が $p-1$ の約数であることを示すのがラスボスだよ！」

テトラ「ラスボス！」

僕「……」

テトラ「具体的なパターンははっきりわかります。 $p = 7$ で $n = 2$ のとき、 $$ 2\to4\to\MARK1 $$ のように $\MARK1$ に着地したら、 あとはまた $n = 2$ から始まりますので、 $2\to4\to\MARK1$ がループとなって繰り返されることはわかります」

僕「そうだね」

テトラ「$d$ というのはこのループの長さということですよね。 $d=3$ が $p-1=6$ の約数になるのはすぐわかりますけれど、 一般的に証明するのは難しいです。 もどかしい……」

僕「$2,4,\MARK1$ 以外はどうだろう？　つまりループ外にある数」

テトラ「$2,4,\MARK1$ 以外？」

僕「$p = 7$ で考えているから、 $1$ から $p-1$ までの整数は $$ 1,2,3,4,5,6 $$ という $6$ 個になる。 そのうち、ループの $2,4,\MARK1$ に入ってないループ外の数は $3,5,6$ の $3$ 個ある」

テトラ「そうですね。でもそれはループ外ですから、あまり $d$ とは関係ないような……」

僕「そんなことはないよ。 だって、もしもループの長さ $d$ が $p-1$ の約数になるというなら、 ループの長さ $d$ は、 $(p-1)-d$ の約数でもある。つまり、 $d$ は、 ループ外に取り残された数の個数 の約数になるはずだよね」

テトラ「えっえっ？」

僕「たとえば、 $p=7, n=2$ なら、 全体の $p-1=6$ 個から ループ内にある $2,4,\MARK1$ の $d=3$ 個を引くと、 残りは $3,5,6$ の $3$ 個で、 $d=3$ はその約数になっている」

テトラ「それはそうですね」

僕「それからたとえば、 $p = 7, n = 6$ なら、ループ内に $6,\MARK1$ の $d=2$ 個があって、 ループ外には $2,3,4,5$ の $4$ 個がある。そして $d=2$ は $4$ の約数になっている」

テトラ「あっあっあっ！　待って待って待って！　あたし、わかったかも！　別のループができそう！」

僕「おっ？」

テトラ「あたしたちが作った $$ 6\to\MARK1\qquad(\cdots\to6\to\MARK1\to\cdots) $$ とは別のループとして、 $$ 2\to5\qquad(\cdots\to2\to5\to\cdots) $$ というループができます！　それから、 $$ 3\to4\qquad(\cdots\to3\to4\to\cdots) $$ というループも！　ぜんぶ、《$6$ を掛けて $7$ で割った余り》で《ジャンプ》するループです！」

僕「なるほど、なるほど。 《$6$ を掛けて $7$ で割った余り》を使って 新たなループを作り出したんだね。出発点を $2$ にしたらループ $2,5$ ができて、 出発点を $3$ にしたらループ $3,4$ ができる。つまり、テトラちゃんのいう《ジャンプ》は、 《$p=7$ を法とする世界》での《$n=6$ 倍》なんだ！」

テトラ「そうですね」

僕「うん、これで一般化した証明ができるよ。 $n^1,n^2,\ldots,n^d$ というループに対して……」

テトラ「あっ、すっ、すみません。 $p=7,n=2$ で具体例を確かめたいです。本当に別のループができるかどうか」

僕「そうだね、さすがテトラちゃんだ」

テトラ「すぐにできます。 まず最初のループは、 $2\to4\to\MARK1$ でした。 これは $2$ から始めて《$p=7$ を法とする世界》での《$n=2$ 倍》です。 $$ 1,2,3,4,5,6 $$ の中からループ $2,4,\MARK1$ 以外の数として $3$ を選びます。 $3$ から始めて《$p=7$ を法とする世界》での《$n=2$ 倍》を繰り返すと、 $$ 3\to6\to5 $$ になりますね。 $5$ は $6\times 2=12$ を $7$ で割った余りです。 そして $5\times2 = 10$ を $7$ で割った余りは $3$ でループになります！」

僕「いいね！　じゃあ、一般化した証明を作ろう。 $$ n^1,n^2,\ldots,n^d $$ というループに対して、ループ外の数 $m$ を一つ選んで、 $$ mn^1,mn^2,\ldots,mn^d $$ という数列を作る。すると……」

テトラ「ちょっとお待ちください。 ループとなるのは、 $$ n^1\COMMA n^2\COMMA \ldots\COMMA n^d $$ ではないですよね。単なる冪乗ではなく、 $p$ で割った余りを考える必要があります」

僕「あっと、確かにそうだなあ……一般的に書くときに面倒だから、 余りを表す表記の約束を決めよう」

テトラ「表記の約束？」

整数 $a$ を $p$ で割った余り $\BAR{a}$

僕「うん、これから 整数 $a$ を $p$ で割った余りを $$ \BAR{a} $$ と表記することにしよう」

テトラ「なるほど。 具体例で確かめます。 $p = 7$ で $n = 2$ のときのループは $2,4,\MARK1$ ですが、それを $$ \BAR{2^1}\COMMA\BAR{2^2}\COMMA\BAR{2^3} = \MARK1 $$ と書けるということですね。 $2^3 = 8$ ですけれど、 $8$ を $7$ で割った余りは $1$ なので $\BAR{8} = 1$ になる」

僕「そういうこと。 $\overline{\text{この表記}}$を使うと、 $n$ から始まって $\MARK1$ に着地するループは、 $$ \BAR{n^1}\COMMA\BAR{n^2}\COMMA\ldots\COMMA\BAR{n^d} = \MARK1 $$ と書ける。 これで一般化する証明が書きやすくなる」

テトラ「そうですね。 $a\equiv b\pmod p$ が $\BAR{a}=\BAR{b}$ と書けます」

僕「もしも、たまたま（・・・・） このループが $1,2,\ldots,p-1$ のすべてを巡ってくれたなら、うれしい。 その場合は $d = p-1$ になって、 $d$ は $p-1$ の約数になっているから」

すべてを巡るループ

テトラ「ちょっとお待ちください。 あたしの理解を確認させてください。 すべてを巡るというのは、 たとえば、 $p = 7, n = 3$ のときのような場合ですね？ ループは、 $$ \BAR{3^1}\COMMA \BAR{3^2}\COMMA \BAR{3^3}\COMMA \BAR{3^4}\COMMA \BAR{3^5}\COMMA \BAR{3^6}=\MARK1 $$ で、具体的には $$ 3\COMMA 2\COMMA 6\COMMA 4\COMMA 5\COMMA \MARK1 $$ です。いまおっしゃったのはこのような場合のことですよね？」

僕「そういうこと。 $d = p-1$ の場合は $d$ は $p-1$ の約数になるから、 もう考えなくていい」

テトラ「はいはい、わかります。 ラスボスの一部を撃破しました！」

別のループを作る

僕「$d = p-1$ の場合は済んだから、 証明の残りでは $d < p-1$ の場合を考えることになる」

テトラ「はい。 ループ外の数からスタートして 別のループ を作るんです！」

僕「そうだね。 $d < p - 1$ の場合には、 $n$ から始まって $\MARK1$ に着地するループ $$ \BAR{n^1}\COMMA\BAR{n^2}\COMMA\ldots\COMMA\BAR{n^d} = \MARK1 $$ で訪れない数が、 $$ 1,2,\ldots,p-1 $$ のどこかに少なくとも一つはある。 それを $m_1$ と呼ぶことにしよう。 これは集合の表記を使いたくなるところだね。 $$ \begin{xalignat*}{2} P &= \SET{1,2,\ldots,p-1} \\ M_0 &= \NSET{n} \end{xalignat*} $$ とおいて、集合 $P$ に属しているけれど、集合 $M_0$ に属していない数として、 $m_1$ を一つ選ぶ。これは、集合の差を使って $$ m_1 \in P\setminus M_0 $$ と書ける」

テトラ「なるほどです。念のため、具体例で理解を確認します！ $p = 7$ で $n = 2$ の場合、 $$ \begin{xalignat*}{2} P &= \SET{1,2,3,4,5,6} \\ M_0 &= \SET{\BAR{2^1}\COMMA\BAR{2^2}\COMMA\BAR{2^3}} = \SET{2,4,1} \end{xalignat*} $$ ということですから、 集合の差 $P\setminus M_0$ は、 $$ P\setminus M_0 = \SET{1,2,3,4,5,6}\setminus\SET{2,4,1} = \SET{3,5,6} $$ になります。 $m_1$ としては $3,5,6$ のどれかから選ぶ……はい、 あたしがイメージした通りです」

僕「そして、 《$\MARKB{m_1}n^1$ から始まる別のループ》を作ることになる。 $$ \begin{array}{cccccccccccccc} \BAR{{n}^1}\COMMA & \BAR{{n}^2}\COMMA & \ldots\COMMA& \BAR{{n}^d} \\ \downarrow & \downarrow & \vdots & \downarrow \\ \BAR{\MARKB{m_1}{n}^1}\COMMA& \BAR{\MARKB{m_1}{n}^2}\COMMA& \ldots\COMMA& \BAR{\MARKB{m_1}{n}^d} \end{array} $$ これで、 $$ M_1 = \MSET{m_1} $$ という集合を作る」

テトラ「はいはいっ！　もうわかりましたよ。具体例で理解を確かめますね。 $p = 7$ で $n = 2$ の場合、 $m_1$ として $3$ を選んだときには、 《$\MARKB{3}\times 2^1$ から始まる別のループ》を作るんですが、それは $$ \begin{array}{cccccccccccccc} \BAR{{2}^1}\COMMA & \BAR{{2}^2}\COMMA & \BAR{{2}^3} \\ \downarrow & \downarrow & \downarrow \\ \BAR{\MARKB{3}\times{2}^1}\COMMA& \BAR{\MARKB{3}\times{2}^2}\COMMA& \BAR{\MARKB{3}\times{2}^3} \end{array} $$ となります。 これで、 $$ M_1 = \SET{\BAR{\MARKB{3}\times{2}^1}\COMMA\BAR{\MARKB{3}\times{2}^2}\COMMA\BAR{\MARKB{3}\times{2}^3}} = \SET{\BAR{6}\COMMA\BAR{12}\COMMA\BAR{24}} = \SET{6\COMMA5\COMMA3} $$ という集合 $M_1$ ができました。 $M_0$ と $M_1$ で、全部が埋まりましたね！」

僕「テトラちゃんは、一歩一歩、具体的に書いていくんだね。偉いなあ」

テトラ「き、恐縮です。具体的に書かないと心配なので……でも、 これで証明はできましたね。

• $d$ 個の要素を持つ集合 $M_0$ を作り、
• $M_0$ 以外から $m_1$ を選んで集合 $M_1$ を作り、
• $M_0,M_1$ 以外から $m_2$ を選んで集合 $M_2$ を作り、
• $M_0,M_1,M_2$ 以外から $m_3$ を選んで集合 $M_3$ を作り、
• これを繰り返して……
• $M_0,M_1,M_2,\ldots,M_{t-2}$ 以外から $m_{t-1}$ を選んで集合 $M_{t-1}$ を作ります。

僕「おお！」

テトラ「たとえば、 $p=7,n=6,m_1=2,m_2=3$ としたときには、 集合の個数は $t = 3$ となります。 $t$ はループの数です！」

僕「うん、ストーリーはその通り！　ちゃんとテトラちゃんはわかってるね」

テトラ「ストーリーは……といいますと？」

僕「証明としてはまだ足りないポイントがあるんだ」

テトラ「足りないポイント……」

僕「足りないポイントは次の（1）と（2）だね」

• （1）$k=0,1,2,\ldots,t-1$ で $\ABS{M_k}=d$ を示す。
• （2）$j < k$ のとき $M_j\cap M_{k}=\varnothing$ を示す。

足りないポイント（1）

テトラ「（1）は、 $M_0,M_1,M_2,\ldots,M_{t-1}$ の要素数が $d$ 個ずつということですよね……でも、 あたしはそれは当たり前だと思ってしまいました。だって、たとえば $M_1$ は、 $$ M_1 = \SET{\BAR{m_1n^\MARKB1}\COMMA\BAR{m_1n^\MARKB2}\COMMA\ldots\COMMA\BAR{m_1n^\MARKB d}} $$ ですから、 $n$ の指数を見ればわかる通り、 集合 $M_1$ の要素は $d$ 個なのではありませんか？」

僕「でもその $d$ 個の中にはダブりがないことを示さないとね」

テトラ「あっ……」

僕「でも、示すのは難しくないよ。 たとえば、 $$ \BAR{m_1n^{\MARKB j}} = \BAR{m_1n^{\MARKB k}}\qquad (1\LEQ j < k \LEQ d) $$ を満たす $j,k$ があったとすると、 これは $$ m_1n^{\MARKB j} \equiv m_1n^{\MARKB k} \pmod p $$ ということだから、 $p$ と互いに素な $m_1n^j$ で両辺を割って $1\equiv n^{k-j} \pmod p$ となる。 つまり、 $$ n^{k-j} \equiv 1 \pmod p $$ だけど、 $1 \LEQ k-j < d$ だから $d$ の最小性に反する。 それで $d$ 個の中にはダブりがない。 もちろんこの議論は $M_0,M_1,M_2,\ldots,M_{t-1}$ のどれについてもいえる」

テトラ「これと似た議論、さっきもやりましたね（第473回参照）」

僕「そうだね。 $d$ を $n^{d}\equiv 1\pmod p$ を満たす最小の正整数と定義したのが効いてる」

足りないポイント（2）

テトラ「足りないポイント（2）は、 $j < k$ のとき、 $$ M_j\cap M_{k}=\varnothing $$ ということ。これは異なるループは交わらないということですよね。 ううう……これも当たり前に感じてしまいます」

僕「これも（1）と同じように示せるんじゃないかな。 $j < k$ のとき、 $$ \BAR{m_jn^{\MARKB J}} = \BAR{m_kn^{\MARKB K}} \qquad\cdots\cdots\text{（$\clubsuit$）} $$ を満たす $J,K$ があったとする。 ただし、 $1\LEQ J\LEQ d$ で $1\LEQ K\LEQ d$ とする。 ここから矛盾を導けばいい」

テトラ「……」

僕「$j < k$ だから、 $m_k$ は、その選び方により、 $$ m_k \not\in M_0\cup M_1\cup \cdots \cup M_j \cup \cdots \cup M_{k-1} $$ を満たさなくてはいけない。 つまり、 $$ m_k \not\in M_j $$ のはず。 だから、 $\clubsuit$ から $$ m_k \in M_j $$ を導ければ矛盾して証明完了だよ。 ここがラスボスの最後の砦だ！　 でも、うーん、 $J$ と $K$ の大小関係で場合分けが要りそうだ」

テトラ「場合分け、やりましょうよ！ $J = K$ と $J > K$ と $J < K$ ですよね？　 最後の三つの砦です！」

僕「そうだね。よし、やろう！　すべての場合で矛盾を導けばいい」

テトラ「これで完成ですね！　テトラ、満足です！　一歩一歩、具体例で確かめましたし……

• $1,2,\ldots,p-1$ を $t$ 個の交わらないループで埋め尽くす。
• ループの長さがすべて $d$ なので、 $d$ が $p-1$ の約数になる。

僕「感覚的にはわかった気になるんだけど、思ってたより大変だったなあ……」

瑞谷先生「下校時間です」

放課後のメタトーク！

ミルカ「では、私の出番がなかった件について議論しようか」

僕「……」

テトラ「……」

ミルカ「……」

僕「（というか、僕たちに言われても困るんだよなあ）」

ミルカ「ん？」

僕「いや、独り言」

ミルカ「ふむ」

テトラ「あ、あたしがたくさん具体例を作ってしまったからでしょうか。 それで時間を使い過ぎて……」

ミルカ「いや、 具体例を作ることに文句をいう人は誰もいない。 テトラは立派だ」

僕「き、きっと次回はミルカさん登場シーンから始まるんじゃないかなあ……」

ミルカ「だといいな」

テトラ「フェルマーの小定理、ミルカさんの別証明も見たいです！」

ミルカ「ふうん……」

瑞谷先生「メタ下校時間です」