登場人物紹介
僕:数学が好きな高校生。
テトラちゃん:僕の後輩。好奇心旺盛で根気強い《元気少女》。
リサ:自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。
ある日の放課後。僕が高校の図書室に行くと、 テトラちゃんが一人で《カード》を眺めていた。
僕「テトラちゃん。それは村木先生の?」
テトラ「あっ、先輩! ……はい、そうです。 こんな《カード》をいただいてきました」
村木先生の《カード》
$$ \overbrace{(1+1)\cdots(1+1)}^n \bmod ({\underbrace{1+\cdots+1}_{n}}) $$
村木先生は僕たちの数学の教師。 ときどき僕たちに《カード》をくれる。 そこには数式が書かれていたり、問題が書かれていたり。
僕たちはそれをきっかけにして、自由に数学トークを楽しむのだ。
僕「これは、また思わせぶりな数式だなあ」
テトラ「思わせぶり?」
僕「そうだよ。何か不思議なものがあるみたいな雰囲気を盛り上げているけど、実は単純な式」
テトラ「はあ……でも、ちょっとおもしろそうじゃありません?」
僕「この式なんだけど、 $$ \overbrace{(1+1)\cdots(1+1)}^n \bmod ({\underbrace{1+\cdots+1}_{n}}) $$
$1+1 = 2$ で、それを $n$ 個掛ける。 $1$ を $n$ 個加える。 ということは、要するにこういう式を考えるってことだよね」「僕」のまとめ
$$ 2^n \bmod n $$
$n = 1,2,3,\ldots$
テトラ「まあ……そうなるんですよね、きっと」
僕「これでも十分シンプルなんだから、そう書けばいいのにね」
テトラ「$2^n \bmod n$ というのは《$2^n$ を $n$ で割ったときの余り》ですよね」
僕「そうだね。研究のセオリーとして《小さい $n$ で考える》をやってみようか」
テトラ「はい。 $n = 1$ のとき、この式は、 $$ 2^1 \bmod 1 $$ ということになります。《$2^1$ を $1$ で割ったときの余り》は $0$ でいいんですよね。 あまり《$1$ で割る》ということはやりませんけれど」
僕「うん。 $1$ で割ったときの余りはいつも $0$ だよね。整数を $1$ で割ったら、どんな整数でも割りきれるわけだから」
テトラ「ということは、 $$ 2^{1} \bmod {1} = 0 $$ になります」
僕「次に $n = 2$ のときを考えてみよう」
テトラ「$n = 2$ ということは、 $$ 2^2 \bmod 2 $$ ですが、 $2^2 = 4$ ですから、 $2$ で割った余りはやはり $0$ です」
僕「そうだね。 $2$ の倍数を $2$ で割るんだから余りは $0$ になる。 何も問題はないよ」
テトラ「$2^n \bmod n$ の値は、 $n = 1$ のときは $0$ で、 $n = 2$ のときも $0$ です。 ここにどんな意味があるんでしょう」
僕「もう少し進まなくちゃわからないね。《小さい $n$ で考える》のはいいけど、 小さすぎたら何だかよくわからない。 本の表紙をめくってすぐに《この本にどんな意味があるのか》って聞くようなものだから。 もう少し進もうよ」
テトラ「そうですよね。それでは $n = 3$ に進みます」
$$ 2^{3} \bmod {3} = 8 \bmod 3 = 2 $$僕「$8$ を $3$ で割ったら、余りは $2$ ……そうだね。 そうだ、二人で分担して計算しようか。テトラちゃんは奇数の $n$ を計算してみてよ。 僕は偶数の $n$ を計算するから」
テトラ「はいっ!」
こんなふうにして、僕たちは、 $$ 2^n \bmod n $$ を巡る冒険に出発した。 いったい、何が見つかるんだろう。
僕「偶数の $n$ だと、こうなったよ。 $6$ 以外は $0$ だね」
$$ \begin{array}{rll} 2^{2} \bmod {2} &= 4 \bmod 2 & = 0 \\ 2^{4} \bmod {4} &= 16 \bmod 4 & = 0 \\ 2^{6} \bmod {6} &= 64 \bmod 6 & = 4 \\ 2^{8} \bmod {8} &= 256 \bmod 8 & = 0 \\ \end{array} $$テトラ「奇数の $n$ は、こうなりました。 $1$ のほかは全部 $2$ です」
$$ \begin{array}{rll} 2^{1} \bmod {1} &= 2 \bmod 1 &= 0 \\ 2^{3} \bmod {3} &= 8 \bmod 3 &= 2 \\ 2^{5} \bmod {5} &= 32 \bmod 5 &= 2 \\ 2^{7} \bmod {7} &= 128 \bmod 7 &= 2 \\ \end{array} $$僕「へえ……規則性がありそうな、なさそうな、へんな感じだね。 $n = 9$ もやってみようか」
$$ \begin{array}{rll} 2^{9} \bmod {9} &= 512 \bmod 9 &= 8 \end{array} $$テトラ「あ、 $2$ になりませんね。 ということは、 $2^n \bmod n = 2$ にならない奇数もあるんですね。 $n = 9$ はだめということで、結果が $2$ になる $n$ は、いまのところ、 $n = 3, 5, 7$ だけで……」
僕「ちょっと待って。 $n = 11$ は?!」
テトラ「$n = 10$ を飛ばすんですか?」
僕「$2^{10} = 1024$ だから、 $2^{10} \bmod 10 = 4$ だってすぐわかるよ。 それより、 $n = 11$ を計算しようよ。おもしろくなってきた!」
テトラ「はい」
$$ \begin{array}{rll} 2^{11} \bmod {11} &= 2048 \bmod 11 &= 2 \end{array} $$僕「やっぱり」
テトラ「ちょっとお待ちください。表にしてみます」
$$ \begin{array}{c|ccccccccccccccccccccc} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline 2^n \bmod n & 0 & 0 & 2 & 0 & 2 & 4 & 2 & 0 & 8 & 4 & 2 \\ \end{array} $$僕「うん。ほら、 $2^n \bmod n = 2$ になる $n$ に印を付けてみよう!」
$$ \begin{array}{c|ccccccccccccccccccccc} n & 1 & 2 & \FBOX3 & 4 & \FBOX5 & 6 & \FBOX7 & 8 & 9 & 10 & \FBOX{11} \\ \hline 2^n \bmod n & 0 & 0 & 2 & 0 & 2 & 4 & 2 & 0 & 8 & 4 & 2 \\ & & &\UP& &\UP& &\UP& & & &\UP \\ \end{array} $$テトラ「$3,5,7,11$ ですね……えっ! もしかして素数? 素数ってことでしょうか。 $$ 2^n \bmod n = 2 $$ になるのは、 $n$ が素数のときっ!?」
僕「厳密には、奇素数かな。 $2$ を除くことになるから」
テトラ「もう少し、先まで確かめましょうよ!」
僕たちはどきどきしながら計算を進めた。
僕「……これは」
テトラ「すごいですっ! $13, 17, 19$ は素数ですよね。 そして、偶数はもちろんのこと、 $15, 21$ のような奇数もちょうど避けていくみたいに! 村木先生の《カード》 に書かれていた数式は《素数判定機》だったんですね!」
僕「素数判定機?」
テトラ「そうですよ。改めてちゃんと書きます。あたしたちの予想はこういうことですよね」
あたしたちの予想(素数判定機?)
$n$ を $3$ 以上の整数とする。 $$ 2^n \bmod n = 2 $$ が成り立つとき、 $n$ は素数である。
(そのように予想しましたっ!)
僕「うん……この予想はいいんだけど《素数判定機》というネーミングのためには、 もう少し考える必要があるよ、テトラちゃん」
テトラ「え? それはどういうことでしょうか」
僕「僕たちは $2^n \bmod n = 2$ という式を、 $n$ に関する条件だと見なしたわけだよね」
テトラ「そうですね。村木先生の《カード》から」
僕「話を簡単にするために、テトラちゃんが言ってたように、 $n$ は $3$ 以上の整数という前提にするよ。 そのとき、僕たちは二つの条件を考えているわけだ」
テトラ「二つ……」
僕「そうだよ。つまり、
テトラ「そうですが……」
僕「そして、二つの条件を考えるときには、 必要条件と十分条件について注意しなくちゃ」
$$ \begin{array}{ccc} \REMTEXT{《$2^n \bmod n = 2$》} & \Longrightarrow & \REMTEXT{《$n$は素数である》} \\ \REMTEXT{《$2^n \bmod n = 2$》} & \Longleftarrow & \REMTEXT{《$n$は素数である》} \\ \end{array} $$テトラ「……なるほどです。 あたしは思わず《素数判定機》といいましたが、 《素数判定機》というためには、この両方がいえなくてはいけないという意味でしょうか」
僕「そういうこと。 《$2^n \bmod n = 2$》ならば《$n$ は素数である》し、 逆に《$n$ は素数である》ならば《$2^n \bmod n = 2$》といえる。 そうなっているなら《素数判定機》の名前にふさわしいよね」
テトラ「さっきのあたしの書き方だと、 $$ \REMTEXT{《$2^n \bmod n = 2$》} \Longrightarrow \REMTEXT{《$n$は素数である》} $$ の方しか主張していなかったんですね。ではあらためて……」
あたしたちの予想(素数判定機)
$n$ を $3$ 以上の整数とする。
$$ 2^n \bmod n = 2 $$ が成り立つとき、 $n$ は素数である。
また逆に、 $n$ が素数であるとき、 $$ 2^n \bmod n = 2 $$ が成り立つ。
(そのように予想しましたっ!)
僕「うん……僕たちの《小さな $n$ で考える》方法だと、いまのところ $n = 3,4,5,\ldots,21$ については、 テトラちゃんのいう《素数判定機》が正しく動いているわけだね」
テトラ「でも、先輩がよくおっしゃいますけど、 証明をしなければ、これは確かめられませんよね。 いくら大きな $n$ で確かめても、整数は無数にあるわけですから、 確かめ尽くすことは絶対にできません」
僕「そうだね。特に《素数判定機の予想》が正しいときにはね」
テトラ「正しいときには?」
僕「$n$ をどんどん大きくして確かめて、どこかで《素数判定機》が成り立たない $n$ が見つかったとするよね。 その場合には、否定的に確かめられるわけだ。僕たちの予想はまちがっていたってね」
テトラ「ははあ……反例(はんれい)のことですね?」
僕「そういうこと。もしも《素数判定機の予想》が正しければ、 もちろん反例は存在しない。だから、いつまでたっても確かめ尽くすことはできない」
テトラ「正しければ、確かめ尽くすことはできないって、 何だか皮肉な……不思議な話ですね」
僕「うん。小さな $n$ で《素数判定機の予想》を立てた。 次の一歩は、この予想を証明してみることになるね」
テトラ「はいっ!」
テトラ「……とはいうものの、何をどうすることになりますか」
僕「僕もわからないけど、出発点は $2^n \bmod n = 2$ だから、 この式を研究してみることになるよね」
テトラ「はあ」
僕「たとえば……あくまで、たとえばなんだけど、 こんなふうに書き換えてみようか」
$$ 2^n \bmod n = 2 \Leftrightarrow 2^n \equiv 2 \pmod n $$テトラ「$2^n \equiv 2 \pmod n$ は《合同式》ですよね」
僕「そうそう。 $$ 2^n \bmod n = 2 $$ というのは、 《$2^n$ を $n$ で割ったときの余りは $2$ に等しい》を《等式》で表したもの。 そしてそれとまったく同じことを《合同式》で表すと、 $$ 2^n \equiv 2 \pmod n $$ になる。《$2^n$ は $n$ を法として $2$ と合同である》」
テトラ「はい……それはわかります。でも、こう書いたからといって、 何かわかることはあるんでしょうか」
僕「何がわかるかわからないから、試行錯誤してるんだけどね」
テトラ「そうでした……すみません」
僕「まあ、でも、こう書き換えたからといって……あれ? いやいやいや! すごいこと見つけたよ、 テトラちゃん!」
テトラ「はい?」
無料で「試し読み」できるのはここまでです。 この続きをお読みになるには「読み放題プラン」へのご参加が必要です。
ひと月500円で「読み放題プラン」へご参加いただきますと、 435本すべての記事が読み放題になりますので、 ぜひ、ご参加ください。
参加済みの方/すぐに参加したい方はこちら
結城浩のメンバーシップで参加 結城浩のpixivFANBOXで参加(2017年6月2日)