第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$ の場合を考えることになる」

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