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

第198回 シーズン20 エピソード8
エヌを巡る冒険(後編)

登場人物紹介

:数学が好きな高校生。

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

ミルカさん:数学が好きな高校生。のクラスメート。長い黒髪の《饒舌才媛》。

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

$ \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} $

図書室にて

テトラちゃんは、 $$ 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日)

[icon]

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


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

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