ａ^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の素因数を発見したのだろうか？

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