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

平方剰余とルジャンドル記号（前編） ただいま無料

図書室

ミルカ「やっと来たか」

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

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

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

ミルカ「遅かったな」

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

僕「あ、そうなんだ」

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

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

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

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

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

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

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

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

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

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

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

僕「……」

テトラ「……」

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

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

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

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

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

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

僕「カギになる主張？」

ミルカ「それは、

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

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

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

といってもいい」

《ジャンプ》は全単射

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

僕「写像 $f_n$ は、 $1,2,3,\dots ,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$ に移るので、

結局は、 $1,2,3,4,5,6$ を $2,4,6,1,3,5$ に並べ替える？」

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

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

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

テトラ「えっえっ？」

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

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

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

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

僕「それだよ」

ミルカ「そこだな」

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

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

僕「テトラちゃんがいま言ったことは、 そのまま $f_n$ が単射であることの証明につながるよ。 $a,b$ を $P$ の要素として、 $f_n$ で移した先が等しいと仮定する。 つまり、 $$f_n(a)=f_n(b)$$ を仮定する。これは $f_n$ の定義から $\overline{an}=\overline{bn}$ ということで、 $$an\equiv bn(\mathrm{mod}p)$$ になる。テトラちゃんがいま言った通り、両辺を $n$ で割れるから、 $$a\equiv b(\mathrm{mod}p)$$ がいえる。 $a$ も $b$ も $1$ 以上 $p-1$ 以下だから、 $$a=b$$ になる。 $P$ の要素 $a,b$ に対して $$f_n(a)=f_n(b)\text{ならば}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)=\overline{nx}$ は $P$ 上の全単射だから、 $$\{1,2,3,\dots ,p-1\}=\{\overline{1n},\overline{2n},\overline{3n},\dots ,\overline{(p-1)n}\}$$ が成り立つ」

僕「そうだね」

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

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

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

僕「なるほどねえ……この証明は、 数学的帰納法による証明とも、 ループを使った証明とも違うね。 いったい何が違うんだろう。 $n$ 倍して $p$ の剰余をとるという写像 $f_n(x)=\overline{nx}$ の何が効いているんだろうね」

テトラ「何だか……視野が広いと感じました」

僕「視野？」

テトラ「$P$ 全体を見てる……みたいな？　 $f_n$ を使って $1,2,3,\dots ,p-1$ を置き換えると、 $\overline{1n},\overline{2n},\overline{3n},\dots ,\overline{(p-1)n}$ が得られますけれど、 変わっているのは順序だけ。だから全部掛けても変わらない……というところが効いているんですよね？」

僕「そうだね」

テトラ「ミルカさんのご説明を聞いていると、 $$1,2,3,\dots ,p-1$$ という《$p$ と互いに素》なメンバーたち一人一人に《$n$ 倍して剰余を取る》という指をさして、 あっちいけー！　こっちいけー！　と命じているイメージが浮かびました。 そうすると、 $$\overline{1n},\overline{2n},\overline{3n},\dots ,\overline{(p-1)n}$$ が得られるんですっ！」

僕「確かにね」

テトラ「きゃうんっ！」

瑞谷先生「お静かに」

テトラ「あっ、す、すみません……」

ミルカ「静かにしろと命じられることもある」

図書室

僕「テトラちゃん！」

テトラ「……」

僕「どうしたの。元気ないね」

テトラ「反省しているんです」

僕「え？」

テトラ「昨日は大声を出しすぎました。テトラはとても（・・・）反省しています。お恥ずかしい」

僕「でも、そんなに小声にならなくてもいいと思うよ。普通に話そうよ。それは？」

テトラ「村木先生からの《カード》です。でも、《表》と《裏》があるんですっ！」

村木先生の《カード》

僕「なるほど。 この《表》の方は簡単だね」

テトラ「はい。この《表》って要するに 二次方程式の判別式の話です」

僕「うん……」

テトラ「《裏》はすごく《表》に似ています。 条件も似ていて、式の形も似ていて、問われていることは同じです！　 あたしでも《表》はわかります。でも、この、《裏》は、さっぱりわかりません！！」

僕「テトラちゃん。声」

テトラ「《裏》は、さっぱりわかりません！」

僕「《表》は僕たちがよく知ってるし、導くこともできる。 でも《裏》は違う。何が問われているかはわかるけれど、 どうすればいいかはわからない」

テトラ「はい」

僕「僕は思うんだけど、これは村木先生からのチャレンジだね、きっと」

テトラ「チャレンジ？」

僕「つまりね、《表》を本当に（・・・）理解しているなら、 《裏》もわかるはずだろう？……そういうチャレンジ」

テトラ「それは、同じ解法が使えるということでしょうか？」

僕「いや、そこまではわからない。 でも、《裏》への手掛かりが見つかることを期待して、 とりあえずは《表》をていねいに進んでみようよ」

テトラ「《表》の方ならあたしもできますっ！　あっ！　……できますっ！」

カード《表》を考えよう

僕「じゃ、テトラちゃん、どうぞ」

テトラ「はい。《表》の答えなら、すぐに出せます。 二次方程式 $$a{x}^2+bx+c=0$$ が実数解を持つのは、 判別式である $b^2-4ac$ が $0$ 以上のときです。 ですから、実数 $x$ が存在する条件は、 $$b^2-4ac\geqq 0$$ です！」

僕「うん、それは正解」

テトラ「はいっ！」

僕「正解なんだけど…… それは、テトラちゃんが覚えていた判別式を頭から取り出して答えたんだよね？」

テトラ「確かにそうです。 あたしは判別式 $b^2-4ac$ を覚えていて、 実数解を持つ条件は判別式が $0$ 以上ということも覚えています」

僕「もちろんそれは正しいんだけど、 いまの僕たちは《裏》に進む手掛かりがほしいんだ。 《判別式が $0$ 以上》という答えが出てきただけだと、 そこからどこにも行けない」

テトラ「で、では、これではどうでしょう。 解の公式を使うんです。 二次方程式 $a{x}^2+bx+c=0$ の解は、 $$x=\frac{-b\pm \sqrt{b^2-4ac}}{2a}$$ と書けます。 この式を見ると、 $x$ が実数であるためには、 ルートの中身が $0$ 以上であればいいですから、条件は $$b^2-4ac\geqq 0$$ になります！」

僕「そうだね。それも正しいよ。 正しいけれど、解の公式を手掛かりにするのは難しそうだ」

テトラ「そうですか……」

僕「僕たちは《裏》に進む手掛かりがほしい。 そこは整数の世界、特に《$p$ を法とする世界》だ。 そう考えると、 解の公式をその世界に直接持って行くのは難しそうだ」

テトラ「どうしてでしょう」

僕「解の公式には、ルートが出てくる。 《$p$ を法とする世界》でのルートとは何だろう。 それから $2a$ で割る割り算も出てくる。 $2a$ は $p$ と互いに素だから割り算もできそうだけど、 それを分数で書くのもちょっと」

テトラ「あたし、《表》が簡単だといいましたけど、 違いますね。あたし、わかってないです」

僕「いや、テトラちゃんのヒントからいけそうだ。 判別式から解の公式にさかのぼったように、解の公式からさらにさかのぼってみよう」

テトラ「さかのぼる？」

僕「解の公式を導くときに使う平方完成を行うんだ！　割り算もルートも使わずにできるだけ進んでみる。 判別式の直前まで、ね」

テトラ「ははあ……！」

僕「まず、 $a\ne 0$ だから $4a\ne 0$ で、 $$a{x}^2+bx+c=0$$ の両辺を $4a$ 倍した $$4a^2{x}^2+4abx+4ac=0$$ は、もとの方程式と同値になる」

テトラ「すみません、先輩。いま、どうして $4a$ を掛けたんですか？　 ふつうの平方完成は、 $a$ で割って $$x^2+\frac{b}{a}x+\frac{c}{a}=0$$ としませんでしたっけ？」

僕「《表》はそれでも解けるけど、 でも、 $a$ で割ると分数が出てきちゃう。 さっきも言ったけど、《裏》は整数の世界だから、分数をあまり出したくない。 掛け算だけなら、整数の世界でも安心して使える」

テトラ「なるほどです……《裏》を見ながら《表》を進むんですね」

僕「それで、 $4a^2{x}^2+4abx+4ac=0$ を平方完成すると、 $$(2ax+b{)}^2-b^2+4ac=0$$ つまり、 $$(2ax+b{)}^2=b^2-4ac$$ になる。ここで $X=2ax+b$ と置くと、 $a{x}^2+bx+c=0$ を満たす実数 $x$ が存在することは、 $$X^2=b^2-4ac$$ を満たす実数 $X$ が存在することと同値になる。 $x$ があれば $X=2ax+b$ を計算すればいいし、 逆に $X$ があれば、 $2a\ne 0$ だから $x=\frac{X-b}{2a}$ で戻せるからね」

テトラ「なるほど。 $X^2=b^2-4ac$ を満たす実数 $X$ が存在する条件は $b^2-4ac\geqq 0$ になります。 これで判別式が出てくるんですね。 でも、これは《裏》の手掛かりになるんでしょうか」

僕「$b^2-4ac\geqq 0$ の一歩手前が役に立ちそうだ」

テトラ「一歩手前……」

僕「《$X^2=b^2-4ac$ を満たす実数 $X$ が存在する》という部分だよ。

　《$b^2-4ac$ が、ある実数の平方（・・）になっている》

といえば《裏》でも使えそう。ルートも割り算も出てこない。 実数の世界では、《ある実数の平方になっている》ことと 《$0$ 以上である》ことが同じだから、 条件を $b^2-4ac\geqq 0$ と言い換えられたわけだ」

テトラ「《裏》への手掛かりは《平方完成》と《$X^2=b^2-4ac$ を満たす実数 $X$ が存在する》ですねっ！」

僕「そうなるね！」

テトラ「《裏》に進みましょうよ！」

カード《裏》を考えよう

僕「《平方完成》と同じことを、 《$p$ を法とする世界》でやってみよう」

テトラ「はいっ！」

テトラ「できました！」

僕「できたね！　ぴったり同じだ！」

• 《表》の解答は《$X^2=b^2-4ac$ を満たす実数 $X$ が存在する》
• 《裏》の解答は《$X^2\equiv b^2-4ac(\mathrm{mod}p)$ を満たす整数 $X$ が存在する》

テトラ「二つの《宝箱》はそっくりです！　こう書いてもいいですよね？」

• 《表》の解答は《$X^2=b^2-4ac$ を満たす実数 $X$ が存在する》
• 《裏》の解答は《$\overline{X^2}=\overline{b^2-4ac}$ を満たす整数 $X$ が存在する》

僕「そうだね！」

テトラ「ちょっとお待ちください。えーっと、蒸し返してすみませんけれど、 《表》では $b^2-4ac\geqq 0$ という書き方ができました。 でも《裏》では？」

僕「そうだよね。僕もそこが引っかかる。 《裏》で僕たちが言えたのは

　 $b^2-4ac$ がいわば《$p$ を法とする世界の平方数（・・・）》である

という条件だけだ。《表》のように $b^2-4ac\geqq 0$ みたいには書けない」

テトラ「《表》と《裏》で、《平方完成》というそっくりの道をたどってきて、 そっくりの《宝箱》を見つけたのに、 開ける呪文が違うみたいですね……」

僕「《$p$ を法とする世界の平方数》がその呪文になるのかな……」

参考文献

• 雪江明彦『整数論1　初等整数論から $p$ 進数へ』
• 高木貞治『初等整数論講義 第2版』
• 結城浩『数学ガール／フェルマーの最終定理』