初項１，第２項１から始まり，隣り合う２項の和が次の項となるフィボナッチ数列

　　１，１，２，３，５，８，１３，２１，３４，５５，８９，・・・

の各項を２で割った余りをとると（ｍｏｄ２で考えると），

　　１，１，０，１，１，０，・・・

３項ごとに元に戻ることがわかる．

　

　３で割った余りなら，

　　１，１，２，０，２，２，１，０，１，１，２，・・・

のように８項毎に元に戻る．

　

　ｍｏｄ５のとき，

　　１，１，２，３，０，３，３，１，４，０，４，４，３，２，０，２，２，４，１，０，１，１，２，・・・

２０項毎に循環している．

　

　ｍｏｄ７のとき，

　　１，１，２，３，５，１，６，０，６，６，５，４，２，６，１，０，１，１，・・・

１６項毎に循環している．

　

　このような性質を周期性というのだが，任意の自然数でフィボナッチ数を割っていくと，必ず周期性が現れる．循環節の長さには，はたしてどういう規則があるのだろうか？

　

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

　

【１】黄金比とフィボナッチ数

　

　正五角形の１辺と対角線の長さの比が＜黄金比＞です．黄金比φは２次方程式：ｘ2 −ｘ−１＝０の根であり，φ＝（√５＋１）／２＝１．６１８です．１／φ＝φ−１ですから，黄金比の逆数１／φは（√５−１）／２＝０．６１８になります．

　

　黄金比は，古来より調和のとれた美しい比としてたくさんの美術作品の中に使われてきました．縦横比が黄金比，すなわち１：（√５＋１）／２＝１：１．６１８の長方形を黄金長方形とよびます．岩波新書版の縦横比もおおよそ黄金比倍になっています．また，植物の葉序に黄金比が使われていることは有名な話であり，黄金比は身近な現象にもしばしば登場しこの種の話題には事欠きません．

　

　黄金長方形から正方形を取り去ると再び小さい黄金長方形が残ります．同様にしてこの手続きは無限に続行できます．したがって，黄金比はユークリッドの互除法によって「１」だけを使って連分数に展開できる無理数であり，すなわち，

　　（１＋√５）／２＝［１；１，１，１，１，１，・・・］

その意味では最もゆっくり収束する無理数であり，最もシンプルなフラクタル生成装置ともいえます．

　

　黄金比φには多くの性質があり，

　　１，φ，φ^2，φ^3，φ^4，φ^5，・・・

という等比数列を考えると，

　　１＋φ＝φ^2

ですから

　　φ^n＝φ^(n-1)＋φ^(n-2)

　

　ここで，ガウス記号［ｘ］（ｘを超えない最大の整数）を用いると，数列｛［φ^(n-1)］｝の各次数に対応して得られる整数列は

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

すなわち，フィボナッチ数列｛Ｆn｝となります．

　

［補］白銀長方形

　

　縦横比が白銀比，１：√２＝１：１．４１４の長方形を白銀長方形とよびます．白銀長方形の長辺を２等分すると，半分の面積の白銀長方形となります．この性質を利用して，白銀比は世界中で用紙の大きさとして使われています．

　

　黄金比とは正五角形の１辺と対角線の長さの比であり，白銀比とは正方形の１辺と対角線の長さの比のことですが，正多角形の中で１辺と対角線の長さの比が一定に決まるのは，この２つだけしかありません．正三角形には対角線はなく，正六角形以上では対角線の長さが２種類以上になるからです．

　

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

　

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

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

をフィボナッチ数列とよびます．

　

　一般に，数列｛Ｘn−αＸn-1｝が公比βの等比級数になるものと仮定すると，

　　Ｘn+1−αＸn＝β（Ｘn−αＸn-1）

すなわち，

　　Ｘn+1−（α＋β）Ｘn＋αβＸn-1＝０

根と係数の関係から，α，βは

　　ｘ^2−（α＋β）ｘ＋αβ＝０

の根でなけれならないのですが，このことから，この数列は２つの等比級数の１次結合

　　Ｘn＝ｃα^n＋ｄβ^n

として表されます．

　

　フィボナッチ数列の一般項Ｆnは，３項漸化式：

　　Ｆn＝Ｆn-1＋Ｆn-2

の特性方程式

　　ｘ^2−ｘ−１＝０

の２つの解：

　　α＝（１＋√５）／２，β＝（１−√５）／２

より，

　　Ｆn ＝１／√５［｛（１＋√５）／２｝^n−｛（１−√５）／２｝^n］

　　　　＝１／√５｛φ^n−（−１／φ）^n｝

　　　　　（Ｆ0 ＝０：φ＝（１＋√５）／２）

のように黄金比φを使って表すことができます．

　

　この式は１７６５年にオイラーが初めて発表したものですが，みんなに忘れられていてそれを再発見したビネにちなんでビネの公式（１８４３年）と命名されています．整数の数列に無理数である√５や黄金比φが出現する不思議に驚かれた経験をお持ちの方の少なくないでしょう．かくいう小生も心理的抵抗感を禁じ得なかったひとりです．

　

　第１項は等比級数的に増大し，第２項は符号が入れ替わりながら等比級数的に減少します．ｎが大きくなるほど第２項｛（１−√５）／２｝^nは０に近づきますから，この項を無視するとフィボナッチ数列は黄金比を公比とする等比数列に次第に近づくことになります．

　　Ｆn ＝φ^n／√５

　

　また，フィボナッチ数列の各項はパスカルの三角形の対角線上の数の和に一致しています．２項係数とフィボナッチ数の間にも多くの関係があるのですが，この他にもフィボナッチ数は多くの性質をもっていて，以下にいくつか紹介しておきます．

　　Ｆn・Ｆn+2＝Ｆn+1^2−（−１）^n

　　Ｆ1＋Ｆ2＋Ｆ3＋・・・＋Ｆn＝Ｆn+2−１

　　Ｆ1＋Ｆ3＋Ｆ5＋・・・＋Ｆ2n-1＝Ｆ2n

　　Ｆ2＋Ｆ4＋Ｆ6＋・・・＋Ｆ2n＝Ｆ2n+1−１

　　Ｆ1^2＋Ｆ2^2＋Ｆ3^2＋・・・＋Ｆn^2＝Ｆn・Ｆn+1

　

　有名な幾何学的パラドックス＜６４ｃｍ^2＝６５ｃｍ^2＞は，「不思議の国のアリス」の作者であるルイス・キャロルが創ったとも，パズルの大御所であるサム・ロイドが創ったともいわれているパズルです．きっと，いろいろな本でみたことのある方も多いと思います．

　

　このトリックは一直線をなすように使われた２つの線分の傾き３／８，５／１３の相違がわれわれの視力の限界外となる錯覚を利用したもので，もっと先の数，たとえば８／２１とかを使えばより巧妙なトリックになります．公式

　　Ｆn・Ｆn+2＝Ｆn+1^2−（−１）^n

は，３つ並んだフィボナッチ数の真ん中の数の平方は前後の２つの数の積より１大きいか小さいかのどちらかで，このトリックパズルのもとになっています．

　

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

　

　隣り合う２項の和が次の項となる数列はフィボナッチ数列の名で有名ですが，フィボナッチ数列｛Ｆn｝の通常型母関数ｆ（ｘ）は

　　　　ｆ（ｘ）＝Ｆ0＋Ｆ1ｘ＋Ｆ2ｘ^2＋Ｆ3ｘ^3＋・・・

　　　ｘｆ（ｘ）＝　　　Ｆ0ｘ＋Ｆ1ｘ^2＋Ｆ2ｘ^3＋・・・

　　ｘ^2ｆ（ｘ）＝　　　　　　　Ｆ0ｘ^2＋Ｆ1ｘ^3＋・・・

また，Ｆn＝Ｆn-1＋Ｆn-2より

　　ｆ（ｘ）＝ｘ／（１−ｘ−ｘ^2）＝ΣＦnｘ^n

と簡単な式になります．

　

　さらに，１つの項の和がその前の３つの項の和になっている

　　Ｔn＝Ｔn-1＋Ｔn-2＋Ｔn-3

で定義される数列

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

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

　

　この数列でも連続する２項の比はある決まった値

　　１／３｛3√（１９＋３√３３）＋3√（１９−３√３３）＋１｝＝１．８３９・・・

に収束します．これは

　　　ｘ^3−ｘ^2−ｘ−１＝０

の実根です．トリボナッチ数列は３次のフィボナッチ数列ですが，ｋ次に一般化することもできるでしょう．

　

［補］通常型母関数と指数型母関数

　

　数列は補助変数ｘを用いてベキ級数としてうまく表すことができます．数列｛ａn｝，すなわち，ａ0，ａ1，ａ2，・・・に対して，

　　ａ0＋ａ1ｘ＋ａ2ｘ^2＋・・・＝Σａnｘ^n＝ｆ（ｘ）

で表される関数ｆ（ｘ）をその通常型母関数といいます．

　

　一方，

　　ａ0／０！＋ａ1／１！ｘ＋ａ2／２！ｘ^2＋・・・

を数列｛ａn｝に対する指数型母関数と呼びます．ｅｘｐ（ｘ）は数列｛１，１，１，・・・｝の指数型母関数です．

　

　フィボナッチ数列｛Ｆn｝の指数型母関数

　　ｆ（ｘ）＝ΣＦnｘ^n／ｎ！

は微分方程式

　　ｙ”＝ｙ＋ｙ’

を満足するので，

　　ｙ＝Ａｅｘｐ（λｘ）＋Ｂｅｘｐ（μｘ）

の形となります．

　

　ここで，λ，μは２次方程式

　　ｘ^2＝１＋ｘ

の解ですから，

　　λ＝（１＋√５）／２，μ＝（１−√５）／２

また，Ａ，Ｂを定めるためには

　　ｆ（ｘ）＝Ａｅｘｐ（λｘ）＋Ｂｅｘｐ（μｘ）

　　ｆ’（ｘ）＝Ａλｅｘｐ（λｘ）＋Ｂμｅｘｐ（μｘ）

において，ｘ＝０とおくと，Ａ＝１／√５，Ｂ＝−１／√５

　

　以上より，

　　φ＝（１＋√５）／２，−１／φ＝（１−√５）／２

とおくと，指数型母関数は

　　ｆ（ｘ）＝１／√５［ｅｘｐ（φｘ）−ｅｘｐ（−ｘ／φ）］

となります．

　

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

　

【２】フィボナッチ数の周期性

　

　フィボナッチ数Ｆnにはある程度の周期性があります．たとえば，フィボナッチ数の１の位は周期６０で循環します．すなわち，Ｆ1，Ｆ61，Ｆ121の１の位は等しくなります．周期はずっと長くなりますが，下２桁（３００周期），下３桁（１５００周期）でも周期性があります．

　

　１の位が６０の周期をもつことのＦnの１の位とは，単にＦn（ｍｏｄ１０）のことです．Ｆn（ｍｏｄ　ｍ）も周期的になるのですが，ここで，Ｆn（ｍｏｄ　ｍ）の循環部分の長さを表にしてみましょう．

　

　　　　　ｍ　　Ｆn の周期　　　　　ｍ　　Ｆn の周期

　　　　　１　　　　１　　　　　　　９　　　２４

　　　　　２　　　　３　　　　　　１０　　　６０

　　　　　３　　　　８　　　　　　１１　　　１０

　　　　　４　　　　６　　　　　　１２　　　２４

　　　　　５　　　２０　　　　　　２５　　１００

　　　　　６　　　２４　　　　　１００　　３００

　　　　　７　　　１６　　　　１０００　１５００

　　　　　８　　　１２

　

　周期の長さはいろいろですが，そこには何か規則性が隠されているように感じられます．実際，フィボナッチ数列をｍで割った余りについての周期の長さをｆ（ｍ）とすると，

　　ｆ（ｍ）が奇数→ｍ＝２

　　ｆ（ｍ）＝４ｓ→Ｆ2s＝０（ｍｏｄ　ｍ）

が成り立ちます．

　

　また，周期性はいくつかの整数を法とする合同で計算（わり算）を行ったときの余りに関連することなので，整除性（ある特定の整数で割り切れるという性質）と密接に関係します．

　

　Ｆ3＝２ですが，２の倍数は３項ごとに現れます．以下，

　　Ｆ4＝３　→　３の倍数は４項ごとに現れる

　　Ｆ5＝５　→　５の倍数は５項ごとに現れる

　　Ｆ6＝８　→　８の倍数は６項ごとに現れる

　

　これにより，フィボナッチ数はきれいな規則性に従って並んでいることがわかりますが，フィボナッチ数の整除性をまとめると，

(1)各素数ｐに対して，ｐで割り切れるようなＦnがある．

(2)奇素数ｐ（ｐ≠５）に対して

　　ｐ＝±１（ｍｏｄ５）→Ｆp-1＝０（ｍｏｄｐ）

　　ｐ＝±２（ｍｏｄ５）→Ｆp+1＝０（ｍｏｄｐ）

すなわち，

　　ｐ＝±１（ｍｏｄ５）に対するＦp-1はｐで割り切れる．

　　ｐ＝±２（ｍｏｄ５）に対するＦp+1はｐで割り切れる．

　　ｐ＝５ならばｐ＝Ｆp

(3)奇素数に対して

　　Ｆp＝５^((p-1)/2)（ｍｏｄ５）

なので，

　　ｐ＝±１（ｍｏｄ５）←→Ｆp＝＋１（ｍｏｄｐ）

　　ｐ＝±２（ｍｏｄ５）←→Ｆp＝−１（ｍｏｄｐ）

　

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

　

【３】フィボナッチ数列と有限体

　

　いよいよ，今回のコラムのメインテーマとなるのですが，循環節の長さにどういう規則があるのかという問題に突入します．

　　ｆ（ｍ）が奇数→ｍ＝２

　　ｆ（ｍ）＝４ｓ→Ｆ2s＝０（ｍｏｄ　ｍ）

だけではつまらないでしょう．

　

　ここでは有限体を扱うので，フィボナッチ数列を奇素数ｐを法として考えることにします．すると，奇素数ｐに対して循環する項数をｆ（ｐ）とすると，

　　ｆ（３）＝８，ｆ（５）＝２０，ｆ（７）＝１６，ｆ（１１）＝１０，

　　ｆ（１３）＝２８，ｆ（１７）＝３６，ｆ（１９）＝１８，・・・

となっていますから，

　　ｐ＝±１（ｍｏｄ５）のとき，ｆ（ｐ）＝ｐ−１

　　ｐ＝±２（ｍｏｄ５）のとき，ｆ（ｐ）＝２ｐ＋２

と予想できます．

　

　ただし，５は例外としておき，ｐは５以外の奇素数であるとします．そのとき，ビネの公式：

　　Ｆn ＝１／√５［｛（１＋√５）／２｝^n−｛（１−√５）／２｝^n］

はｍｏｄｐで考えても意味をもつことになります．

　

　コラム「因数分解の算法（その３）」の復習になるのですが，

(1)もし√５すなわちｘ^2＝５の根が有限体Ｆpの中にあれば，ビネの公式はＦpの元として意味をもつ

(2)Ｆpの中になければ，その根はＦp^2の中にあり，その根の一つを√５とすれば，ビネの公式はＦp^2の元として意味をもつ

ことになります．

　

　たとえば，ｐ＝１１であるとすると，方程式ｘ^2＝５（ｍｏｄ１１）の根として，ｘ＝４とｘ＝７の２根がありますから，√５＝４とおくと，７＝−４＝−√５

したがって，

　　（１＋√５）／２＝５／２＝５・６＝８

　　（１−√５）／２＝−３／２＝８／２＝４

より，法１１でのフィボナッチ数列の一般項は

　　Ｆn＝１／４（８^n−４^n）＝３・（８^n−４^n）

　

　確認のために計算してみると

　　Ｆ1＝３・４＝１，Ｆ2＝３・４＝１，Ｆ3＝３・８＝２，

　　Ｆ4＝３・１＝３，Ｆ5＝３・９＝５，・・・

となり，正しいことが確認されます．

　

　次に，ｐ＝７とすると，ｘ^2＝５（ｍｏｄ７）はＦ7の中には根をもたないので，ｘ^2＝５の一つの根を√５とおき，それをＦ7につけ加えて有限体Ｆ7^2をつくることができます．そのとき，もう一つの根は−√５になっており，一般項は

　　Ｆn ＝１／√５［｛（１＋√５）／２｝^n−｛（１−√５）／２｝^n］

とまったく同じ式で与えられます．

　

　　Ｆ1 ＝１／√５［｛（１＋√５）／２｝−｛（１−√５）／２｝］

　　　　＝１／√５・√５＝１

　　Ｆ2 ＝１／√５［｛（１＋√５）／２｝^2−｛（１−√５）／２｝^2］

　　　　＝１／√５・√５＝１

　　Ｆ3 ＝１／√５［｛（１＋√５）／２｝^3−｛（１−√５）／２｝^3］

は２^3＝１を用いると

　　Ｆ3 ＝１／√５［（２＋√５）−（２−√５）］＝２

となって正しいことが確認されます．

　

　５以外の奇素数ｐに対して，方程式ｘ^2＝５は

(1)ｐ＝±１（ｍｏｄ５）ならば，有限体Ｆpの中に根をもつ

(2)ｐ＝±２（ｍｏｄ５）ならば，有限体Ｆpの中に根をもちません．

　

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

　

　懸案の予想

　　ｐ＝±１（ｍｏｄ５）のとき，ｆ（ｐ）＝ｐ−１

　　ｐ＝±２（ｍｏｄ５）のとき，ｆ（ｐ）＝２ｐ＋２

を証明してみましょう．

　

　これを示すには，

　　Ｆf(p)＝０，Ｆf(p)+1＝１

が成り立つことをいえばよいのですが，ｐ＝±１（ｍｏｄ５）のとき，ｘ^2＝５を満たす元ｃが有限体Ｆpのなかにありますから，

　　Ｆf(p)＝Ｆp-1

　　　　　＝１／ｃ［｛（１＋ｃ）／２｝^(p-1)−｛（１−ｃ）／２｝^(p-1)］

　

　ここで，フェルマーの定理により，有限体Ｆpのどんな元も

　　ａ^(p-1)＝１

（ｐ乗すると元に戻る）ですから，　

　　Ｆf(p)＝Ｆp-1＝１／ｃ（１−１）＝０

　

また，

　　Ｆf(p)+1＝Ｆp

　　　　　　＝１／ｃ［｛（１＋ｃ）／２｝^p−｛（１−ｃ）／２｝^p］

　　　　　　＝１／ｃ［｛（１＋ｃ）／２｝−｛（１−ｃ）／２｝］

　　　　　　＝１／ｃ・ｃ

　　　　　　＝１

が示されました．

　

　一方，ｐ＝±２（ｍｏｄ５）のとき，有限体Ｆpの中に根をもちませんから，一般項は

　　Ｆn ＝１／√５［｛（１＋√５）／２｝^n−｛（１−√５）／２｝^n］

とまったく同じ式で与えられます．

　

　ここで，［］の中を展開しますが，二項係数pＣiは常にｐで割り切れること，有限体Ｆp^2の元ａ＋ｂ√５（ａ，ｂは有限体Ｆpの元）に対して

　　（ａ＋ｂ√５）^p＝ａ−ｂ√５

となることより，

　　｛（１＋√５）／２｝^(2p+2)＝（３＋√５）^(p+1)／２^(p+1)

　　＝（３＋√５）^p（３＋√５）／４

　　＝（３−√５）（３＋√５）／４＝１

　

　まったく同様にして

　　｛（１−√５）／２｝^(2p+2)＝１

より，

　　Ｆf(p)＝Ｆ2p+2＝０

　

　さらに，

　　Ｆf(p)+1＝Ｆ2p+3

　＝１／√５［｛（１＋√５）／２｝^(2p+3)−｛（１−√５）／２｝^(2p+3)］

　＝１／√５［｛（１＋√５）／２｝−｛（１−√５）／２｝］

　＝１

　

　これで予想が証明されたことになりますが，同時に，５以外の奇素数ｐに対して，フィボナッチ数の第ｆ（ｐ）項はｐで割り切れることが示されました．

　

　なお，この定理の証明は

　　［参］硲文夫「初等代数学」森北出版

に負っています．実は，小生，有限体を使ったこの意外な証明に驚いて，本コラムでも是非紹介したいと考えた次第です．如何でしたでしょうか？

　

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

　

［補］リュカ数列と素数判定法

　

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

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

　

　初項１，第２項３のフィボナッチ数列

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

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

　　Ｌn ＝｛（１＋√５）／２｝^n＋｛（１−√５）／２｝^n

　　　　＝｛φ^n＋（−１／φ）^n｝

　　　　　（Ｌ0＝２：φ＝（１＋√５）／２）

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

　

　　　　　ｍ　　Ｌn の周期　　　　　ｍ　　Ｌn の周期

　　　　　１　　　　１　　　　　　　９　　　２４

　　　　　２　　　　３　　　　　　１０　　　１２＊

　　　　　３　　　　８　　　　　　１１　　　１０

　　　　　４　　　　６　　　　　　１２　　　２４

　　　　　５　　　　４＊　　　　１００　　　６０＊

　　　　　６　　　２４　　　　１０００　　３００＊

　　　　　７　　　１６

　　　　　８　　　１２

　

　リュカ数にはフィボナッチ数とは別の周期性が現れます．フィボナッチ数と異なるところに＊印を付けておきました．とはいっても，リュカ数の周期とフィボナッチ数の周期は全部ではないにしても，ほとんどが一致します．

　

　両者の決定的な違いは，フィボナッチ数の循環節には必ず０が現れるのに対して，リュカ数のｍ＝５やｍ＝８の循環節には０が出てこないということです．これはリュカ数が５や８では決して割り切れないということを意味しています．もちろん５と８の倍数でも割れません．フィボナッチ数では任意の自然数ｍに対して，必ず割り切れるＦnが存在します．

　

　また，フィボナッチ数とリュカ数の性質は，整除性という点でも大分様子が違っています．２の倍数は３項ごとに現れる，３の倍数は４項ごとに現れるなどは似ていますが，５の倍数や８の倍数は出てきません．フィボナッチ数がきれいな規則性に従って並んでいるのに対し，リュカ数では１，３から始めて前の２項を加えるという規則を多少変えただけで，そうはならないのです．

　

　リュカ数の整除性をまとめると

(1)素数ｐに対して

　　Ｌp＝１　（ｍｏｄｐ）

(2)奇素数（ｐ≠５）に対して

　　ｐ＝±１（ｍｏｄ５）→Ｌp-1＝＋２（ｍｏｄｐ）

　　ｐ＝±２（ｍｏｄ５）→Ｌp+1＝−２（ｍｏｄｐ）

　

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

　

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

　

　添字に２^nをもつリュカ数列｛Ｌ2^n｝，すなわち，３，７，４７，２２０７，４８７０８４７，・・・では，漸化式Ｌ2^(n+1)＝（Ｌ2^n）^2−２が成り立ちますが，この漸化式とフェルマーの小定理（１６４０年）

　　「もしｐが素数であれば，任意の整数ａに関してａ^p−ａはｐの倍数である．」を応用した素数判定法がリュカテストです．

　

　リュカはフィボナッチ数列，リュカ数列を用いてメルセンヌ数（２^n−１）が素数であるかどうかを判定し，（２^127−１）が素数であることを示しています（１８７６年）．この数は１２番目のメルセンヌ素数で，１９５２年の１３番目（２^521−１）からはコンピュータによる発見ですから，コンピュータを使わずに見つけられた最大のメルセンヌ素数になっていて，わかっている最大の素数として最長不倒記録を保ち続けました．

　

　１９９４年，アメリカのスーパーコンピュータ，クレイによって発見された２５８７１６桁の巨大な素数（２^859433−１）は現在知られている最大の素数（３３番目のメルセンヌ素数）ですが，リュカテストはメルセンヌ数が素数であるか否か判定する非常に能率的なアルゴリズムとなっていて，リュカテストの効率のよさのおかげで最近の素数の世界記録はすべてメルセンヌ素数が独占しています．

　

　なお，フェルマー数（２^(2^n)＋１）に対してはリュカテストと同じくらい能率的なペパンの素数判定法があり，コンピュータを使って６番目のフェルマー素数の探索が続けられているのですが，はたして本当に存在するのでしょうか？

　

　リュカやペパンの素数判定法によってある数が合成数とわかってもそれを素因数分解するのはとても大変な作業になります．現在，巨大な整数の素因数分解に楕円曲線法とか平方ふるい法とか能率のよい素因数分解法が考え出されています．

　

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