美しい反例

若い数学者が、壇上へと静かに足を運んでいく。
「だれだあいつは」という声が、どこからともなく聞こえた気がした。

彼は壇上へ上がると、一呼吸置いて自分のノートを開いた。
まだ一言も発していない。
彼は自分の名前さえ名乗らないままに、ゆっくりと、しかし力強く、黒板に数式を１つ書きはじめた。

$\displaystyle 2^{2^5}+1 = 641 \times 6700417$

会場が一瞬どよめいたが、すぐにおさまった。観衆は彼の意図を理解したようだった。そして、静かに拍手が沸き起こった。

彼の口元から、笑みがこぼれたように見えた。

上の文章は私の創作です。とある数学者が、ある問題を解決したシーンを文章にしたものです。
演出は、だいぶ盛っているかもしれません。笑
当時の様子を見た人は、もう生き残っていませんから、事実を確かめようがないのが残念です。

主役の数学者の名は「レオンハルト・オイラー」。オイラーは、上に挙げた「たった一つの数式」を示すことによって、これまで謎だった問いに明解な答えを与えました。

「たった１つの式を書いただけで証明になるなんて、そんなことは可能なのか？」
と思うかもしれません。
一般的な証明では無理ですが、もしそれが反例を使った「反証」ならば、可能です。

オイラーが示したのは、つまりこういうことです。

フェルマー数と呼ばれる数のグループがあります。これは、「ピエール・ド・フェルマー」という著名な数学者によって発見された数でした。

$2^{2^n} + 1$

この数は、 $n = 0, 1, 2, 3, 4$ の場合において、すべて素数であることが知られていました。

$\begin{eqnarray} 2^{2^0} + 1 &=& 3 \\ 2^{2^1} + 1 &=& 5 \\ 2^{2^2} + 1 &=& 17 \\ 2^{2^3} + 1 &=& 257 \\ 2^{2^4} + 1 &=& 65537 \end{eqnarray}$

たしかにすべて素数です。

次の $2^{2^5} + 1$ から先は、とてつもなく大きな数となります。ちなみに、 $2^{2^5} + 1$ はこんな数です。

$2^{2^5} + 1 = 4294967297$

しかしながらフェルマーは、今後も素数が続くだろう、すなわち、フェルマー数はすべて素数である、と予想したのです。

フェルマーの予想：
フェルマー数 $2^{2^n} + 1$ は，すべて素数である．

もちろん、この予想は証明されていませんから、間違っている可能性があります。フェルマーの予想は長いこと未証明でした。にも関わらず、単に証明が難しいだけで、予想そのものは正しいものだと考えられてきました。

ここでオイラーの登場です。オイラーは、このフェルマーの予想が誤りであることを反証によって示したのです。フェルマーの没後約70年たった 1732年のことでした。

反証には、元の命題が成り立たない具体例、すなわち反例を１つ提示すればいい。オイラーは、これまで素数と分かっていた $n = 4$ の次、つまり $n = 5$ のフェルマー数が、素数ではないことを示したのです。

これが冒頭のシーンでした。素数でないことを示すには、その数が素因数分解できることを示せばよい。オイラーは、 $n=5$ のフェルマー数が素因数分解できることを、実際に素因数分解の式を書いてみせることで示したわけです。しかも無言で。

オイラー先生かっこいい。

これが tsujimotter が思う、もっとも美しい反例です。余計な説明はいっさいなく、数式一本で有無を言わさず反証できてしまうのだから気持ちいいですよね。

オイラーの見つけた約数の探し方

という話で、今回の主題はほとんど終わりなわけですが、１つ気になる点があると思います。

オイラーはどうやって、この巨大な数の素因数分解をやってのけたのでしょう。コンピュータが使える現代ならまだしも、オイラーの時代は手計算するしかありません。あてずっぽうで割ってみたのでしょうか。それとも、 $2, 3, 5, \ldots$ と順に素数で割ってみたのでしょうか。そうではありません。オイラーは根拠をもって、 $2^{2^5} + 1$ が $641$ で割り切れると考えたのです。

オイラーが使ったとされるのは、フェルマー数の持つ次の性質です。

$2^{2^n}+1$ が素数 $p$ で割り切れるとき，
その $p$ は正の整数 $k$ を用いて $p = k\cdot 2^{n+2} + 1$ の形で表せる．

具体的に数値を代入して考えてみましょう。今回考えたいのは、 $2^{2^5} + 1$ が合成数であるとしたら、何で割り切れるかです。

証明なしに上の結論を使うと、素数 $p$ で割り切れるとすれば、それは $p = k\cdot 2^{7} + 1$ の形で表せるはずです。 $k$ に順番に数を代入していくと、

$1\cdot 2^7 + 1 = 129$
$2\cdot 2^7 + 1 = 257$
$3\cdot 2^7 + 1 = 385$
...

となっていきます。それぞれの候補で、 $2^{2^5} + 1$ を割っていけば良いわけです。途中で、 $385$ など、明らかに素数でない数が登場しますが、これは無視します。すると５番目に、

$5\cdot 2^7 + 1 = 641$

となって、見事割り切れます。

おめでとう！ $2^{2^5} + 1$ の約数を発見しました！！

結構早い段階で見つかりましたね。上の定理を利用することで、本来 $641$ までの素数すべてで割り算しなければならないところ、回数を 5回に短縮することが出来ました。これなら手計算でもわけないでしょう。

こうなると、上の定理をどうしても証明したくなりますね。

この定理の証明方法はなかなか面白いのですが、残念なことに、初等整数論の高度な運用が必要です。注意したいのは、「初等」だからといって「簡単」ではない、ということです。

以下の証明は、分かる方はじっくりと、そうでない方は雰囲気だけでも感じてみてください。

（証明）
フェルマー数 $2^{2^n} + 1$ が，素数 $p$ で割り切れるならば， $p\equiv 1 \pmod {2^{n+2}}$ となることを示す．

フェルマー数 $2^{2^n} + 1$ が，素数 $p$ で割り切れると仮定すると， $2^{2^n} + 1 \equiv 0 \pmod p$ ，すなわち，

$\displaystyle 2^{2^n} \equiv -1 \pmod p \tag{1}$

である．

ここで，両辺二乗すると， $2^{2^{n+1}} \equiv 1 \pmod p$ であるが，式 (1) とから， $2^{n+1}$ が法 $p$ における $2$ の位数であると結論づけてよい．

なぜなら，位数を $e$ とすると， $e$ は $2^{n+1}$ の約数であるから， $e=2^k, \; k \leq n+1$ となるはずだが， $k < n+1$ においては式 (1) と矛盾するからである．

次にフェルマーの小定理より，

$\displaystyle 2^{p-1} \equiv 1 \pmod p \tag{2}$

であるから，先ほどの位数 $2^{n+1}$ は $p-1$ を割り切る．

ところで， $n+1 = 1, 2$ のときには，フェルマー数は素数となるから，この証明では $n+1 \geq 3$ を考えてよい．したがって， $2^{3}$ は $2^{n+1}$ を割り切る．

よって，上の結論とあわせて， $2^3 = 8$ は $p-1$ を割り切る．すなわち， $p\equiv 1 \pmod 8$ である．

平方剰余の第二補充則より， $p\equiv 1 \pmod 8$ であれば， $2$ は法 $p$ の平方剰余である．したがって，平方剰余におけるオイラーの基準により，

$2^{\frac{p-1}{2}} = 1 \pmod p \tag{3}$

である．

結局，(3) により， $2$ の位数 $2^{n+1}$ は $\frac{p-1}{2}$ を割り切ることがわかった．すなわち，双方 2 倍して， $2^{n+2}$ は $p-1$ を割り切る．

すなわち，

$p-1 \equiv 0 \pmod {2^{n+2}}$

であるから，これで欲しかった

$p \equiv 1 \pmod {2^{n+2}}$

という結論が得られた．

（証明終わり）

どうです？長かったでしょう。初等整数論の道具をふんだんに使った贅沢な証明でした。天才オイラーは、計算を楽にするためにこんな難しい証明をやっていたのか、と思うと面白いですね。もしかして、この証明を考えるより計算した方が早かったりして・・・。

個人的には、フェルマーの予想の反証に「フェルマーの小定理」が使われているというのが、なんとも憎たらしいなと思います。笑

tsujimotter の過去記事では、フェルマーの小定理はこんなところで登場しました。参考までに。

フェルマー素数と作図

ここまで読んできた方の中には「フェルマー素数をなぜ考えるのか」と思った人もいるかもしれません。フェルマー数が何かの役に立つ気がしませんからね。ところが、このフェルマー数、実は意外な話につながるのです。それが「正多角形の作図」です。

「定規とコンパスの作図において、どんな正多角形が作れるのか？」という幾何学の問題は、ギリシャ時代から続く数学者の関心事でした。
正三角形と正五角形は、ユークリッドの書にもあるように、作図可能であることが知られていました。証明はされていないものの、大方の予想は、これ以外の「角の数が素数の正多角形」すなわち「正素数角形」の作図は不可能であろう、というものでした。偶数角の正多角形なら作図できそうですが、「正素数角形」なんて、いかにも作図が難しそうです。

f:id:tsujimotter:20141218113339g:plain:w320

図：正五角形が作図手順の例

ところが、オイラーよりあとに生まれた「カール・フリードリヒ・ガウス」は、正１７角形の作図が可能である、と主張したのです。この「１７」という数字、まさに $n=2$ のフェルマー素数です。

実は、フェルマー数が素数のときに限り、正素数角形が作図可能であることが知られています。したがって、作図可能な正素数角形は、正三角形、正五角形、正１７角形、正２５７角形、正６５５３７角形、の５つです。これらは、５つのフェルマー素数と対応しています。もちろん、フェルマー素数がこの先見つかるかもしれませんので、もし見つかればそれに対応した正素数角形が作図可能になるわけです。まぁ、ここまで来ると、ほとんど円ですが。

ちなみに、正１７角形の作図手順は、ガウスの後「ヨハネス・エルチンゲル」によって示されました。正２５７角形、正６５５３７角形もそれぞれ具体的な作図手順が示されています。正６５５３７角形の手順を示したのは、ドイツの「ヨハン・グスタフ・ヘルメス」です。彼は 10 年もの歳月をかけて正６５５３７角形の作図法を調べ、1894年には計算の要旨のみの報告を雑誌に発表しました。200ページを超える原稿は、今もゲッティンゲン大学に収蔵されているそうです。一度みてみたいものですね。

だいぶ、脱線してしまいましたが、ともかくフェルマー素数は、数学のまったく異なる分野でも登場する数で、とりわけそれが素数であることが重要なのです。

美しく、シンプルな反例、を紹介するという話だったのですが、あまりに面白い話が詰まっているので、解説がずいぶんと長くなってしまいました。いかがだったでしょうか。

それでは、今日はこの辺で。