第198回 シーズン20 エピソード8

エヌを巡る冒険（後編）

図書室にて

リサ「実行開始」

テトラ「ええっ？！」

リサ「失敗発見」

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

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

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

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

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

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

ことを証明した」

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

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

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

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

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

が見つかったことになるね。要するに、 $$ \REMTEXT{《$n$は素数である》} \Longrightarrow \REMTEXT{《$2^n \bmod n = 2$》} $$ はいえる。でも、 $$ \REMTEXT{《$n$は素数である》} \Longleftarrow \REMTEXT{《$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$ という式が 《素数判定機》として使えると思ったんだけどね」

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

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

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

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

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

リサ「検算？」

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

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

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

$$ \begin{array}{rcl} 2^1 &=& 2 \\ 2^2 &=& 4 \\ 2^3 &=& 8 \\ 2^4 &=& 16 \\ 2^5 &=& 32 \\ &\vdots& \\ 2^{341} &=& \REMTEXT{？？？} \\ \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\REMTEXT{とした})\\ 2^{31} \equiv 2 \pmod {31} && (n = 31\REMTEXT{とした})\\ \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 \REMTEXT{（？）} $$ を計算する作戦ですかっ！」

僕「ちょ、ちょっと待ってよ。テトラちゃん。 $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} && \REMTEXT{$341$を素因数分解} \\ & = (2^{11})^{31} && \REMTEXT{指数法則} \\ & = (2^{31})^{11} && \REMTEXT{指数法則} \\ \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$ が具体的すぎたのか」

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

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