素数とは、２，３，５，７，１１，・・・のように１とその数自身以外に約数をもたない数のことで、プロ・アマを問わず数学者たちを魅了し続けてきました。整数論の発展は素数なしには望めなかったといっても過言ではないでしょう。

１．素数定理

　素数の分布は不規則かつ複雑で未知の部分が多いのですが、１８世紀から１９世紀にまたがって活躍したガウスは、「素数はどのような規則で現れるか」ということを考え、素数定理を予想しました（１７９２年：ガウスは当時１５才であった）。素数定理とは、

π（ｘ）〜ｘ／ｌｏｇｘ　　　（ｘ→∞）

というものです。ここで、π（ｘ）は任意の整数ｘを越えない素数の個数を表すものとします。素数定理は、ｘを超えない素数の個数を与える近似的な公式ですが、”〜”記号は漸近的に等しい、すなわちｘが十分大きいとき両者の比が１に近づくという意味であって、両者の差がなくなるという意味ではありません（→【補】）。いいかえれば、この近似式の絶対誤差はｘの増大とともに増大するが、相対誤差は減少する、つまり、左辺と右辺の比はｘを∞にすると極限が存在して０でも無限大でもなく、１に収束する、

π（ｘ）／（ｘ／ｌｏｇｘ）〜１　　　（ｘ→∞）

ということです。ｘに近い２つの連続した素数間の平均距離はおよそｌｏｇｘだといってもよいでしょう。

　１８５０年に、ロシアの数学者チェビシェフは任意の数ｎと２ｎの間には少なくとも一つの素数ｐが存在する（ｎ＜ｐ≦２ｎ）、同じことですが素数ｐの次の素数は２ｐより小さい（ｐ_k+1 ＜２ｐ_k ）という定理を発見しました。この証明の発見は彼が実に１８才のときだったそうですから、「栴檀は双葉よりの芳し」の諺のごとくです。チェビシェフの定理によって、素数の分布には何らかの秩序が存在していることになります。さらに、チェビシェフは１８５２年に、十分大きなｘについてπ（ｘ）／（ｘ／ｌｏｇｘ）が０．９２１２９と１．１０５５５の間にあるという結果を得ています。この結果を得るためにチェビシェフは、オイラーによって１７４０年に考案されたゼータ関数（のちにリーマンがこの名前を付けた）を利用しました。

　素数定理は、ガウス以降、多くの数学者たちが証明できなかった難問でしたが、ガウスの予想から約１００年後の１８９６年、フランスの数学者アダマールとプーサンは、同じ年に独立に、リーマンによって複素数まで拡張されたゼータ関数を用いてガウスの素数定理を証明しました。

　その後、長い間、素数定理の証明には複素解析的な方法を使用することが避けられないと信じられていましたが、１９４９年、フィールズメダリストのセルバーグとさすらいの数論家エルデスは独立に複素解析関数の理論を使わない初等的な方法で素数定理を証明し、当時の数学界を大いに驚嘆させました。セルバーグはこの功績によりフィールズ賞（４年に一度開かれる世界数学者会議で数学の著しい研究に対して与えられる賞で、数学界のノーベル賞ともいうべきものである）を受賞していますが、エレガントで独創的な解をもつ問題を探し当てることができる数学者が優れた数学者ということなのでしょう。

　素数定理をエラトステネスのふるいという初等的な方法を用いて、ラフなスケッチ程度に誘導してみましょう。ｘまでのすべての整数うちで、奇数、すなわち２で割れない数は大体半分（１−１／２）あります。奇数のうちで、３で割り切れない数は２／３＝１−１／３あります。さらに、残っている数のうち、５で割り切れない数は１−１／５あります。したがって、ｘを越えない素数の個数はこれらの積をすべての素数ｐにわたってとればよいことになり、近似的に

Π（１−１／ｐ）・ｘ

に等しくなります。さらに、Π（１−１／ｐ）は近似的に１／ｌｏｇｘに等しくなります。ただし、これを証明するのは微積分を使っても容易ではありません。専門的で、ここで説明することはできそうにありませんから、天下り式に結果だけを示しておきます。このことを認めれば、素数定理π（ｘ）〜ｘ／ｌｏｇｘが導出されたことになります。

　さらに、素数定理にはもっとうまい近似法があります。素数の密度関数はπ（ｘ）／ｘですから、

π（ｘ）／ｘ〜１／ｌｏｇｘ　　　（ｘ→∞）

です。１／ｌｏｇｘが１からｘまでの平均的な素数の密度と考えられますが、これをｘの近くの素数の密度と考え、区間［１，ｘ］を小区間に区切って積分してみます。

Ｌｉ（ｘ）＝��₂^xｄｔ／ｌｏｇｔ

Ｌｉ（ｘ）は積分対数関数と呼ばれますが、π（ｘ）をｘ／ｌｏｇｘで近似するより、対数積分を用いたＬｉ（ｘ）の近似はさらに適切な素数分布の近似式になっています。

　素数が無限に存在すること・�浮Qが無理数であることは、ギリシア数学のなかでも有名な定理です。それぞれユークリッドとピタゴラスが背理法を用いて証明していますが、その証明はだれしもが容易に理解できるものです。同様に、調和級数Σ（１／ｎ）が無限大に発散すること

１／１＋１／２＋１／３＋・・・＝∞

も容易に示すことができます。それでは、素数の逆数の和

Σ（１／ｐ）＝１／２＋１／３＋１／５＋１／７＋１／１１＋・・・

は有限でしょうか？

（証明）

　調和級数１／１＋１／２＋１／３＋・・・は、オイラー積表示するとΠ（１−１／ｐ）^-1と書けますから、

Π（１−１／ｐ）^-1〜∞。

また、ｌｏｇΠ（１−１／ｐ）＝Σｌｏｇ（１−１／ｐ）。１／ｐが非常に小さいとき、マクローリン展開より、Σｌｏｇ（１−１／ｐ）〜−Σ（１／ｐ）ですから、Σ（１／ｐ）＝∞になります。したがって、すべての素数の逆数の和は発散することが示されます。調和級数Σ（１／ｎ）は発散し、また、オイラー級数Σ（１／ｎ² ）＝π² ／６で収束しますから、素数は平方数ほどまばらには分布していないことがわかります。

　さらに、このことを詳しく調べると、

Σ（１／ｐ）〜ｌｏｇ（ｌｏｇｘ）　（ｐはｐ≦ｘの素数を動く、証明略）

などがわかってきます。ｌｏｇ（ｌｏｇｘ）は１／（ｘｌｏｇｘ）の原始関数です。

　Σ（１／ｐ）はｘに近い整数について、その素因数の個数の近似値を与えるもので、ハーディーとラマヌジャンにより明らかにされています。インド生まれの数学者ラマヌジャンは、多くの公式や定理を発見し、神秘的な東洋の天才数学者とよばれていて、１日１つの割合で新しい公式または定理を発見したといわれています。ラマヌジャンは、素数と同じくらい風変わりな数として高次合成数の性質について探求しています。合成数とは素数でない数のことで、高次合成数とは２４のように１，２，３，４，６，８，１２，２４と多くの約数をもつ数のことです。ラマヌジャンについてはカニーゲル「無限の天才」（工作舎）をおすすめします。なお、これらの式から

Σｌｏｇ（１−１／ｐ）〜−ｌｏｇ（ｌｏｇｘ）

がでますが、両辺の指数をとると前にあげた

Π（１−１／ｐ）〜１／ｌｏｇｘ

が得られます。

　ガウスによって基礎づけられ、これらの数学者たちが磨き上げた素数定理はいまのところ不十分かつ不完全で、所詮、概算にすぎません。どれくらい速くこの比が１に近づくのかを特定できないし、ましてやある数まで数えてゆく間にいくつ素数があるのかを正確に教えてくれはしません。そのような精密な公式があれば素数定理より断然優ることはいうまでもありません。

２．素数生成式

　Ｆn ＝２^{2^n}＋１の形の素数をフェルマー素数といいます。Ｆ₀ ＝３，Ｆ₁ ＝５，Ｆ₂ ＝１７，Ｆ₃ ＝２５７，Ｆ₄ ＝６５５３７２５７は素数であることがわかります。フェルマーはこの型の数がすべて素数だと勘違いしていて必ず素数を与える式として考え出されたのですが、ｎ＝５であっけなく破綻してしまいました（Ｆ₅ ＝２^{2^5}＋１＝４２９４９６７２９７＝６４１×６７００４１７）。この間違いを発見したのはフェルマーから約１００年後のオイラーです。彼は約数６４１をあてずっぽうでみつけたのでも、２，３，５，７，・・・と割っていって執念で見つけたのでもありません。オイラーはＦ_n が合成数であるならば、それはあるｋに対してｋ２ⁿ⁺² ＋１であることを知っていて、Ｆ₅ の中の因数６４１＝５・２⁷ ＋１を見つけたのです。現在、ｎ＝０，１，２，３，４の５個以外にフェルマー素数はみつかっていません。

　また、オイラー自身、素数をかなりの確率で生成する公式ｎ² ＋ｎ＋４１を発見しています。この公式はｎ＝０のとき素数４１、ｎ＝１で素数４３、ｎ＝２で素数４７を与えます。このようにしてｎが０から３９までのどのｎをとってもオイラーの公式はすべて素数を与えます。オイラーの公式はｎ＝４０で１６８１＝４１2 となって破綻しますが、１０００万以下のｎに対して４７．５％の確率で素数を生成します。この事実を確認するのは簡単ですが、しかしオイラーはどうやってこんな事実を見つけだしたのでしょうか。また、そうなる真の理由は何でしょうか。

　ウラムは自然数を四角いらせん状に配列させるとｎ² ＋ｎ＋４１型の素数の多くはその対角線上に分布していることを確認しました。ランダムに分布しているように見える素数が四角い渦巻きの対角線上に規則的に分布していたことは驚くべきことです。ウラムは、また、１０００万以下のｎに対して４ｎ² ＋１７０ｎ＋１８４７が４６．６％、４ｎ² ＋４ｎ＋５９が４３．７％の確率で素数を生み出すことを突き止めています。

　オイラーの公式ｎ² ＋ｎ＋４１のｎをｎ−１に変換すればｎ² −ｎ＋４１、ｎ−４０に変換すればｎ² −７９ｎ＋１６０１が与えられます。１変数の２次多項式ではｎ² ＋ｎ＋１７や２ｎ² ＋２９なども高い確率で素数を生成します。それでは、多変数の高次多項式ではどうでしょうか。１９７１年、旧ソ連のマチアセビッチは、素数全体をあるひとつのディオファントス方程式の解として表すことにも成功しています。すなわち、すべての素数をつくる式を生み出したことになるのですが、その式は３７次で２４個の変数をもつ多項式と２１次で２１個の変数をもつ多項式でした。これらの多項式は負の値もとり、また、素数は多項式の値として繰り返し出現します。

　すべての素数をもれなくつくり、しかも素数以外はつくらない公式は知られていません。素数を完全に定義する式が存在することは証明されていませんし、存在しないともわかっていません。

３．素数判定法

　初項１，第２項１から始まり、隣り合う２項の和が次の項となる数列

１，１，２，３，５，８，・・・

をフィボナッチ数列とよびます。その一般項Ｆ_n は、Ｆ_n ＝Ｆ_n-1 ＋Ｆ_n-2 で

Ｆ_n ＝１／�浮T［｛（１＋�浮T）／２｝ⁿ −｛（１−�浮T）／２｝ⁿ ］

　　＝１／�浮T｛φⁿ −（−１／φ）ⁿ ｝

（Ｆ₀ ＝０：φ＝（１＋�浮T）／２）

と表すことができます。この式は１７６５年にオイラーが初めて発表したものですが、みんなに忘れられていてそれを再発見したビネにちなんでビネの公式（１８４３年）と命名されています。整数の数列に無理数である�浮Tや黄金比φが出現する不思議に驚かれた経験をお持ちの方の少なくないでしょう。ｎが大きくなるほど｛（１−�浮T）／２｝ⁿ は０に近づきますから、この項を無視するとフィボナッチ数列は黄金比を公比とする等比数列に次第に近づくことになります。

　また、フィボナッチ数列の各項はパスカルの三角形の対角線上の数の和に一致しています。この他にもフィボナッチ数は多くの性質をもっていて、以下にいくつか紹介しておきます。

Ｆ_n ・Ｆ_n+2 ＝Ｆ_n+1²−（−１）ⁿ

Ｆ₁ ＋Ｆ₂ ＋Ｆ₃ ＋・・・＋Ｆ_n ＝Ｆ_n+2 −１

Ｆ₁ ＋Ｆ₃ ＋Ｆ₅ ＋・・・＋Ｆ_2n-1＝Ｆ_2n

Ｆ₂ ＋Ｆ₄ ＋Ｆ₆ ＋・・・＋Ｆ_2n＝Ｆ_2n+1−１

Ｆ₁²＋Ｆ₂²＋Ｆ₃²＋・・・＋Ｆ_n²＝Ｆ_n ・Ｆ_n+1

　この数列にフィボナッチ（１３世紀のイタリアの数学者でピサのレオナルドとしても知られる）の名を冠したのはフランスの数学者リュカで、ハノイの塔の名で知られる２進法のパズルも１８８３年にリュカによって考案されたものです。　初項１，第２項３のフィボナッチ数列

１，３，４，７，１１，１８，・・・

は彼にちなんでリュカ数列と呼ばれています（１８７７年）。リュカ数列の一般項Ｌ_n は、

Ｌn ＝｛（１＋�浮T）／２｝ⁿ ＋｛（１−�浮T）／２｝ⁿ

　　＝｛φⁿ ＋（−１／φ）ⁿ ｝

（Ｌ₀ ＝２：φ＝（１＋�浮T）／２）

で表され、Ｌ_n ＝Ｆ_n-1 ＋Ｆ_n+1 の関係があります。リュカ数列はフィボナッチ数列と同じ漸化式をもち、連続する２つの項の比は黄金比に近づきます。

　さらに、１つの項の和がその前の３つの項の和になっているＦ_n ＝Ｆ_n-1 ＋Ｆ_n-2 ＋Ｆ_n-3 で定義される数列

１，１，１，３，５，９，１７，・・・

は、フィボナッチ数列の拡張とみなせるので、フィボナッチ（Fibonacci）をもじってトリボナッチ（Tribonacci）数列と呼ばれます。

　２ⁿ −１の形の数が素数であるためにはｎが素数であることが必要条件です。一方、２ⁿ ＋１の形が素数であるためにはｎ＝２m の形であることが必要です。しかし、このことは十分条件ではなく、指数ｎがどんな数のとき２ⁿ −１，２ⁿ ＋１が素数になるかはいまだに解決されていません。

　添字に２n をもつリュカ数列｛Ｌ_2^n｝、すなわち、３，７，４７，２２０７，４８７０８４７，・・・では、漸化式Ｌ_2^(n+1)＝（Ｌ_2^n）² −２が成り立ちますが、この漸化式とフェルマーの小定理（もしｐが素数であれば、任意の整数ａに関してａ^p −ａはｐの倍数である。１６４０年）を応用した素数判定法がリュカテストです。

　リュカはフィボナッチ数列、リュカ数列を用いてメルセンヌ数（２ⁿ −１）が素数であるかどうかを判定し、（２¹²⁷ −１）が素数であることを示しています（１８７６年）。この数は１２番目のメルセンヌ素数で、１９５２年の１３番目（２⁵²¹ −１）からはコンピュータによる発見ですから、コンピュータを使わずに見つけられた最大のメルセンヌ素数になっていて、わかっている最大の素数として最長不倒記録を保ち続けました。１９９４年、アメリカのスーパーコンピュータ、クレイによって発見された２５８７１６桁の巨大な素数（２⁸⁵⁹⁴³³−１）は現在知られている最大の素数（３３番目のメルセンヌ素数）ですが、リュカテストはメルセンヌ数が素数であるか否か判定する非常に能率的なアルゴリズムとなっていて、リュカテストの効率のよさのおかげで最近の素数の世界記録はすべてメルセンヌ素数が独占しています。

　なお、フェルマー数（２^{2^n}＋１）に対してはリュカテストと同じくらい能率的なペパンの素数判定法があり、コンピュータを使って６番目のフェルマー素数の探索が続けられているのですが、はたして本当に存在するのでしょうか（→【補】）。リュカやペパンの素数判定法によってある数が合成数とわかってもそれを素因数分解するのはとても大変な作業になります。現在、巨大な整数の素因数分解に楕円曲線法とか平方ふるい法とか能率のよい素因数分解法が考え出されています。

【補】スターリングの公式

　　数列｛ａ_n｝と｛ｂ_n ｝がともに無限大に発散し、差｛ａ_n −ｂ_n ｝は無限大に発散するが、比｛ａ_n ／ｂ_n ｝は１に近づくという例に、階乗ｎ！の近似値を与える公式として有名なスターリングの公式があります。

　　ｎ！〜�普i２πｎ）ｎⁿ ｅ^-n

　スターリングの公式ではｎが大きくなるほど相対誤差は小さくなります。スターリングの公式を誘導してみましょう。

ｌｏｇｎ！＝ｌｏｇ１＋ｌｏｇ２＋・・・＋ｌｏｇｘ

　　　　　＝Σｌｏｇｘ

ここで、ｙ＝ｌｏｇｘのグラフを幅が１の長方形に分割していくと、ｘが十分大きければ相対的に和の間隔が小さくなるので、和は積分に置き換えられます。

Σｌｏｇｘ�睡�₁^xｌｏｇｔｄｔ

ｌｏｇｘの原始関数は置換積分よりｘｌｏｇｘ−ｘ＋Ｃと計算されますから、右辺はｘｌｏｇｘ−ｘ＋１となります。したがって、

　　ｎ！�垂�ｎⁿ ｅ^-n

が得られます。もっと正確に近似すると

　��₁^xｌｏｇｔｄｔ

＝ｌｏｇ１＋ｌｏｇ２＋・・・＋ｌｏｇｘ−１／２ｌｏｇｘ＋δ

であること、また、

　　ワリスの公式：�父ﾎ〜（ｎ！）² ２²ⁿ／（２ｎ）！�浮�

より、結局、

　　ｎ！〜�普i２πｎ）ｎⁿ ｅ^-n

になります。スターリングの近似公式は階乗の一般化であるガンマ関数の近似値としても使われています。

　　Γ（ｘ＋１）＝�窒�^-tｔ^x ｄｔ〜�普i２πｘ）ｘ^x ｅ^-x

【補】フェルマー数

　フェルマー数は簡単な漸化式Ｆ_n ＝（Ｆ_n-1 −１）² ＋１を満たしています。この式からＦ_n −２＝Ｆ_n-1 （Ｆ_n-1 −１）＝・・・＝Ｆ₀ Ｆ₁ ・・・Ｆ_n-1

言い換えれば、Ｆ_n −２はそれより小さいすべてのフェルマー数で割り切れることがわかります。