登場人物紹介
僕:数学が好きな高校生。
テトラちゃん:僕の後輩。好奇心旺盛で根気強い《元気少女》。
ミルカさん:数学が好きな高校生。僕のクラスメート。長い黒髪の《饒舌才媛》。
リサ:自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。
僕とテトラちゃんは、 $$ 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$ は素数じゃない例
が見つかったことになるね。要するに、 $$ \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$ という式が 《素数判定機》として使えると思ったんだけどね」
テトラ「あたしたちの《素数判定機の予想》が……」
《素数判定機の予想》
$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}_{\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^{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$ と同じなんですか? 似てはいますが……」
僕「並べてみるとはっきりするよ」
無料で「試し読み」できるのはここまでです。 この続きをお読みになるには「読み放題プラン」へのご参加が必要です。
ひと月500円で「読み放題プラン」へご参加いただきますと、 435本すべての記事が読み放題になりますので、 ぜひ、ご参加ください。
参加済みの方/すぐに参加したい方はこちら
結城浩のメンバーシップで参加 結城浩のpixivFANBOXで参加(2017年6月16日)