ピサノ周期（Pisano周期）を徹底解説：定義・性質・計算法・応用と未解決問題

2025年12月11日 最終更新日時 : 2025年12月11日 エバープレイ編集部

はじめに：ピサノ周期とは何か

ピサノ周期（Pisano周期）とは、フィボナッチ数列を整数 m で割ったときに現れる周期のことを指します。具体的には、F_n を通常のフィボナッチ数（F_0=0, F_1=1, F_{n+1}=F_n+F_{n-1}）とすると、F_n mod m がある最小の正整数 T で周期的になるとき、その最小 T をピサノ周期 π(m) と定義します。つまり、すべての n について F_{n+T} ≡ F_n (mod m) が成り立つ最小の T が π(m) です。

基本的な性質と存在証明

π(m) の存在は簡単に示せます。フィボナッチ数列の値を mod m で見たとき、(F_n mod m, F_{n+1} mod m) の組が取る値の種類は m^2 個しかないため、ある i

具体例

  • π(2)=3（0,1,1,0,1,…）
  • π(3)=8（周期: 0,1,1,2,0,2,2,1）
  • π(5)=20
  • π(10)=60（10 に対して 6·10 が上界に達する例）

これらの具体例は、周期が m に依存する一方で単純な線形関係には従わないことを示しています。

乗法性と中国剰余定理

一般に、互いに素な m, n に対しては次が成り立ちます：

π(mn) = lcm(π(m), π(n)).

これは中国剰余定理に基づく標準的な結果です。したがって、任意の正整数のピサノ周期は素因数分解して素冪ごとに調べ、最終的に最小公倍数を取ることで得られます。すなわち、π(∏ p_i^{e_i}) = lcm(π(p_1^{e_1}), π(p_2^{e_2}), …) です。

素冪に関する性質

素 p に対して π(p^k) の振る舞いは理論的にも重要です。ウォール（D. D. Wall, 1960）の結果などから、一般に次が成り立ちます（特異例を除く）：

  • p ≠ 2,5 の場合、π(p^k) = p^{k-1}·π(p)。
  • p = 5 の場合は特別で、π(5)=20、および一般に π(5^k)=20·5^{k-1} が成り立ちます。
  • p = 2 の場合も特殊で、π(2)=3, π(4)=6, 以降 e≥3 について π(2^e)=3·2^{e-1} という形になります。

このため、素数 p に対する π(p) の理解が整数全体の π(m) を決定する鍵になります。

素数に対する周期の上界と判別

素数 p に対しては、判別式 D=5 を持つ二次方程式 x^2−x−1 の根と体論的な考察を用して周期の分解が可能です。具体的には、5 が平方剰余か否か（すなわち Legendre 記号 (5/p)）によって振る舞いが変わります。

p≠5 のとき、次が成り立ちます（Wall らによる既知の結果）：

π(p) は p − (5/p) の約数である。

ここで (5/p) は Legendre 記号で、(5/p)=1 のとき 5 は法 p における二次剰余であり、この場合 p−(5/p)=p−1、(5/p)=-1 のときは p+1 となります。したがって、直感的には 5 が平方剰余であれば π(p) は p−1 の約数、そうでなければ p+1 の約数である、というわけです。

一般的な上界

任意の正整数 m に対して知られている簡単な上界としては

π(m) ≤ 6m

があります。これは最良の細い上界ではないものの、実用上や概念上に有用です。実際、例として m=10 に対して π(10)=60 が等号を達成します。

計算法とアルゴリズム

ピサノ周期を直接求める最も単純な方法は F_n を順に計算して (0,1) の再出を待つ方法ですが、m が大きいと非効率です。効率的なアプローチとして

  • 素因数分解による分割：m を素因数分解して各素冪 p^k の周期を求め、最終的に lcm を取る方法。素冪に対する公式（上記）を使えば高速に計算できます。
  • 高速二乗倍法（fast doubling）でフィボナッチ数 F_n mod m を O(log n) で計算し、周期候補の因子を試す方法。π(p) が p−(5/p) の約数であることを利用して、約数だけを検査すれば済む点が重要です。
  • 行列の位数を求める方法：フィボナッチ数列は 2×2 行列 A = [[1,1],[1,0]] の累乗で表されるため、モジュラー行列環 GL(2, Z/mZ) における A の位数を求めれば π(m) が得られます（ただし A^T ≡ I となる最小 T が周期ではあるが、F_n の周期は A の位数に紐づく）。

実運用では、まず m を素因数分解（または試行除法で小さな素因数を取り除く）、各素因子について候補 t を列挙して fast doubling で F_t を検査、という流れが最も現実的です。

応用例と実用上の意味

ピサノ周期は純粋数学の話題に留まらず、計算機科学や暗号、擬似乱数、ハッシュ関数設計などでの周期性解析にも関係します。具体的には：

  • 大きなモジュロでのフィボナッチ数の周期性を利用した疑似乱数生成やアルゴリズム解析。
  • 線形再帰列の周期解析を通じた合同式ベースのアルゴリズム安定性の評価。
  • 数論的な攻撃や検証での、フィボナッチ数の特定の周期に関する性質の利用（ただし暗号設計で直接的に使う事例は限定的）。

未解決問題と研究の最前線

ピサノ周期に関しては既に多くの結果が知られていますが、未解決な問題もいくつかあります。代表的なものに「Wall–Sun–Sun 素数」に関する問題があります。これは素数 p が次の性質を持つかどうかを問うものです：

p^2 が F_{p − (5/p)} を割るような素数 p が存在するか？（存在が知られていない）

この問題は、かつてはフェルマーの最終定理の特定の証明アプローチにも関係づけられて注目されましたが、一般形での解決は得られていません。他にも π(p) の分布や成長に関する統計的性質、π(m) の平均的振る舞いなど活発な研究が続いています。

実装上の注意点

実際にプログラムで π(m) を計算する際のポイント：

  • まず m の素因数分解を試みる（大きな素因子があれば分解は計算量の支配要因になる）。
  • 候補 t を試す際は約数列挙を行い、小さい順に検査して最小周期を見つける。
  • F_n mod m の計算には fast doubling（O(log n)）を用いることで高速化できる。
  • 大きな m に対してはメモリや時間が問題となるため、適切に打ち切り条件や並列処理を検討する。

まとめ

ピサノ周期はフィボナッチ数列の合同的性質を測る基本的かつ豊かな対象です。存在は自明で、素因数分解と素冪ごとの性質（π(p^k) の公式）を組み合わせることで多くの m に対して効率的に計算できます。素数 p に対する π(p) が p−(5/p) の約数であるという結果や、π(mn)=lcm(π(m),π(n)) といった性質が理論的な骨格を与えます。一方で Wall–Sun–Sun 素数の存在など未解決問題も残されており、数論的興味は尽きません。

参考文献

カテゴリー
IT
前の記事
徹底解説：DC映画の歴史・潮流・評価とこれからの展望New!!
2025年12月11日
次の記事
マーベル作品を深掘り：MCUの歴史・構造・影響と今後の展望New!!
2025年12月11日