第197回 シーズン20 エピソード7

エヌを巡る冒険（前編）

図書館にて

僕「テトラちゃん。それは村木先生の？」

テトラ「あっ、先輩！　……はい、そうです。 こんな《カード》をいただいてきました」

僕「これは、また思わせぶりな数式だなあ」

テトラ「思わせぶり？」

僕「そうだよ。何か不思議なものがあるみたいな雰囲気を盛り上げているけど、実は単純な式」

テトラ「はあ……でも、ちょっとおもしろそうじゃありません？」

式をまとめる

僕「この式なんだけど、 $$ \overbrace{(1+1)\cdots(1+1)}^n \bmod ({\underbrace{1+\cdots+1}_{n}}) $$

$1+1 = 2$ で、それを $n$ 個掛ける。 $1$ を $n$ 個加える。 ということは、要するにこういう式を考えるってことだよね」

テトラ「まあ……そうなるんですよね、きっと」

僕「これでも十分シンプルなんだから、そう書けばいいのにね」

小さい $n$ で考える

テトラ「$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$ を計算するから」

テトラ「はいっ！」

僕「偶数の $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$ を除くことになるから」

テトラ「もう少し、先まで確かめましょうよ！」

$$ \begin{array}{c|ccccccccccccccccccccc} n & 12 &\FBOX{13}& 14 & 15 & 16 &\FBOX{17}& 18 &\FBOX{19}& 20 & 21 \\ \hline 2^n \bmod n & 4 & 2 & 4 & 8 & 0 & 2 & 10 & 2 & 16 & 8 \\ & &\UP & & & & \UP & &\UP & & \\ \end{array} $$

僕「……これは」

テトラ「すごいですっ！　 $13, 17, 19$ は素数ですよね。 そして、偶数はもちろんのこと、 $15, 21$ のような奇数もちょうど避けていくみたいに！　村木先生の《カード》 に書かれていた数式は《素数判定機》だったんですね！」

僕「素数判定機？」

テトラ「そうですよ。改めてちゃんと書きます。あたしたちの予想はこういうことですよね」

僕「うん……この予想はいいんだけど《素数判定機》というネーミングのためには、 もう少し考える必要があるよ、テトラちゃん」

テトラ「え？　それはどういうことでしょうか」

僕「僕たちは $2^n \bmod n = 2$ という式を、 $n$ に関する条件だと見なしたわけだよね」

テトラ「そうですね。村木先生の《カード》から」

僕「話を簡単にするために、テトラちゃんが言ってたように、 $n$ は $3$ 以上の整数という前提にするよ。 そのとき、僕たちは二つの条件を考えているわけだ」

テトラ「二つ……」

僕「そうだよ。つまり、

• 《$2^n \bmod n = 2$》という条件
• 《$n$ は素数である》という条件

この二つだね」

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

僕「そして、二つの条件を考えるときには、 必要条件と十分条件について注意しなくちゃ」

$$ \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$ で考える》方法だと、いまのところ $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$ と合同である》」

テトラ「はい……それはわかります。でも、こう書いたからといって、 何かわかることはあるんでしょうか」

僕「何がわかるかわからないから、試行錯誤してるんだけどね」

テトラ「そうでした……すみません」

僕「まあ、でも、こう書き換えたからといって……あれ？　いやいやいや！　すごいこと見つけたよ、 テトラちゃん！」

テトラ「はい？」