ａ^n−１＝（ａ−１）（ａ^(n-1)＋ａ^(n-2)＋・・・＋１）

という形の数は，少なくともａ＝２でｎが素数でない限り素数にはならない．この形の素数をメルセンヌ素数という．

［補］メルセンヌ数の素因数

　ｑがメルセンヌ数Ｍp＝２^p−１の素因数であるならば，ｑは２ｋｐ＋１の形の整数である．

　　ａ^n＋１＝（ａ＋１）（ａ^(n-1)−ａ^(n-2)＋・・・＋１）

が素数になるのもａが素数でｎは２の累乗の場合に限られている．すなわち，ａが２の場合にこの形の素数候補はファルマー数：Ｆn＝２^(2^n)＋１だけとなる．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】オイラーとフェルマー素数

　　Ｆ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　→　ｐ＝１（ｍｏｄ６４）

したがって，ｐ＝１（ｍｏｄ６４）なる素数で，√６７００４１７＝２５８８．５・・・より小さいものが，どれも６７００４１７を割らないことをみればよいことになります．このような素数は１９３，２５７，・・・，１６０１，２１１３の１１個あります．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝