第197回 エヌを巡る冒険(前編)

「この不思議な式を研究したら、どんなものが出てくるんでしょうか?」とテトラちゃんは素朴な疑問を投げかけた。「整数に誘われて」シーズン第4章前編。
登場人物紹介

:数学が好きな高校生。

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

リサ:自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。

$ \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\HIRANO}{\unicode[sans-serif,STIXGeneral]{x306E}} \newcommand{\UL}[1]{\underline{#1}} \newcommand{\FBOX}[1]{\fbox{$#1$}} \newcommand{\GEQ}{\geqq} \newcommand{\LEQ}{\leqq} \newcommand{\UP}{\uparrow} $

図書館にて

ある日の放課後。が高校の図書室に行くと、 テトラちゃんが一人で《カード》を眺めていた。

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

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

村木先生の《カード》

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

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

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

小さい$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$を計算するから」

テトラ「はいっ!」

こんなふうにして、僕たちは、 $$ 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$を除くことになるから」

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

僕たちはどきどきしながら計算を進めた。

$$ \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$のような奇数もちょうど避けていくみたいに! 村木先生の《カード》 に書かれていた数式は《素数判定機》だったんですね!」

「素数判定機?」

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

あたしたちの予想(素数判定機?)

$n$を$3$以上の整数とする。 $$ 2^n \bmod n = 2 $$ が成り立つとき、$n$は素数である。

(そのように予想しましたっ!)

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

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

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

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

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

テトラ「二つ……」

「そうだよ。つまり、

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

この二つだね」

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

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

$$ \begin{array}{ccc} \text{《$2^n \bmod n = 2$》} & \Longrightarrow & \text{《$n$は素数である》} \\ \text{《$2^n \bmod n = 2$》} & \Longleftarrow & \text{《$n$は素数である》} \\ \end{array} $$

テトラ「……なるほどです。あたしは思わず《素数判定機》といいましたが、 《素数判定機》というためには、この両方がいえなくてはいけないという意味でしょうか」

「そういうこと。《$2^n \bmod n = 2$》ならば《$n$は素数である》し、 逆に《$n$は素数である》ならば《$2^n \bmod n = 2$》といえる。 そうなっているなら《素数判定機》の名前にふさわしいよね」

テトラ「さっきのあたしの書き方だと、$$ \text{《$2^n \bmod n = 2$》} \Longrightarrow \text{《$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$と合同である》」

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

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

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

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

テトラ「はい?」

この続きは有料会員登録をすると
読むことができます。
cakes会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の中高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わいましょう。本シリーズはすでに12巻も書籍化されている大人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

yuko88551 〔コラム〕 2年以上前 replyretweetfavorite

chibio6 式の変形が難しかったけれど何とか理解。命題「2^nのnが素数なら余りは2になる」の逆に反例が出てきてしまったが、それはなぜか。次回が気になる。 2年以上前 replyretweetfavorite

yuko88551 〔コラム〕 2年以上前 replyretweetfavorite

tks564bys 【コラム】 2年以上前 replyretweetfavorite