第475回 シーズン48 エピソード5

平方剰余とルジャンドル記号（前編）

図書室

ミルカ「やっと来たか」

テトラ「せんぱーい！　こっちです！　お待ちしてました！」

僕「ねえテトラちゃん。ここは図書室なんだから、大きな声を出しちゃだめだよ」

テトラ「あっ、そ、そうですよね。すみません……つい」

ミルカ「遅かったな」

テトラ「先輩のことをお待ちしてたんですよ」

僕「あ、そうなんだ」

テトラ「フェルマーの小定理の話をミルカさんもしてくれるということで、 先輩がいらっしゃるのを待ってたんです」

ミルカ「話はすぐに終わるんだが、テトラが『おあずけ』と命じるので我慢していた」

テトラ「そ、そんなこと言ってませんよぅ！」

ミルカ「フェルマーの小定理の証明は、以前一緒に追った（第400回参照）」

テトラ「はい。数学的帰納法を使いましたね」

僕「先日はテトラちゃんのイメージを形にするような証明を作ったよ（第473回参照）」

テトラ「そうです。たとえば $p = 7$ のときだと、 $n = 1,2,3,4,5,6$ のどれを使っても、みんな $p-1$ 回目の《ジャンプ》で、 $\MARK1$ にぴったり着地する。 その不思議ポイントから考えをスタートしました」

僕「最後のラスボスを倒すのには手間取ったけどね（第474回参照）」

ミルカ「その証明は、さっきテトラから聞いたよ」

テトラ「それで……ミルカさんのお話とは？」

ミルカ「テトラの観察は《$n$ を繰り返し掛ける》ところにあった。 $n$ を掛けるたびに《ジャンプ》をするという比喩を使い、 $\MARK1$ から始めて $p-1$ 回目の《ジャンプ》で $\MARK1$ に着地する。 まさにそれはフェルマーの小定理の主張だ」

僕「……」

テトラ「……」

ミルカ「ではここで視点を変える。 《ジャンプ》を表す写像 $f_n$ を考えよう」

僕「つまり、 $f_n(x) = \BAR{nx}$ というのは、 $nx$ を $p$ で割ったときの余りだよね？」

ミルカ「そうだ。 念のためにいっておくと、 $\BAR{nx} \in \SET{\MARKB0,1,2,3,\ldots,p-1}$ であり、 $\MARKB0\not\in P$ だから、 $f_n$ が $P$ から $P$ への写像であるというためには、 $x\in P$ のとき $\BAR{nx}\NEQ\MARKB0$ であることを示す必要がある。 まあ、これは読者の練習問題でいいだろう。 ところで、テトラは $f_n$ は何だかわかるのかな」

テトラ「はい。 $f_n$ がどんなものかはわかります。 たくさん練習しましたから。 たとえば、 $p = 7$ で $n = 2$ のとき、 $f_n$ つまり $f_2$ はこうなります。 $f_2(x)$ は $2$ 倍した $x$ を $7$ で割った余りをとればいいからです」

僕「うん、 $f_n$ はわかるよ。でもわざわざ $f_n$ と名前を付ける意味はないよね。 だって $\BAR{nx}$ と書けばいいんだから」

ミルカ「私が $f_n$ と名前を付けたのは、 カギになる主張を一言で言いたいからだ」

僕「カギになる主張？」

ミルカ「それは、

　写像 $f_n$ は $P$ から $P$ への全単射（ぜんたんしゃ）である

という主張だよ。 別の言い方として、

　写像 $f_n$ は集合 $P$ 上の置換である

といってもいい」

《ジャンプ》は全単射

テトラ「ど、どういう意味でしょう？」

僕「写像 $f_n$ は、 $1,2,3,\ldots,p-1$ を並べ替えると言ってるんだよ、テトラちゃん」

テトラ「ははあ……こういうことですか。 $p = 7$ で $n = 2$ の例でいうと、

• $1$ は $f_2$ によって $2$ に移り、
• $2$ は $f_2$ によって $4$ に移り、
• $3$ は $f_2$ によって $6$ に移り、
• $4$ は $f_2$ によって $1$ に移り、
• $5$ は $f_2$ によって $3$ に移り、
• $6$ は $f_2$ によって $5$ に移るので、

僕「そうだね。 全単射だから《もれなく、だぶりなく》移されてくる。 だから並べ替えになる」

テトラ「あれ？　それって、どんな $n$ と $p$ でも？　そんなこといえるんですか？」

僕「そりゃそうだよね。だって、 $n$ と $p$ は互いに素なんだから」

テトラ「えっえっ？」

ミルカ「そこで引っかかるなら、ちゃんと示す価値がありそうだ」

テトラ「わからなくなってしまいました……」

ミルカ「どこまでならわかっている？」

テトラ「はい。 $n$ と $p$ が互いに素のとき、 $$ an\equiv bn\pmod p $$ から $$ a\equiv b\pmod p $$ がいえることまではわかっています。 $p$ と《互いに素》な $n$ なら、 両辺を《割れる》んです」

僕「それだよ」

ミルカ「そこだな」

テトラ「えっ、えっ、えっ？」

ミルカ「君が、まず単射性を示す」

僕「テトラちゃんがいま言ったことは、 そのまま $f_n$ が単射であることの証明につながるよ。 $a,b$ を $P$ の要素として、 $f_n$ で移した先が等しいと仮定する。 つまり、 $$ f_n(a) = f_n(b) $$ を仮定する。これは $f_n$ の定義から $\BAR{an} = \BAR{bn}$ ということで、 $$ an\equiv bn\pmod p $$ になる。テトラちゃんがいま言った通り、両辺を $n$ で割れるから、 $$ a\equiv b\pmod p $$ がいえる。 $a$ も $b$ も $1$ 以上 $p-1$ 以下だから、 $$ a = b $$ になる。 $P$ の要素 $a,b$ に対して $$ f_n(a) = f_n(b) \NARABA a = b $$ が示されたから $f_n$ は単射だね」

テトラ「あ……《移った先が等しいなら、もとも等しい》。 つまり $f_n$ は《だぶりなく》移す……つまり単射です」

ミルカ「そこから全射性はすぐに言える。 $P$ は、要素がちょうど $p-1$ 個ある有限集合で、 $p-1$ 個の要素が《だぶりなく》移るのだから、 移った先も $p-1$ 個になる。 ところが $P$ の要素はぜんぶで $p-1$ 個しかないから……」

テトラ「$f_n$ は《もれなく》移す全射にもなってます！」

ミルカ「単射かつ全射。ゆえに $f_n$ は $P$ から $P$ への全単射」

フェルマーの小定理？

僕「ところで 《$f_n$ は全単射》 から何がいえるの？」

テトラ「フェルマーの小定理のお話ですよね？」

ミルカ「写像 $f_n(x) = \BAR{nx}$ は $P$ 上の全単射だから、 $$ \SET{1\COMMA2\COMMA3\COMMA\ldots\COMMA p-1} = \SET{\BAR{1n}\COMMA\BAR{2n}\COMMA\BAR{3n}\COMMA\ldots\COMMA\BAR{(p-1)n}} $$ が成り立つ」

僕「そうだね」

テトラ「はい、順番は変わるかもしれませんが、 $1,2,3,\ldots,p-1$ という $p-1$ 個の要素を持つ集合ですよね」

ミルカ「そこで全要素をすべて掛け合わせると、 $$ 1\times2\times3\times\cdots\times(p-1) = \BAR{1n}\times\BAR{2n}\times\BAR{3n}\times\cdots\times\BAR{(p-1)n} $$ から、 $$ 1\times2\times3\times\cdots\times(p-1) \equiv 1n\times2n\times3n\times\cdots\times(p-1)n \pmod p $$ となり、 $$ (p-1)! \equiv n^{p-1}\times(p-1)! \pmod p $$ となる。 $p$ は素数なので、 $(p-1)!$ は $p$ と互いに素。 よって、両辺を $(p-1)!$ で割って左右を交換すると、 $$ n^{p-1} \equiv 1 \pmod p $$ となり、フェルマーの小定理が証明できた」

テトラ「あらららっ！！」