第399回シーズン40 エピソード9

パターンを見出すために（前編）

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

登場人物紹介

僕：数学が好きな高校生。

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

$ \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|} $

図書室にて

ミルカ「……それでだ。素数 $p$ を法とする世界での二項定理を考えたくなる。特に $(x + y)^p$ の場合に注目しよう」

僕「お、おおっ？！」

定理

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

僕とテトラちゃんは、ミルカさんが書いた式を凝視した（第398回参照）。

テトラ「……ああああああっ！　これは、確かに成り立ちますっ！　あたし、わかっちゃいました。だって、ここにある $1$ だけが生き残りますからっ！」

テトラちゃんは両腕をまた伸ばして、握った両手をぶんぶんと振る。

うん、確かにそうだ！　素数 $p$ を法とする世界では、テトラちゃんが両手に持った $\BINOM{p}{0}$ と $\BINOM{p}{p}$ だけが生き残る。確かにそうだ。しかも、 $1$ として。なぜなら——

僕「うん、なぜなら——」

テトラ「なぜなら、両端に出てくる $1$ は $p$ で割り切れませんが、そのあいだに出てくる $\BINOM{p}{r}$ はすべて、すべて！ $p$ で割り切れますから——ですよね？　あたしの考えは正しいですよね、ミルカさん？」

ミルカ「ふむ。《テトラの考え》が正しいかどうかを判断するためには、まず、その《テトラの考え》を提示しなければならないな」

ミルカさんはそう言いながら、テトラちゃんの前にあるノートを指さした。

テトラ「あ、そ、そうですね。確かにそうです。きちんと書かなければ、正しいかどうか判定できませんよね。ではっ、テトラ、書きますっ！」

僕「……」

なるほど、と僕は思った。

確かにミルカさんの言う通りだ。

僕はもうさっきの定理の証明が《わかった》と思う。

なぜなら、これまで考えてきたことを組み合わせるだけだからだ。

でも、それが本当にそうなのか。本当に正しいかどうかは、実際にきちんと書いてみなければわからない。しっかり吟味するためには、どうしても証明の形に書いてみなければならないのだ。

テトラ「まず、あたしたちがよく知っているところから始めます。素数 $p$ を法とする世界ではなく、普通の二項定理からです。二項定理はよくわかっています。 $p$ を素数として $(x + y)^p$ を展開すると、次のようになります。この展開では、特に $p$ が素数であることは使っていません」

二項定理で $(x + y)^p$ を展開する（$p$ は正の素数）

$$ (x + y)^p = \sum_{r = 0}^{p}\BINOM{p}{r}x^{p-r}y^{r} $$

ミルカ「ふむ」

テトラ「右辺にはシグマ（$\sum$）が出てきて、ちょっぴり恐いんですけれど、でも、実際には恐くありません。だってこれは単に $p$ 個の項の足し算だからですっ！」

ミルカ「$p + 1$ 個」

テトラ「え？　……そうですね。 $r$ が $0$ から始まって、 $p$ までですから、右辺は単に $p + 1$ 個の項の足し算になりますっ！　具体的にはこうです」

$$ \underbrace{\BINOM{p}{0}x^{p}y^0}_{r = 0} + \underbrace{\BINOM{p}{1}x^{p-1}y^1}_{r = 1} + \cdots + \underbrace{\BINOM{p}{p-1}x^{1}y^{p-1}}_{r = p-1} + \underbrace{\BINOM{p}{p}x^{0}y^p}_{r = p} $$

ミルカ「合ってる？」

テトラ「んー……はい、合ってます。各項のパターンをチェックしました。各項は $$ \BINOM{p}{r}x^{p-r}y^r $$ という形ですから、 $r$ が $0$ から $p$ まで動くと——

$\BINOM{p}{r}$ の $r$ は $0$ から $p$ まで動き、
$x^{p-r}$ の $p - r$ は $p$ から $0$ まで逆に動き、
$y^{r}$ の $r$ は $0$ から $p$ まで動く。

——ということになっています。いいですよね？」

ミルカ「それでいい。ついでにいえば、 $x^{p-r}$ の指数 $p-r$ と、 $y^{r}$ の指数 $r$ の和が、どの項についても $p$ になっているな」

テトラ「はい、そうですね。 $$ \BINOM{p}{0}x^{\MARKA{p}}y^{\MARKB{0}} + \BINOM{p}{1}x^{\MARKA{p-1}}y^{\MARKB{1}} + \cdots + \BINOM{p}{p-1}x^{\MARKA{1}}y^{\MARKB{p-1}} + \BINOM{p}{p}x^{\MARKA{0}}y^{\MARKB{p}} $$ で、 $$ \begin{array}{ccccl} \MARKA{p} &+& \MARKB{0} &=& p \\ \MARKA{(p-1)} &+& \MARKB{1} &=& p \\ \vdots & & \vdots & & \vdots \\ \MARKA{1} &+& \MARKB{(p - 1)} &=& p \\ \MARKA{0} &+& \MARKB{p} &=& p \end{array} $$ になっています」

ミルカさんがうなずき、テトラちゃんもうなずいた。

テトラちゃんは、ちゃんと《わかって》式を書いているなあ。文字が多くなると、うっかりミスも増える。だから、ミスを防ぐためには、書いている途中で細かくチェックする必要がある。

テトラちゃんはチェックするポイントを押さえて式を書いている。

ミルカ「それで？」

テトラ「はい、それでですね、この $p + 1$ 個の項のうち、 $r = 0$ に対応する項と、 $r = p$ に対応する項の係数はどちらも $1$ になります。つまり、こういうことです」

$$ \begin{align*} \MARKA{\BINOM{p}{p}}x^py^0 &= \MARKA{1}x^py^0 = x^p \\ \MARKA{\BINOM{p}{0}}x^0y^p &= \MARKA{1}x^0y^p = y^p \end{align*} $$

テトラちゃんは両手を握りしめてそう言った。

やっぱり、両手に握ってたのは $\BINOM{p}{0}$ と $\BINOM{p}{p}$ だったんだな。

ミルカ「ふむ」

テトラ「すると残りの項は $r$ が $0 < r < p$ の場合ということですけれど、その場合はすべての項の係数は $p$ の倍数になります。なぜかというと、 $p$ が素数なら $0 < r < p$ を満たす任意の整数 $r$ について $\BINOM{p}{r}$ は $p$ の倍数だからです。これはもう証明しました（第396回参照）」

僕「うんうん！」

テトラ「つまり、こうなって……」

$$ \begin{align*} (x + y)^p & = \sum_{r = 0}^{p}\BINOM{p}{r}x^{p-r}y^{r} \\ & = \underbrace{\BINOM{p}{0}x^{p}y^0}_{r = 0} + \underbrace{\BINOM{p}{1}x^{p-1}y^1}_{r = 1} + \cdots + \underbrace{\BINOM{p}{p-1}x^{1}y^{p-1}}_{r = p-1} + \underbrace{\BINOM{p}{p}x^{0}y^p}_{r = p} \\ & = x^p + \underbrace{ \fbox{$ \BINOM{p}{1}x^{p-1}y^1 + \cdots + \BINOM{p}{p-1}x^{1}y^{p-1} $} }_{0 < r < p} + y^p \end{align*} $$

ミルカ「……」

テトラ「この四角で囲った部分の係数はすべて《$p$ の倍数》です。 $p$ の倍数は、素数 $p$ を法として $0$ と合同ですから、 $$ (x + y)^p \equiv x^p + y^p \pmod p $$ が成り立つことになります！」

ミルカ「パーフェクト」

証明

$p$ を正の素数とする。このとき、 $$ \BINOM{p}{r} \equiv \begin{cases} 1 \pmod p & \TEXT{$r = 0$の場合} \\ 0 \pmod p & \TEXT{$0 < r < p$の場合} \\ 1 \pmod p & \TEXT{$r = p$の場合} \end{cases} $$ である。これを使って $(x + y)^p$ を展開すると、 $$ \begin{align*} (x + y)^p &= \sum_{r = 0}^{p}\BINOM{p}{r} x^{p-r}y^{r} \\ &\equiv \BINOM{p}{0}x^py^0 + \sum_{r = 1}^{p-1}\BINOM{p}{r}x^{p-r}y^{r} + \BINOM{p}{p}x^0y^p \pmod p \\ &\equiv x^p + y^p \pmod p \end{align*} $$ なので、 $$ (x + y)^p\equiv x^p + y^p \pmod p $$ が成り立つ。（証明終わり）

僕「おもしろいねえ！」

式の観察

ミルカ「ところで、君はどこがおもしろいと思った？」

ミルカさんが急に僕の方を向いたので、ちょっと驚いた。

僕「え、いや。この定理そのものだよ。素数 $p$ を法とすると、 $(x + y)^p$ が $x^p + y^p$ のようなシンプルな結果になることがおもしろいと思ったんだ。だって $p$ が素数なら、いくら大きくてもいいわけだよね。たとえば、 $$ (x + y)^{9973} \equiv x^{9973} + y^{9973} \pmod{9973} $$ になる」

テトラ「$9973$ って素数なんですか」

僕「確か $4$ 桁に収まる最大の素数だよ」

ミルカ「十進法の位取り記数法に依存した概念」

僕「まあそうだけどさ」

テトラ「ミルカさんは、 $$ (x + y)^p \equiv x^p + y^p \pmod p $$ を見るとどこがおもしろいと感じるんですか」

ミルカ「一つは、交換可能性かな」

テトラ「交換……可能性？　何と何が交換できるんでしょう」

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

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

読み放題プランへのご参加について

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

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