第198回 エヌを巡る冒険(後編)

「インダクションの発見前夜」とミルカさんは言った。「整数に誘われて」シーズン第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} $

図書室にて

テトラちゃんは、 $$ 2^{n} \equiv 2 \pmod n $$ という式について議論をしていた。$n$は$2$以上の整数だ。 この式は、

$2^n$と$2$とは、$n$で割ったときの余りが等しい

ことを表している。

おどろくべきことに、$n$に小さな素数$2,3,5,7,11$などを代入してみると、この式は成り立つ。

そして、$n$に小さな合成数$4,6,8,9,10$などを代入してみると、この式は成り立たない。

もしかしたら、 この式は$n$が素数か否かを判定する《素数判定機》なのだろうか? コンピュータ少女のリサがプログラムを動かして確認していくと……(第197回の続き)
具体的な$n$で《素数判定機》の動作を確認する

リサ「実行開始」

$\texttt{CHECK-PRIME(400)}$

...................................................................................................................................................................................................................................................................................................................................................341...........................................................

テトラ「ええっ?!」

リサ「失敗発見」

「$n = 341$のときには《素数判定機》はうまくいかないということか。うーん……」

テトラ「これは、いったい……?」

「うん。そもそも、僕たちは、

 (1)$n$が素数なのに、《素数判定機》が素数じゃないという場合

がありえないことはすでに証明したよね(第197回参照)。言い換えると、どんな正の整数$n$についても、

 (1a)$n$が素数ならば、$2^{n} \equiv 2 \pmod n$は成り立つ

ことを証明した」

テトラ「はい、そうでした」

「でも、いまのリサちゃん……リサのプログラムで、

 (2)$n$は素数じゃないのに、《素数判定機》が素数だという場合

が見つかってしまった。言い換えると、

 (2a)$2^{n} \equiv 2 \pmod n$が成り立っているのに、$n$は素数じゃない例

が見つかったことになるね。要するに、 $$ \text{《$n$は素数である》} \Longrightarrow \text{《$2^n \bmod n = 2$》} $$ はいえる。でも、 $$ \text{《$n$は素数である》} \Longleftarrow \text{《$2^n \bmod n = 2$》} $$ がいえるとは限らないんだね。$n = 341$という数が見つかってしまったから」


テトラ「$341$って素数じゃないんですか?」

リサ「$341 = 11 \times 31$」

テトラ「ほんとですね。$2^{341} \equiv 2 \pmod {341}$になってしまうけれど、$341$は素数ではない。素数判定失敗です! $n=2,3,4,\ldots,340$まで、ずっとうまく判定してきたのに、 $n = 341$で失敗するなんて!」

「驚きだけど、反例は反例だね。これで僕たちの予想は誤りだということがわかってしまった。 すべての正の整数$n$について$2^n \equiv 2 \pmod n$という式が 《素数判定機》として使えると思ったんだけどね」

テトラ「あたしたちの《素数判定機の予想》が……」

《素数判定機の予想》

$n$を$2$以上の整数とする。

$n$が素数であるとき、 $$ 2^n \equiv 2 \pmod n $$ が成り立つ(主張$P_1$)。

また逆に、 $$ 2^n \equiv 2 \pmod n $$ が成り立つとき、$n$は素数である(主張$P_2$)。

(のではないかしら、と予想したのに……)

「《すべて》を崩すときに反例は強力だよ。長い証明を作らなくても、たった一言いえば終わりだから」

《素数判定機の予想》は成り立たない。

$n = 341$が反例である。

証明終わり。

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

「厳密には、この反例が崩したのは主張$P_2$だけどね。主張$P_1$はすでに証明してあるわけだから(第197回参照)」

テトラ「がっかりです……あっ! でもっ! ちょっと待ってください。プログラムにはバグがつきものですよね。リサちゃ……」

リサ「検算?」

「ああ、$341$は実際には反例じゃないという可能性を考えているの?」

テトラ「だって、そうです。プログラムは$341$と表示しましたが、あたし自身は確かめていません!  あたしは、 $$ 2^{341} \equiv 2 \pmod {341} $$ が本当に成り立っているかを確かめたいです……テトラ、挑戦しますっ!」

テトラの挑戦

$$ 2^{341} \equiv 2 \pmod {341} $$ が本当に成り立つのか、手計算で確かめることに挑戦ですっ!
テトラちゃんはノートを開いて検算を始めた。

これは、いわば、リサとコンピュータへの挑戦である。

テトラ「……困りました…… $2^{341}$って、$2$の$341$乗ですよね。$$ \underbrace{2 \times 2 \times 2 \times \cdots \times 2}_{\textrm{$341$個}} $$ こんな計算は手では無理です」

$$ \begin{array}{rcl} 2^1 &=& 2 \\ 2^2 &=& 4 \\ 2^3 &=& 8 \\ 2^4 &=& 16 \\ 2^5 &=& 32 \\ &\vdots& \\ 2^{341} &=& \text{???} \\ \end{array} $$

リサ「$2^{341}$」

テトラ「ありがとうございます……でも、それではだめなんです。だって、これはコンピュータを使って計算したものですよね。 それでは、結局、人間が確かめたことにはなりません」

リサは小さく肩をすくめた。

「なるほど……うん、テトラちゃんの納得のために、いいアイディアがあるよ。 僕たちがやってきたことは無駄じゃなかったんだ」

テトラ「といいますと?」

「僕たちは、$n$の性質を利用できる。$n$が素数のとき、$$ 2^n \equiv 2 \pmod {n} $$ が成り立つことを僕たちは知ってる。主張$P_1$だね」

テトラ「はあ……でも、$n = 341 = 11 \times 31$ですから、$n$は素数ではありません」

「うん。テトラちゃんはいま$11\times31$のように素因数分解をしたよね。$11$と$31$は素数。ということは、主張$P_1$を使うと、こんな二つの式が成り立つことになるんじゃない?」

$$ \left\{\begin{array}{llll} 2^{11} \equiv 2 \pmod {11} && (n = 11\text{とした})\\ 2^{31} \equiv 2 \pmod {31} && (n = 31\text{とした})\\ \end{array}\right. $$

テトラ「なるほどです。$n$がどんな素数でも$2^n \equiv 2 \pmod n$は成り立ちます。 ですから、特に$n = 11$という素数のときと、$n = 31$という素数のときで考えてみるんですね。 あとは、$2^{11}$と$2^{31}$を掛け算して、 $$ 2^{11} \times 2^{31} = 2^{341} \qquad \text{(?)} $$ を計算する作戦ですかっ!」

「ちょ、ちょっと待ってよ。テトラちゃん。$n = 11$と$n = 31$のときに分けて考えるところまではいいんだけど、 そんなふうに話は進まないよ。 そもそもその計算は指数法則に反しているし。 掛け算したら、指数は足し算になるんだよ」

$$ 2^{11} \times 2^{31} = 2^{11 + 31} = 2^{42} $$

テトラ「あっと。すみませんでした……先走りし過ぎました。先輩のお考えをお聞きします」

「うん。とにかく$2^{341}$という大きな数を分解したい。そのために、$341 = 11 \times 31$という素因数分解をうまく使いたい。 だから、こんなふうに考えればいいんじゃない?」

$$ \begin{align*} 2^{341} &= 2^{11\times31} && \text{$341$を素因数分解} \\ & = (2^{11})^{31} && \text{指数法則} \\ & = (2^{31})^{11} && \text{指数法則} \\ \end{align*} $$

テトラ「ああ……掛け算ではなかったんですね」

「だから、$2^{341} = (2^{11})^{31}$と$2^{11} \equiv 2 \pmod {11}$から考えを進めていこう。できるだけ$2^{11}$を作っていくんだ」

$$ \begin{align*} 2^{341} &\equiv (2^{11})^{31} & \pmod{11} \\ &\equiv 2^{31} & \pmod{11} \\ &\equiv 2^{11\times2 + 9} & \pmod{11}\\ &\equiv (2^{11})^2 \cdot 2^9 &\pmod{11} \\ &\equiv 2^2\cdot2^9 &\pmod{11} \\ &\equiv 2^{11} &\pmod {11} \\ &\equiv 2 &\pmod{11} \\ \end{align*} $$

テトラ「……」

「同じように、今度は$31$を法として考える」

$$ \begin{align*} 2^{341} &\equiv (2^{31})^{11} &\pmod{31} \\ &\equiv 2^{11} &\pmod{31} \\ \end{align*} $$

「これはどうしようか」

テトラ「$2^{10}=1024$ですよね。ということは、$2^{11} = 2048$ですから、 $31$で割れば、商は$66$で余りは$2$です」

$$ 2048 = 31 \times 66 + 2 $$

「だとしたら、$2^{341} \equiv 2 \pmod {31}$ということだから、$$ \begin{cases} 2^{341} \equiv 2 \pmod{11} \\ 2^{341} \equiv 2 \pmod{31} \\ \end{cases} $$ だといえた」

テトラ「でも知りたいのは$\pmod {341}$のときですよね」

「うん、でも、大丈夫。右辺の$2$を左辺にもっていくと、$$ \begin{cases} 2^{341} - 2 \equiv 0 \pmod{11} \\ 2^{341} - 2 \equiv 0 \pmod{31} \\ \end{cases} $$ になる。これはどういうことかというと?」

テトラ「どういうことか?」

「$2^{341} - 2$は、$11$で割り切れるし、$31$でも割り切れるってことだよね。余りが$0$になるんだから」

テトラ「確かにそうですね」

「$11$と$31$はどちらも素数だから、$11$と$31$の最大公約数は$1$になってる。ということは、$2^{341} - 2$は、$11 \times 31$で割り切れるよね?」

テトラ「あっ、だったら、$2^{341} - 2$は$341$で割り切れる?」

「そういうことになって、結局、$$ 2^{341} - 2 \equiv 0 \pmod {341} $$ がいえる。つまり、 $$ 2^{341} \equiv 2 \pmod {341} $$ がいえたことになる」

テトラ「はい……結局、余りが$2$になりましたから、$$ 2^{341} \equiv 2 \pmod {341} $$ が成り立つので、確かに$n = 341$は反例ですね」

テトラの挑戦(終了)

$$ 2^{341} \equiv 2 \pmod {341} $$ は本当に成り立ちました……

リサ「検算終了ひゃうんっ!」

リサが変な声をあげた。

見ると、いつのまにかミルカさんが背後から両手を回し、リサの両目をふさいでいる。 「だーれだ」の体勢である。

ミルカ「今日はフェルマーの定理?」

リサから手をふりほどかれたミルカさんは、 テトラちゃんが書いていたノートをのぞきこんでそう言った。

「え……あっ、そうか! フェルマーの小定理じゃないか、これ!」

ミルカ「気づいてなかったのか」

「うわ、情けない。なぜ気づかなかったんだろう」

テトラ「フェルマーの最終定理って、あの、ワイルズさんの?」

フェルマーの最終定理じゃなくて、フェルマーの小定理と呼ばれている定理だよ。もっと早く気づくべきだった……」

フェルマーの小定理

$p$を素数、$m$を整数とし、$m$と$p$の最大公約数が$1$であるとする。 このとき、 $$ m^{p-1} \equiv 1 \pmod p $$ が成り立つ。
フェルマーの小定理の注意

$m^{p-1} \equiv 1 \pmod p$が成り立っているからといって、$p$が素数とは限らない。

「なぜ気づかなかったんだろう」

ミルカ「$2$が具体的すぎたのか」

テトラ「この式って、あたしたちが考えていた$2^n \equiv 2 \pmod n$と同じなんですか? 似てはいますが……」

「並べてみるとはっきりするよ」

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

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

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

人気の連載

おすすめ記事

ケイクス

この連載について

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

結城浩

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

この連載の人気記事

関連記事

関連キーワード

コメント

chibio6 m<0 の場合は p が偶数か奇数かの場合分けがいるかもしれないがどちらも成り立ちそうだ。 約2ヶ月前 replyretweetfavorite

aramisakihime 「数学的帰納法により!! (この宣言って気持ちいいですね)」同感。そして最後のミルカさんの台詞に驚きました。 2ヶ月前 replyretweetfavorite

MQ_null ああああこれ群論の本で見たことある! mod使った計算とか慣れてなくて苦手だけど、式をひとつひとつ追ったら分かった 2ヶ月前 replyretweetfavorite

wed7931 テトラの「コンピュータで計算した結果は人間が確かめたことにはならない」がとても深い。手計算で確認困難な例はコンピュータに頼る必要がある。一方、デバッグとは何か? 2ヶ月前 replyretweetfavorite