僕：数学が好きな高校生。
テトラちゃん：僕の後輩。好奇心旺盛で根気強い《元気少女》。
ミルカさん：数学が好きな高校生。僕のクラスメート。長い黒髪の《饒舌才媛》。
リサ：自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。
図書室にて
$2^n$と$2$とは、$n$で割ったときの余りが等しい
ことを表している。
おどろくべきことに、$n$に小さな素数$2,3,5,7,11$などを代入してみると、この式は成り立つ。
そして、$n$に小さな合成数$4,6,8,9,10$などを代入してみると、この式は成り立たない。
もしかしたら、 この式は$n$が素数か否かを判定する《素数判定機》なのだろうか？ コンピュータ少女のリサがプログラムを動かして確認していくと……（第197回の続き）
リサ「実行開始」
...................................................................................................................................................................................................................................................................................................................................................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$と同じなんですか？ 似てはいますが……」
僕「並べてみるとはっきりするよ」
この連載について
数学ガールの秘密ノート
数学青春物語「数学ガール」の女子高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わってください。本シリーズはすでに何冊も書籍化されている人気連載です。 （毎週金曜日更新）
