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

第397回 シーズン40 エピソード7
素数を法とする世界(前編)

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

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

登場人物紹介

:数学が好きな高校生。

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

$ \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{\BIFRAC}[3]{\frac{#1}{{#2}\SP{#3}}} \newcommand{\DBIFRAC}[3]{\displaystyle\BIFRAC{#1}{#2}{#3}} \newcommand{\LNOT}{\lnot} $

僕の部屋

ここは僕の部屋。いまは夜——いや、夜中だ。

授業の復習、課題の解決、テストの解き直し……そんな勉強が終わったら、 もうこんな時間になってしまった。

でも、ここからようやくの時間。自分の数学に取り組める時間だ。

今日の放課後。 図書室でテトラちゃんは、 パスカルの三角形組み合わせの数について考えていた(第395回参照)。

その中で、 組み合わせの数が持つおもしろい性質を証明したのだ(第396回参照)。

それは、こんな性質だ。(A)と呼ぶことにしよう。

(A)組み合わせの数の性質(証明済み)

$n$ は $2$ 以上の整数とする。

$n$ が素数ならば、 $0 < r < n$ を満たすすべての整数 $r$ について、 $$ \BINOM{n}{r} $$ は $n$ の倍数になる。

「瑞谷先生の『下校時間です』宣言が来てしまったから、 あの場ではそれ以上の探求はできなかったけれど、 気になることがある。 それはこの(A)のは成り立つか、ということだ。 (A)の逆の命題を(B)としよう」

(B)組み合わせの数の性質(Aの逆。未証明)

$n$ は $2$ 以上の整数とする。

$0 < r < n$ を満たすすべての整数 $r$ について、 $$ \BINOM{n}{r} $$ が $n$ の倍数ならば、 $n$ は素数である。

「テトラちゃんと二人でパスカルの三角形を作った範囲では、 (A)はもちろんのこと、(B)も成り立っているのを確かめた」

$n$ 行目の数で、両端の $1$ を除いたすべての数が $n$ の倍数になるのは、 $2,3,5,7,11$ 行目

「(A)と(B)の両方が成り立つというのはどういうことかというと、 《両端以外がすべて $n$ の倍数》と《$n$ は素数》とが同値だということだ。 僕たちが調べた $2 \LEQ n \LEQ 11$ という範囲に限れば、 《両端以外がすべて $n$ の倍数》なのは、 $$ n = 2,3,5,7,11 $$ であり、そしてそれはまさしく、 $2 \LEQ n \LEQ 11$ という範囲で《$n$ は素数》にほかならない。 でもそれは、あくまで $2 \LEQ n \LEQ 11$ というわずかな範囲で調べた結果に過ぎない。 整数は無数にある。素数も無数にある。 だから、(B)が成り立つことを言うためには——無限を出し抜くためには——証明がどうしても必要になるんだ」

「まだ起きてるの? あまり遅くまで根を詰めないで。睡眠重要よ」

「わかってるよ」

部屋の外からが出し抜けに声を掛けてきたのでは驚いた。 無限に立ち向かおうとしていたタイミングで、急に現実に引き戻された気分だ。

「ねえ、温かいハーブティでもいれる? ほっとしてよく眠れるわよ」

「いらない。いま忙しいんだけどな」

「はいはい。それじゃ、おやすみなさい」

「あ……うん、おやすみ。ありがとう」

つい、イラッとした口調で応対してしまったのを取り繕うように、 は母におやすみを言った。

それで——何を考えていたんだっけ。

証明だ。

「いきなり一般的な証明に取りかかる前に《小さな $n$ で確かめる》ことにしよう。 小さな $n$ で何を確かめるかというと……何を確かめるんだ?  証明する前には、証明したい命題をはっきりさせておく必要がある。 さもないと、どこに向かうかわからないまま、旅に出るような事態になるから。 注意深く考えていこう」

  • 《$n$ は素数である》を $P(n)$ とする。
  • 《$0 < r < n$ を満たす任意の整数 $r$ について、 $\BINOM{n}{r}$ は $n$ の倍数である》を $Q(n)$ とする。

「こんなふうに $P(n)$ と $Q(n)$ を定めると、(A)と(B)の違いがよくわかる」

  • (A)は「$2$ 以上の任意の整数 $n$ について、 $P(n)$ ならば $Q(n)$」で、
  • (B)は「$2$ 以上の任意の整数 $n$ について、 $Q(n)$ ならば $P(n)$」だ。

「うん。僕はいま(B)について調べたい。 だから《小さな $n$ で確かめる》というのは 小さな $n$ について、本当に《$Q(n)$ ならば $P(n)$》かどうかを確かめることになる。 そうやっていけば、(B)について具体的なイメージが浮かび、 理解が深まるはずだ」

はしばし考える。

そして、

  $Q(n)$ ならば $P(n)$

を考える代わりに、その対偶である、

  $\LNOT P(n)$ ならば $\LNOT Q(n)$

すなわち、

  $P(n)$ の否定が成り立つならば $Q(n)$ の否定が成り立つ

を考えた方がいいと気が付いた。

「なぜ対偶を考えた方がいいかというとね、テトラちゃん——って、ここにはいないけど」

最近のは、テトラちゃんに話しかけるように考えることが多くなってきている。 そうすると、なぜか考えが整理されるからだ。

「なぜ対偶を考えるか。 ある命題とその対偶となる命題は同値になる。 だから、どちらを証明してもいい。 証明したい命題(B)の対偶は、

  $2$ 以上の任意の整数 $n$ について、 $\LNOT P(n)$ ならば $\LNOT Q(n)$

になる。 $\LNOT P(n)$ は《$n$ は素数ではない》ということだから、 $n \GEQ 2$ であることを考えると、 $n$ は二つ以上の素数の積で表せる数になる。すなわち《$n$ は合成数》だ」

  • $\LNOT P(n)$ は《$n$ は合成数》ということ。

「だから、合成数の $n$ を具体的に用意してやれば、 $$ \BINOM{n}{1}, \BINOM{n}{2}, \BINOM{n}{3}, \ldots, \BINOM{n}{n-1} $$ の中には《$n$ の倍数じゃないもの》が少なくとも一つあることが予想される。 そして、小さな合成数 $n$ を具体的に考えれば、 そのような《$n$ の倍数ではない $\BINOM{n}{r}$》もまた、 具体的に見つけることができる。 そのような、 $$ \text{$n$の倍数ではない}\,\BINOM{n}{r} $$ が証明のカギになるはずだ」

そこまで考えたところで、 の心の中にいるテトラちゃんがこんな疑問を提示してきた。

テトラ「どうしてそれが証明のカギになるのか、まだよくわかりません」

そこで、は心の中のテトラちゃんに答えることになる。

「だって、もしも $\BINOM{n}{r}$ のすべてが $n$ の倍数になったら、 そのときの $n$ は(B)に対する反例となるからだよ。 いま僕は(B)が成り立つと予想しているから、 《$n$ の倍数ではない $\BINOM{n}{r}$》 の存在に注目したい。 それは証明を導くために重要な特徴を持っているはずなんだ——よし、 小さな合成数 $n$ で実験しよう!」

$n = 4$ の場合

「$2$ と $3$ は素数だから、最小の合成数は $4$ だ。 $\BINOM{4}{r}$ が $4$ の倍数にならないものを見つけていく」

$n = 4, r = 1$

$$ \BINOM{n}{r} = \BINOM{4}{1} = \frac{4}{1} = 4 \qquad \TEXT{$4$の倍数だ。パス。} $$ $n = 4, r = 2$

$$ \BINOM{n}{r} = \BINOM{4}{2} = \frac{\CANCEL{4}^2\times3}{\CANCEL{2}\times1} = 6 \qquad \TEXT{$4$の倍数じゃない。注目!} $$

$n = 6$ の場合

「$5$ は素数だから、次の合成数は $6$ だ。 $\BINOM{6}{r}$ が $6$ の倍数にならないものに注目する」

$n = 6, r = 1$

$$ \BINOM{n}{r} = \BINOM{6}{1} = \frac{6}{1} = 6 \qquad \TEXT{$6$の倍数だ。パス。} $$ $n = 6, r = 2$

$$ \BINOM{n}{r} = \BINOM{6}{2} = \frac{\CANCEL{6}^3\times5}{\CANCEL{2}\times1} = 15 \qquad \TEXT{$6$の倍数じゃない。注目!} $$

$n = 8$ の場合

「$7$ は素数だから、次の合成数は $8$ だ。 $\BINOM{8}{r}$ が $8$ の倍数にならないものに注目する」

$n = 8, r = 1$

$$ \BINOM{n}{r} = \BINOM{8}{1} = \frac{8}{1} = 8 \qquad \TEXT{$8$の倍数だ。パス。} $$ $n = 8, r = 2$

$$ \BINOM{n}{r} = \BINOM{8}{2} = \frac{\CANCEL{8}^4\times7}{\CANCEL{2}\times1} = 28 \qquad \TEXT{$8$の倍数じゃない。注目!} $$

$n = 9$ の場合

「次の合成数は $9$ だ。 $\BINOM{9}{r}$ が $9$ の倍数にならないものに注目する」

$n = 9, r = 1$

$$ \BINOM{n}{r} = \BINOM{9}{1} = \frac{9}{1} = 9 \qquad \TEXT{$9$の倍数だ。パス。} $$ $n = 9, r = 2$

$$ \BINOM{n}{r} = \BINOM{9}{2} = \frac{9\times\CANCEL{8}^4}{\CANCEL{2}\times1} = 36 \qquad \TEXT{おっ、これも$9$の倍数だ。パスか……} $$ $n = 9, r = 3$

$$ \BINOM{n}{r} = \BINOM{9}{3} = \frac{\CANCEL{9}^3\times\CANCEL{8}^4\times7}{\CANCEL{3}\times\CANCEL{2}\times1} = 84 \qquad \TEXT{$9$の倍数じゃない。注目!} $$

「なるほど、なるほど!  $n$ が合成数のときに、 $\BINOM{n}{r}$ の中には確かに、 $n$ の倍数じゃないものが存在する。それは、小さな合成数 $n$ で実験した結果、 $$ \begin{align*} \BINOM{4}{2} &= \frac{\CANCEL{4}^2\times3}{\CANCEL{2}\times1} \\ \BINOM{6}{2} &= \frac{\CANCEL{6}^3\times5}{\CANCEL{2}\times1} \\ \BINOM{8}{2} &= \frac{\CANCEL{8}^4\times7}{\CANCEL{2}\times1} \\ \BINOM{9}{3} &= \frac{\CANCEL{9}^3\times\CANCEL{8}^4\times7}{\CANCEL{3}\times\CANCEL{2}\times1} \end{align*} $$ に注目してはっきりわかった。うん、読み切ったぞ! きっと $\BINOM{49}{7}$ は $49$ の倍数じゃないはずだ。 $$ \BINOM{49}{7} = \frac{\CANCEL{49}^7\times48\times47\times46\times45\times44\times43}{\CANCEL{7}^1\times6\times5\times4\times3\times2\times1} $$ $48$ から $43$ までの間に $7$ の倍数はないから、 $\BINOM{49}{7}$ は確かに $49$ の倍数ではない。 よーしよし! これで(B)を証明できる!」

(B)組み合わせの数の性質(Aの逆、未証明)(再掲)

$n$ は $2$ 以上の整数とする。

$0 < r < n$ を満たすすべての整数 $r$ について、 $$ \BINOM{n}{r} $$ が $n$ の倍数ならば、 $n$ は素数である。

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

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


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

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

(2023年6月30日)

[icon]

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


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

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