皆さん、こんにちは。
ここ１か月は本業の仕事が忙しく、また旅行に行ったりコロナに罹ったりと色々あって記事を上げられずにいました。というわけで、１か月ぶりの記事になります。
1. フェルマー数とは？
以前紹介したメルセンヌ数素数発見器？その１ ～メルセンヌ素数～ - ちょぴん先生の数学部屋 (hatenablog.com)と似てますが、あちらとは違い、定数項がプラスになっていて、指数部分が2の累乗になっています。
この中でも素数になるフェルマー数を「フェルマー素数」と呼ぶわけです。
さて、このフェルマー素数を背景にした大学入試の問題を１つ紹介します。
これは千葉大で過去に出題された問題で、a=2とすればまんまフェルマー数になりますね。まずは、この問題を解いてみましょう。
この問題は、「bが奇数の素因数qを持つ」と仮定して矛盾を導く背理法で考えればよいでしょう。
この仮定を置くと、bが
と書けて、pは下のように因数分解できてしまいます。
ここで、A=a^mとおいています。
この２つの因数のうち一方が1であればpが素数である可能性を残せるのですが、aの最小値が2, mの最小値が1なので、Aの最小値が2となってしまい、
このように、2つの因数はどっちも3以上になってしまいます。よって、上記の仮定の下ではpは合成数になってしまいます。これで矛盾が導けました。
これで、bは2の累乗じゃないといけないと分かりました。
そして、aが奇数の時はpは4以上の偶数になるので必ず合成数です。よって、pが素数になるためにはaが偶数でないといけません。
こんな背景があって、フェルマー数は素数の形の候補になっていて重要だというわけです。
フェルマー数のうち、最初の方をいくつか書き出すと、
といった感じになり、少なくともn=4までの5つは全て素数になっています。
5つ調べて全部素数だったのだから、「フェルマー数はn=5以降も全部素数なんだろうな」と予想したくなります。実際、かの天才フェルマーもそう主張していました。
n=5のときのフェルマー数は、
という10桁の巨大な数になります（日本語にすると、42億9496万7297です）。こんな巨大な数が素数かどうかを判定するのは難しい問題で、フェルマー自身も途中で断念して「きっと素数だよ」と主張したわけです。
しかし約100年後、大天才オイラーがこの数の素因数分解を発見しました。（発見方法については後述します）
一番小さい素因数が641というそこそこ大きなもので、フェルマーが途中で断念して素数だと早合点したのも仕方ないという感じです。
いずれにせよ、n=5のフェルマー数は素数ではなかったわけです。最初の数個で性質を証明なしで決めつけるのが如何に危険か。数学の恐ろしさが垣間見れます。
というわけで、フェルマー数には素数も合成数も紛れていることが分かりました。
そしてなんと、2023年現在n=0,1,2,3,4の5つ以外にフェルマー素数は見つかっておらず、「それ以外にフェルマー素数があるのか？無限個あるのか？」はいずれも未解決問題となっています。
フェルマー数は、見ての通り指数の肩に指数関数が入ってる数列なので、指数関数すらも凌駕する凄まじいスピードで大きくなっていき、ますます素数判定が難しくなってしまうわけです。
3. フェルマー数に関する定理
3-1. 相異なるフェルマー数は必ず互いに素
フェルマー数には、次のような性質があります。
これを証明するために、まずフェルマー数の漸化式を導出します。
フェルマー数はそのままでは因数分解が困難な形をしています。が、定数項が+1ではなく-1であれば「和と差の積」の因数分解ができそうです。
ここに注目して、フェルマー数から2引いた数を考えて因数分解していきます。試しにやってみると、
因数分解後に番号が1つ小さいフェルマー数が出現して、綺麗に漸化式を作れます。
後半に同じく「フェルマー数から2引いた数」が登場しているので、同じプロセスを繰り替えることができて、結局、
フェルマー数の積でかけることが分かります。
よって、フェルマー数は「これまでのフェルマー数全ての積に2を足したもの」
で表せることが分かります。
この漸化式を用いて、フェルマー数同士が互いに素になることを示していきます。
証明方法は、例によって背理法になります。
もし、n=iのフェルマー数とn=jのフェルマー数が3以上の公約数dを持つと仮定すると、
（フェルマー数は定義から必ず奇数なので、1でない公約数は3以上になります）
漸化式でmod dを考えると、
となって、dが2の約数じゃないといけないと分かります。しかし、これはdが3以上であることと矛盾しますね。これで証明完了です。
この性質から、
「各フェルマー数は、各々それ専用の素因数を持っている」ということができます。
言うまでもなくフェルマー数は無限個あるので、このことから「素数は無限個存在する」ことが証明できたことになります。
素数が無限個あることの証明はいくつかありますが、その有名な例の１つになっています。
3-2. 作図可能な正n角形の必要十分条件
フェルマー数は、実は中学で習った「作図」とも深い関係があります。
目盛りの付いてない定規とコンパスだけを使って特定の図形を描くことを「作図」と呼ぶわけですが、ここでは、正n角形を「作図」することを考えます。
かの天才ガウスは、「作図」できる正n角形の必要十分条件が次のようなものであることを証明しました。
（※「具体的な作図方法を見つけた」わけではなく、あくまで「このnなら何かしら作図する方法が必ずあるし、逆にそれ以外の場合はどうあがいても作図できない」ことを証明した、という点に注意です）
2の累乗の部分は、出来上がった円弧（※正n角形は円をベースに作図します。n=6の場合は中学でお馴染みでしょう）を「垂直２等分線の作図」と同じ要領で2等分するだけなので本質的には自明です。
本質はそれ以外の積の部分で、これがなんと「異なるフェルマー素数を1つずつかけたもの」になるというのが、ガウスの証明した主張です。証明は、群論などを用いた大変高度なものになってしまうので、割愛します。
上記のように、現在フェルマー素数はn=0,1,2,3,4の5つが見つかっているので、2の累乗の部分を無視すれば、2023年現在作図可能な正n角形は次のような31通りあることになります。
n=3,5,17,257,65537
n=15,51,85,771,1285,4369,196611,327685,1114129,16843009
n=255, 3855, 13107, 21845, 983055, 3342387, 5570645, 50529027, 84215045, 286331153
n=65535, 16711935, 252645135, 858993459, 1431655765
n=4294967295
17くらいまでならともかく、それ以上になると点と点がつぶれて訳分からなくなりそうですね笑
ちなみに余談ですが、古代ギリシャの時代には正３角形と正５角形（とその2の累乗倍）の作図方法が知られていたのですが、それ以外の作図可能な正多角形は一向に発見できず、ガウスが正17角形が作図可能だと発見したことで2000年ぶりに作図可能な正多角形の種類が更新されました。そのときガウスは御年わずか19歳！！リアルチートもいいところです・・・
4. n=5で素数にならないことが何故分かったか？
さて、オイラーがn=5の場合は合成数になると証明した、と書きましたが、なぜオイラーはn=5の場合の素因数分解に成功したのか？その背景知識を説明します。
普通、素数か否かを判定したければ、その数を素数で小さい順に次々割っていき割り切れるかどうかを調べる、いわゆる「試し割り」という方法が使われます。
しかし、n=5のフェルマー数は
と因数分解され、一番小さい素因数が641という大きな数です。試し割りで641に至るには、計115回割り算しなければなりません（641は115番目の素数です）。2,3,5,11みたいに判定法が存在する素数数個を除いたとしても100回以上割り算しなければならず、これじゃ日が暮れちゃいますね。
ということで、オイラーのアイデアは簡単に言ってしまうと「割り切れそうな素数のアタリをつけ候補を絞ってから試し割りした」となります。
具体的には、後述する性質から、
「n=5のフェルマー数を割り切る素数は64k+1の形じゃないといけない」と候補を絞って試し割りに持ち込みました。
実際に64k+1の形の自然数を並べてみると、下の表のように641までに5個の素数が出て来ます。
原始的な試し割では115回割り算する必要があったところが、このアイデアで5回の割り算で済むようになったわけです。こうしてオイラーはn=5の場合の素因数分解に成功したわけです。
4-2. フェルマー数の持つ素因数の性質
さて、最後にこのオイラーのアイデアの元ネタになったフェルマー数の性質を紹介します。
それは、次のようなものです。
このpの式にn=5を代入すると、前述の64k+1が導けます。これによって、フェルマー数が持っている素因数の候補を導けるわけです。
（あくまで候補＝必要条件です。pがこの形だからと言って、必ずしも本当にFnがpで割り切れるとは限らないことに注意です）
以後、この性質を証明していきます。
Fnがpで割り切れることを数式にすると、合同式を使って、
となります。この(A)を両辺2乗すると、
となります。この(B)のように「累乗≡1」の形にすることで先の見通しがよくなります。
ここで、「位数」という概念を導入します。位数とは、次のような自然数のことです。
このbのことを、「pを法とするaの位数」と呼びます。
例を挙げると、
4=2^2を3で割った余りは1なので、「3を法とする2の位数は2」といった具合です。
位数を考えると、「a^□≡1 (mod p)」という合同式があった場合、□は「位数の倍数」となります。この性質が大変重要です。
というわけで、pを法とする2の位数をbとすると、(B)から
2^(n+1)はbの約数 ⇔ bは2^(n+1)の約数
だとわかるので、bは
の形でかけるはずです。
この下で、実はb=2^(n+1)になることを背理法で証明します。
bが2^n以下だと仮定すると、位数の定義から
が言えます。この(D)を両辺2乗すると、
となり、(D)と比べてちょうど番号が1個増えただけの式ができます。
このプロセスを、番号がnになるまで繰り返すと、
(F)が導けます。
ところが、(A)と比べると矛盾が発生しています。
よって、背理法により仮定が誤りで、目論見通り
が示せました。
さらに、もう１つ式を作ります。その手段が「フェルマーの小定理」です。
（※フェルマーの小定理については、RSA暗号 ～素数は世の中でメチャクチャ役に立っている～ - ちょぴん先生の数学部屋 (hatenablog.com)で証明含めて紹介しています）
pと2は互いに素なので（Fnが奇数なのでpも奇数です）、フェルマーの小定理から、
が言えます。
(G)から位数が2^(n+1)だと分かっているので、位数の性質から
p-1は、b=2^(n+1)の倍数
と示せます。ここまでくれば証明はほぼ終わったも同然です。
自然数kを適切にとってくれば、
とpが書けることになり、これで証明完了です。
今回の証明で用いた「位数」の概念は、数オリの問題でもよく使うアイデアで、整数問題において役立つ知識と言えると思います。
（参考記事数学オリンピックのシンプルな超難問 ～マスターデーモン～ - ちょぴん先生の数学部屋 (hatenablog.com))
