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

第197回 シーズン20 エピソード7
エヌを巡る冒険(前編)

登場人物紹介

:数学が好きな高校生。

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

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

$ \newcommand{\REMTEXT}[1]{\textbf{#1}} \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \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} \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日)

[icon]

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


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

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