[logo] Web連載「数学ガールの秘密ノート」
Share

第400回 シーズン40 エピソード10
パターンを見出すために(後編)

『数学ガールの秘密ノート/数を作ろう』好評発売中!

『数学ガールの秘密ノート/数を作ろう』をアマゾンで見る

登場人物紹介

:数学が好きな高校生。

テトラちゃんの後輩。 好奇心旺盛で根気強い《元気少女》。言葉が大好き。

ミルカさん:数学が好きな高校生。 のクラスメート。長い黒髪の《饒舌才媛》。

$ \definecolor{CUD-GREEN}{rgb}{0.012,0.686,0.478}% 3,175,122 \newcommand{\TEXT}[1]{\textbf{#1}} \newcommand{\REMTEXT}[1]{\textbf{#1}} \newcommand{\FOCUS}[1]{\fbox{ $#1$ }} \newcommand{\MARK}[1]{\textcolor{red}{#1}} \newcommand{\MARKA}[1]{\textcolor{red}{#1}} \newcommand{\MARKB}[1]{\textcolor{blue}{#1}} \newcommand{\MARKC}[1]{\textcolor{CUD-GREEN}{#1}} \newcommand{\CANCEL}[1]{\textcolor{red}{\cancel{\textcolor{black}{#1}}}} \newcommand{\COMBI}[2]{{}_{#1}\mathrm{C}_{#2}} \newcommand{\BINOM}[2]{\binom{#1}{#2}} \newcommand{\TBINOM}[2]{\textstyle\binom{#1}{#2}} \newcommand{\DBINOM}[2]{\displaystyle\binom{#1}{#2}} \newcommand{\GEQ}{\geqq} \newcommand{\LEQ}{\leqq} \newcommand{\SP}{\,\,} \newcommand{\ABS}[1]{\left|#1\right|} \newcommand{\SP}{\,\,} \newcommand{\BIFRAC}[3]{\frac{#1}{{#2}\SP{#3}}} \newcommand{\BIFX}[3]{\BIFRAC{#1!}{#2!}{#3!}} $

図書室にて

《数学トーク》にミルカさんが加わった。

ミルカさんが提示した $$ a^p \equiv a \pmod p $$ という式を巡る問いにテトラちゃんが答えている(第399回参照)。

テトラ「いえ、あの、混乱といいますか……《小さな数で試す》ことをいくら繰り返したとしても、 つまり、 $$ a = 1, 2, 3, 4, 5, \ldots $$ と続けていったとしても、 証明にはなりませんよね。正の整数は無数にあるんですから」

ミルカ「もちろん。だが、《小さな数で試す》ことによって、 テトラはもう $a^p \equiv a \pmod p$ という式と《お友達》になっただろう?」

テトラ「あ……はい、それはそうですね。 $a$ を $p$ 乗したらぐるっと回って $a$ に戻ります」

ミルカ「そして私たちは $a = 1,2,3,4,5, \ldots$ のすべてについて証明する方法をよく知っている」

テトラ「証明する方法——それは、あたしも知っているんですか?」

ミルカ「テトラも知っている。 すべての正の整数 $a$ について何かを証明せよと言われたときに、いつも使っている方法だから。 テトラは、それを知っているはずだ」

テトラ「……もしかして、数学的帰納法ですか?」

ミルカ「その通り」

問題(再掲)

$p$ を正の素数とし、 $a$ を正の整数とする。 このとき、 $$ a^p \equiv a \pmod p $$ が成り立つことを証明せよ。

テトラ「これを、数学的帰納法で証明する……?」

「おおおおお……そうつながるのか! 確かにそれはおもしろい!」

テトラ「ま、まだ答えないでください!」

「わかった。いまはまだ頭の中だけで考えることにするよ」

テトラ「数学的帰納法——はい、いま思い出しました……基本的なところから復習させてください。 $a$ がどんな正の整数でも $a^p \equiv a \pmod p$ が成り立つことを証明するんですが、 数学的帰納法というのは二つのステップで証明するんですよね」

「……」

ミルカ「……」

テトラ「で、ですよね?」

ミルカ「続けて」

テトラ「はい……はい、大丈夫です。 $a$ が $1,2,3,\ldots$ のときに成り立つことを証明するための二つのステップというのは——

  • ステップA: $a = 1$ のときに成り立つ。
  • ステップB: $a = n$ のときに成り立つならば、 $a = n + 1$ のときにも成り立つ。
——のステップAとステップBのことです。この二つがいえれば、 ちょうどドミノ倒しのようにすべての正の整数 $a$ について成り立つことが証明できます。

  • ステップAは《最初のドミノを倒すこと》に相当して、
  • ステップBは《$n$ 番目のドミノが倒れたならば、必ず $n+1$ 番目のドミノが倒れること》に相当します。
これが数学的帰納法での証明です」

ミルカ「それでいい」

テトラ「ということは……はい、ステップAに関しては、あたしも証明できます。 $a^p \equiv a \pmod p$ で、 $a = 1$ のときですから、 $$ 1^p \equiv 1 \pmod p $$ が成り立つことを言えばいいんですが、 $1$ の $p$ 乗は $1$ に等しいですから、 $1^p$ を $p$ で割った余りはもちろん $1$ に等しくなります。 ですから、素数 $p$ を法として $1^p$ と $1$ は合同になります」

「ステップAが証明できたね」

テトラ「はい。でも……数学的帰納法ってたいていはステップAはとっても易しくて、 ステップBがとっても難しいのが普通です。違いますか?」

「確かに」

ミルカ「言いたいことはわかるが、数学をしよう」

テトラ「あ、はい、そうですね。ステップBでは 《$n$ 番目のドミノが倒れたならば、必ず $n+1$ 番目のドミノが倒れること》 を証明するので、まず $n$ 番目について考えます。 $a = n$ のときに成り立つんですよね?」

「それは仮定だからね」

テトラ「え?」

ミルカ「何が仮定で何が結論なのかをはっきりさせないと」

テトラ「あっ、はい。ステップBはこう……ですか?」

  • 仮定は、 $a = n$ のとき $a^p \equiv a \pmod p$ が成り立つ。
  • 結論は、 $a = n+1$ のとき $a^p \equiv a \pmod p$ が成り立つ。

ミルカ「そうだ。しかし、その記述では注意が必要だ。 いまテトラが書いた仮定と結論に同じ文字 $a$ が出てきているが、これは違うものを表している。 だから、混乱しないように書き換えよう」

  • 仮定: $n^p \equiv n \pmod p$
  • 結論: $(n+1)^p \equiv n+1 \pmod p$

テトラ「……ああ、確かにそうですね。 ではあとは、 仮定から結論を導く。つまり、 $n^p \equiv n \pmod p$ を変形して $(n+1)^p \equiv n+1 \pmod p$ を導けばいい——んでしょうか?」

「そういうときもあるけれど、数学帰納法でよくあるのは、 《結論》の式を変形していって、どこかカギになる段階で《仮定》をスッと利用するというやり方だね。 とにかく《結論》を導きたいんだから、そこの式をいじるところからスタートするんだ」

ミルカ「やみくもに式をいじるのもどうかと思うが、今回はそれでいける」

テトラ「なるほど……? ああ、はいはいはいはいっ、 そうでしたそうでした。あたしたちには素数 $p$ を法とする世界の二項定理があるんでしたっ! それを使えば、素数 $p$ を法とする世界で、 $$ (n + 1)^p $$ をきれいに展開できますね!」

定理 $\heartsuit$ (素数 $p$ を法とする世界の二項定理、証明済み)

正の素数 $p$ に対して、 $$ (x + y)^p \equiv x^p + y^p \pmod p $$ が成り立つ。 (第399回参照

「そうそう!」

テトラ「あ……あたしが展開してもいいですよね?」

「もちろん。どうぞどうぞ」

テトラ「この定理 $\heartsuit$ で $x = n, y = 1$ とすれば、 $$ (n + 1)^p \equiv n^p + 1^p \pmod p $$ が成り立ちます。つまり、 $$ (n + 1)^p \equiv n^p + 1 \pmod p $$ です! これで証明が——あらら? 右辺が $n^p + 1$ ですね……」

「いまがカギになる段階だよ、テトラちゃん!」

もどかしくなったは、つい口を出してしまった。

テトラ「ああっ、そうでした。仮定のことを忘れていました。仮定は、 $$ n^p \equiv n \pmod p $$ ですから、これを使えば、 $n^p + 1$ は $n + 1$ に $p$ を法として合同です!」

ミルカ「まとめよう」

テトラ「はいっ!」

解答

命題

$p$ を正の素数とし、 $a$ を正の整数とする。 このとき、 $$ a^p \equiv a \pmod p $$ が成り立つ。

証明

$a$ に関して数学的帰納法を用います。

(ステップA)$1^p = 1$ なので、 $$ 1^p \equiv 1 \pmod p $$ が成り立ちます。

(ステップB)$n^p \equiv n \pmod p$ であると仮定します。 定理 $\heartsuit$ により、 $$ \begin{align} (n + 1)^p &\equiv n^p + 1^p \pmod p \\ &\equiv n^p + 1 \pmod p \end{align} $$ が成り立ちます。仮定より $n^p \equiv n \pmod p$ なので、 $$ (n+1)^p \equiv n + 1 \pmod p $$ が成り立ちます。

ステップAとステップBから、 数学的帰納法により、すべての正の整数 $a$ について、 $$ a^p \equiv a \pmod p $$ が成り立ちます。

(証明終わり)

テトラ「はいっ! これで、ひと仕事おしまいっ!……ですね?」

テトラちゃんミルカさんの決め台詞を宣言した。

ミルカ「決め台詞は、もう一歩だけ進んでからだな」

「フェルマーの小定理だね! $p$ を正の素数とし、 $a$ を正の整数としたとき、 $$ a^p \equiv a \pmod p $$ が成り立つことが示された。 さらにここで、 $a$ と $p$ の最大公約数が $1$ のとき、つまり $a$ と $p$ が互いに素のとき、 この合同式の両辺を $a$ で割ることができるので、 $$ a^{p-1} \equiv 1 \pmod p $$ が成り立つ。これこそ、フェルマーの小定理!」

フェルマーの小定理(再掲)

$p$ を正の素数とし、正の整数 $a$ は $p$ と互いに素とする。 このとき、 $$ a^{p-1} \equiv 1 \pmod p $$ が成り立つ。

ミルカ「はい、これで、ひと仕事おしまい」

僕の部屋にて

「……というふうに証明は進んだんだよ、ユーリ」

ユーリ「『はい、これで、ひと仕事おしまい!』 くううっ! かっこいー! ユーリもミルカさまのそばにいたかったよー! 何でユーリだけ、 図書室にいないんだよー!」

ここはの部屋。いまは土曜日。

ユーリがやってきたので、 は、素数 $p$ を法とする世界の二項定理の話と、 フェルマーの小定理の話をしたところだ。

登場人物紹介

ユーリのいとこの中学生。 のことを《お兄ちゃん》と呼ぶ。 論理的な話は好きだが飽きっぽい。

「ミルカさんの話——というか、数学の展開はおもしろかった」

ユーリ「えーん、つまんないよー!」

「大丈夫。ちゃんとミルカさんから《おみやげ》をもらってきたから」

ユーリ「ミルカさまからの《おみやげ》って何? チョコレート? わかった、キットカットだ!」

「六角形だよ」

ユーリ「ろっかてい? 六花亭のチョコ?」

「ユーリ、ユーリ。いったんチョコレートから離れようか。《パスカルの三角形》の中にある六角形だよ」

ユーリ「は?」

《パスカルの三角形》の中にある六角形

「パスカルの三角形って、こういうものだね」

僕は、手元のA4コピー用紙にパスカルの三角形を書いた。

無料で「試し読み」できるのはここまでです。 この続きをお読みになるには「読み放題プラン」へのご参加が必要です。

ひと月500円で「読み放題プラン」へご参加いただきますと、 439本すべての記事が読み放題になりますので、 ぜひ、ご参加ください。


参加済みの方/すぐに参加したい方はこちら

結城浩のメンバーシップで参加 結城浩のpixivFANBOXで参加

(2023年7月21日)

[icon]

結城浩(ゆうき・ひろし) @hyuki


『数学ガール』作者。 結城メルマガWeb連載を毎週書いてます。 文章書きとプログラミングが好きなクリスチャン。2014年日本数学会出版賞受賞。

Twitter note 結城メルマガ Mastodon Bluesky Threads Home