ａ^n−１＝（ａ−１）（ａ^(n-1)＋ａ^(n-2)＋・・・＋１）
という形の数は，少なくともａ＝２でｎが素数でない限り素数にはならない．この形の素数をメルセンヌ素数という．
［補］メルセンヌ数の素因数
ｑがメルセンヌ数Ｍp＝２^p−１の素因数であるならば，ｑは２ｋｐ＋１の形の整数である．
ａ^n＋１＝（ａ＋１）（ａ^(n-1)−ａ^(n-2)＋・・・＋１）
が素数になるのもａが素数でｎは２の累乗の場合に限られている．すなわち，ａが２の場合にこの形の素数候補はファルマー数：Ｆn＝２^(2^n)＋１だけとなる．
Mathematicaにおける素数判定のインプリメントの仕方は以下の通りである．「PrimeQは最初に小さい素数を使用して除算可能かを試し，次にミラー・ラビン(Miller‐Rabin)強擬似素数テストベース2およびベース3を使用し，次にルーカス(Lucas)テストを試みる．」これで相当大きな数も素数か否か判定してくれる．
しかし，素数かどうかの判定と合成数の素因数分解はまったく別の問題である．コンピュータを使えば素数かどうかの判定はかなり簡単にできるのに対し，因数分解をするのは依然として難しい問題なのである．
以前，フェルマー数について計算してみたのだが，オイラーが発見した2^32+1の素因数を探索するために，
64*k+1が素数か否か→素数ならば2^32+1の素因数の可能性あり
という手順に従って計算すると，k=10で素因数が見つかる．これは手計算でも簡単にできた．
その次は2^64+1の素因数になるのだが，オイラーが1732年にやったのと同じ戦略
128*k+1が素数か否か→素数ならば2^64+1の素因数の可能性あり
をとってみたが，この場合はk=2142にならないと素因数が見つからない．したがって手計算でやったとは思えないのだが，さりとて，1880年のことだからコンピュータでやった計算でもないようだ．では，どうやって2^64+1の素因数を発見したのだろうか？
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【１】オイラーとフェルマー素数
Ｆn＝２^(2^n)＋１
の形の素数をフェルマー素数といいます．Ｆ0＝３，Ｆ1＝５，Ｆ2＝１７，Ｆ3＝２５７，Ｆ4＝６５５３７２５７は素数であることがわかります．
３，５，１７が素数であることは明らかですが，たとえば，２５７については√２５７＝１６．０３・・・ですから，これより小さい素数２，３，５，７，１３が２５７を割らないことを確かめればよいことになりますし，６５５３７２５７については，√６５５３７２５７＝２５６．０・・・ですから，今度は２，３，５，・・・，２３３，２３９，２４１，２５１と５５個の素数で６５５３７２５７を割らないことを確かめます．
フェルマーはこの型の数がすべて素数だと勘違いしていて必ず素数を与える式として考え出されたのですが，ｎ＝５であっけなく破綻してしまいました．
Ｆ5＝２^(2^5)＋１＝４２９４９６７２９７＝６４１×６７００４１７
この間違いを発見したのはフェルマーから約１００年後のオイラーです．彼は約数６４１をあてずっぽうでみつけたのでも，２，３，５，７，・・・と割っていって執念で見つけたのでもありません．オイラーはＦnが合成数であるならば，それはあるｋに対してｋ２^(n+2)＋１であることを知っていて，Ｆ5の中の因数６４１＝５・２^7＋１を見つけたのです（１７３２年）．
オイラーの方法を振り返ってみることにしましょう．ここで，
ｐ｜ａ^(2^n)＋１ （ｐ≠２の素数）
ならば
２^(n+1)｜ｐ−１
となることを証明なしに与えておきます（→証明せよ）．
このことを認めると
ｐ｜Ｆ5ならば２^6｜ｐ−１
すなわち，ｐ＝１＋ｋ・２^6の形でなければならないことがわかります．ｋに１〜１０まで入れると
ｋ １＋ｋ・２^6 素数
１ ６５ ×
２ １２９ ×
３ １９３ ○
４ ２５７ ○
５ ３２１ ×
６ ３８５ ×
７ ４４９ ○
８ ５１３ ×
９ ５７７ ○
１０ ６４１ ○
ここで得られた素数１９３，２５７，４４９，５７７，６４１の中から，Ｆ5＝４２９４９６７２９７を割るものを探すと６４１が最初のものであることがわかります．このことから
Ｆ5＝４２９４９６７２９７＝６４１×６７００４１７
と分解されＦ5が素数でないことが証明されます（１７３２年）．
ついでながら，６７００４１７が素数であることは次のようにしてわかります．
ｐ｜６７００４１７ → ｐ｜Ｆ5 → ｐ＝１（ｍｏｄ６４）
したがって，ｐ＝１（ｍｏｄ６４）なる素数で，√６７００４１７＝２５８８．５・・・より小さいものが，どれも６７００４１７を割らないことをみればよいことになります．このような素数は１９３，２５７，・・・，１６０１，２１１３の１１個あります．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【２】ランドリーとフェルマー素数
１８８０年，ランドリーは（８２才という高齢にもかかわらず）
Ｆ6＝２７４１７７×６７２８０４２１３１０７２１
となることを示しました．
オイラーの場合と同様に，ｋに１〜２０まで入れると
ｋ １＋ｋ・２^7 素数
１ １２９ ×
２ ２５７ ○
３ ３８５ ×
４ ５１３ ×
５ ６４１ ○
６ ７６９ ○
７ ８９７ ×
８ １０２５ ×
９ １１５３ ○
１０ １２８１ ×
１１ １４０９ ○
１２ １５３７ ×
１３ １６６５ ×
１４ １７９３ ×
１５ １９２１ ×
１６ ２０４９ ×
１７ ２１７７ ×
１８ ２３０５ ×
１９ ２４３３ ×
２０ ２５６１ ×
となります．
素数の割合は次第に小さくなりますが，
２７４１７７＝２１４２・２^7＋１ （ｋ＝２１４２）
までこのような作業を続けることは容易ではありませんし，素因数２７４１７７が決して直観でわかるものではないことも理解されます．
逆に
ｐ｜６７２８０４２１３１０７２１ → ｐ｜Ｆ6 → ｐ＝１（ｍｏｄ１２８）
より，ｐ＝１（ｍｏｄ１２８）なる素数で，√６７２８０４２１３１０７２１より小さいものが，どれも６７２８０４２１３１０７２１を割らないことをみてもよいのでしょうが，このような戦略をとったところで意味のないものになってしまうのがオチでしょう．
ランドリーがオイラーの1732年にやった方法を踏襲したとはとても思えないのですが，どうやってやったのかまったく予想がつきません．それで，ランドリーがとった戦略がいかなるものか調べてみたのですが，1880年に素因数が判明と記載されているだけで方法までは載っておらず，結局，わからずじまいでした．これについてご存知の方はぜひ教えて下さい．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
１９７５年にはブリルハートとモリソンがフェルマー数
Ｆ7＝５９６４９５８９１２７４９７２１７×５７０４６８９２００６８５１２９０５４７２１，
１９８１年に，ブレントとポラードが
Ｆ8＝１２３８９２６３６１５５２８９７×９３４６１６３９７１５３５７９７７７６９１６３５５８１９９６０６８９６５８４０５１２３７５４１６３８１８８５８０２８０３２１
を分解してみせました．
Ｆ19までのフェルマー数の素因数を以下に掲げておきますが，おそらくこれらは力任せのコンピュータ計算ではなく，冒頭の部分は数学的な考察が必要であり，最後の部分にある程度のコンピュータ計算を利用して得られたものに違いないでしょう．
Ｆ5：６４１
Ｆ6：２７４１７７
Ｆ7：５９６４９５８９１２７４９７２１７
Ｆ8：１２３８９２６３６１５５２８９７
Ｆ9：２４２４８３３
Ｆ10：４５５９２５７７
Ｆ11：３１９４８６
Ｆ12：１１４６８９
Ｆ13：２７１０９５４６３９３６１
Ｆ15：１２１４２５１００９
Ｆ16：８２５７５３６０１
Ｆ17：３１０６５０３７６０２８１７
Ｆ18：１３６３１４８９
Ｆ19：７０５２５１２４５０９
もちろんこういう分解が発見される以前でもＦ9，Ｆ10，Ｆ11，・・・，Ｆ32が合成数であることは知られていました．現在，合成数かどうかが分からない最小のフェルマー数はＦ33ということです．
いまのところ，フェルマー数
Ｆn＝２^(2^n)＋１
では，ｎ＝０，１，２，３，４の５個以外にフェルマー素数はみつかっていません．フェルマー数（２^(2^n)＋１）に対してはメルセンヌ数におけるリュカテストと同じくらい能率的なペパンの素数判定法
Ｆnが素数 ←→ ３^{(Fn-1)/2}＝−１（ｍｏｄＦn）
があり，コンピュータを使って６番目のフェルマー素数の探索が続けられているのですが，はたして本当に存在するのでしょうか．
Ｆnのなかに素数が無限にあるか，または，合成数が無限にあるかということについては何もわかっていないのです．なお，リュカやペパンの素数判定法によってある数が合成数とわかってもそれを素因数分解するのはとても大変な作業になります．現在，巨大な整数の素因数分解に楕円曲線法とか平方ふるい法とか能率のよい素因数分解法が考え出されています．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【３】ガウスとフェルマー素数
定規とコンパスだけで正３角形，正４角形，正６角形，正８角形が作図できることは簡単にわかりますが，辺の数５，７，９の場合はどうでしょうか．正５角形は古代ギリシャにおいて作図可能であることが発見されました．となれば，次に正７角形・正９角形の作図は？と考えるのは自然な成り行きでしょう．
ところが，かのアルキメデスでさえも正７角形・正９角形の作図に成功しなかったといわれています．また，内接正多角形の作図は画家であり建築家であるレオナルド・ダ・ヴィンチの関心を惹きました．しかし，彼でさえ近似的な内接正七角形の作図を正確なものと思っていたようです．
辺数３，４，５，６，８，１０，１２，１５，１６の正多角形は作図できますが，辺数７，９，１１，１３，１４の正多角形は作図できないことから，正１７角形もそうであろうと推察されます．ところが，１７９６年，ガウスは１９才のときに正１７角形の作図を思いつき，のみならず，ｎが素数の正ｎ角形について，ｎ＝２^(2^m)＋１が素数の場合に限り定規とコンパスだけで作図可能であることを発見しています．
正７角形も正９角形も作図できないのに，まさか正１７角形が作図できるとはと思うのが普通なのでしょうが，このことを用いると，ｍ＝０のとき正３角形，ｍ＝１のとき正５角形，ｍ＝２のとき正１７角形となり，作図可能であることがわかります．当然，ずっと面倒になるでしょうが，正２５７角形（ｍ＝３），正６５５３７角形（ｍ＝４）も作図可能です．
定規とコンパスだけでζnが作図可能となるための必要十分条件は，体の列
Ｑ＝Ｋ0＜Ｋ1＜Ｋ2・・・＜Ｋn＝Ｑ（α）
においてＫiがＫi-1の２次拡大［Ｋi：Ｋi-1］＝２となる，すなわち，複素数αに対して
［Ｑ（α）：Ｑ］＝２^n
となるものが存在することなのですが，α＝ζ5，ζ17はこの条件を満たす，一方，α＝ζ7では［Ｑ（ζ7）：Ｑ］＝６より満たしていないということを考察することによって得られました．
さらに
ｎ−１｜２^kより，ｎ＝１＋２^k
ここで，ｋが奇数因数を含めばｎは素数ではなくなりますから，結局
ｎ＝２^(2^m)＋１
の形でなければなりません．作図可能となるｎ＝２^(2^m)＋１の形の素数をフェルマー素数といいます．フェルマー素数はガウスによって１世紀にわたる眠りから覚まされ，数論と幾何学に新たな美しさを吹き込んだことになります．
フェルマーはこの型の数がすべて素数だと勘違いしていて必ず素数を与える式として考え出されたのですが，ｍ＝５のときは素数ではなく，現在，ｍ＝０，１，２，３，４の５個以外にフェルマー素数はみつかっていません．６番目のフェルマー素数の探索がコンピュータを使ってなされていますが，はたして本当に存在するのでしょうか．
アルキメデスは円柱とそれに内接する球の体積比が３：２であることを発見した記念に，自分の墓の上に円柱の形をした記念碑をおくように遺言したといわれています．アルキメデスと同じように，ガウスは正１７角形を墓石に彫るよう遺言しています．このことはガウス自身がその発見をいかに重視したかを物語っています．
数々の大発見をしたガウスですが，１９才の青年がアルキメデスをもってしてもできなかった古代ギリシア以来２０００年の謎を解いたのですから，まさに驚きとしかいいようがありません．この正１７角形の作図は彼を本格的に数学の道に入らせるきっかけとなったといわれています．
なお，４次曲線：レムニスケートには円に共通する性質があり，定規とコンパスだけで奇数のｎ等分することができる必要十分条件はｎがフェルマー素数（ｎ＝２^(2^m)＋１の形の素数：３，５，１７，２５７，６５５３７）であることです．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
［補］フェルマー数
フェルマー数（２^(2^n)＋１）は簡単な漸化式
Ｆn＝（Ｆn-1−１）^2＋１
を満たしています．Ｆn-1^2はほぼＦnと等しくなるというわけです．
また，この式から
Ｆn−２＝Ｆn-1（Ｆn-1−１）＝・・・＝Ｆ0Ｆ1・・・Ｆn-1
言い換えれば，Ｆn−２はそれより小さいすべてのフェルマー数で割り切れることがわかります．
したがって，（Ｆn，Ｆi）＝１がすべてのｉ（０≦ｉ≦ｎ−１）にについて成り立ちます．このことは任意にｉ≠ｊをとったとき，（Ｆi，Ｆj）＝１と意味するのですが，このことから数列｛Ｆn｝を用いて，素数が無限にあることを示すことができます．
（証明）
すべてのＦiの素因数を１つずつとりｐiと呼べばｐはすべて異なるから，素数は無限にあることがわかる．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝