最終更新:2020/05/20

数列における余りの周期性(特にフィボナッチ数列)

分野: 整数問題  レベル: 数学オリンピック    

数列における余りの周期性について,以下の2つの話題を紹介します。

  • 漸化式で表される数列における,割り算の余りの周期性(受験レベル)
  • 特に,フィボナッチ数列における周期について(難しい)

余りの周期性

漸化式で表される数列の各項を特定の整数 $p$ で割った余りを考えると,ループするという性質が(多くの場合)成立します。

例えば,$a_1=a_2=1,a_{n+2}=a_{n+1}+a_{n}$ で表されるフィボナッチ数列の各項を $p$ で割った余りがループする(途中から同じパターンを繰り返す)ことを証明してみます。

大雑把な説明

各項を $p$ で割った余りは $0,1,\dots,p-1$ の $p$ 通りで有限個。よって,各項を $p$ で割った余りを初項から十分並べると,同じ2連続のパターンが現れる。同じ2連続のパターンが現れると,漸化式より,その後に続く数字たちの余りも同じなのでループする。

もう少し丁寧な証明

数列の各項は整数となる。各項を $p$ で割った余りは $0,1,\dots,p-1$ の $p$ 通りである。よって,隣り合うペア $(a_n,a_{n+1})$ をそれぞれ $p$ で割った余りのパターンは,高々 $p^2$ 通りである。よって,数列の最初の $p^2+1$ ペアを見ると,鳩の巣原理より,パターンが同じペア $(a_{n_1},a_{n_1+1}),(a_{n_2},a_{n_2+1})$ が存在する。(ただし,$n_1< n_2$)

よって,漸化式を使うと,$p$ で割った余りについて
$a_{n_1+2}\equiv a_{n_2+2}$
$a_{n_1+3}\equiv a_{n_2+3}$
$\vdots$
がわかる。つまり,帰納的に,任意の非負整数 $N$ に対して,
$a_{n_1+N}\equiv a_{n_2+N}$
であることがわかる。言い換えると,$n_1$ 以上である任意の整数 $N’$ に対して,
$a_{N’}\equiv a_{N’+n_2-n_1}$
これは,数列の余りがループすること(そして,ループの周期が $n_2-n_1$ の約数であること)を表している。

フィボナッチ数列における余りの周期

実は,フィボナッチ数列については,余りの周期について,より詳しい性質が知られています:

フィボナッチ数列の余りの周期に関する定理:
$p$ を素数とし,$p\neq 2,5$ とする。
$p$ を $5$ で割った余りが $1$ または $4$ なら,周期は $p-1$ の約数
$p$ を $5$ で割った余りが $2$ または $3$ なら,周期は $2(p+1)$ の約数

この記事では,上記の定理について「$5$ で割った余りが $1$ または $4$」の場合のみ,証明します。

定理の証明(余りが $1$ または $4$ の場合)

証明はかなり大変ですが,整数のいろいろな定理を駆使するので,理解できると楽しいです。

証明

普通の三項間漸化式と同様に,
$x^2\equiv x+1\:\mod p$
という「特性合同式」を考える。以下 $\mathrm{mod}\:p$ という記載は省略する。実は,$p$ を $5$ で割った余りが $1$ または $4$ なら,この合同式を満たす $1$ 以上 $p-1$ 以下の整数が2つ存在する(→補足1)ので,それらを $\alpha,\beta$ とおく。

普通の三項間漸化式と同様に,一般項は
$a_n\equiv C_1\alpha^n+C_2\beta^n$
と書けそうである。実際,このようにすれば特性合同式より,$a_{n+2}\equiv a_{n+1}+a_{n}$ を満たすので,あとは初期条件を満たすように $C_1,C_2$ をうまく決めればよい。初期条件は,
$C_1\alpha+C_2\beta\equiv 1$
$C_1\alpha^2+C_2\beta^2\equiv 1$
である。2つめの式に,特性合同式:$\alpha^2\equiv \alpha+1$ などを用いると,
$C_1(\alpha+1)+C_2(\beta+1)\equiv 1$
となる。これと1つめの式より,
$C_1+C_2\equiv 0$
この結果と1つめの式より,$C_1=(\alpha-\beta)^{-1},C_2=-(\alpha-\beta)^{-1}$ となる(→補足2)。

結局,$a_n\equiv (\alpha-\beta)^{-1}(\alpha^n-\beta^n)$ である。この一般項の式に,フェルマーの小定理を適用すると,
$a_{n+p-1}\\
\equiv (\alpha-\beta)^{-1}(\alpha^{n+p-1}-\beta^{n+p-1})\\
\equiv (\alpha-\beta)^{-1}(\alpha^n-\beta^n)\\
\equiv a_n$
であることがわかる。つまり,周期は $p-1$ の約数である。

補足1(特性合同式に解が存在することの証明):
まず,合同式を平方完成します。
$x^2\equiv x+1$
$4x^2\equiv 4x+4$
$(2x-1)^2\equiv 5$
(法 $p$ は奇数なので,両辺を $4$ 倍しても同値であることに注意)
ここで,$x$ が $0$ から $p-1$ の整数を動くとき,$X=2x-1$ も法 $p$ において $0$ から $p-1$ を1回ずつ動きます。よって,
$X^2\equiv 5\mod p$ に解が2つあることを示せば,もとの特性合同式にも解が2つ存在することがわかります。
ここで,平方剰余の相互法則を使うと,$p$ を $5$ で割った余りが $1$ または $4$ なら,$X^2\equiv 5\mod p$ に解が少なくとも1つ存在することがわかります。さらに,$X_0^2\equiv 5\mod p$ なら,$(p-X_0)^2\equiv 5\mod p$ なので,2つめの解も存在します($p$ は奇数なので $X_0$ と $p-X_0$ は異なる解である)。

補足2(合同式の割り算):
$(\alpha-\beta)^{-1}$ とは,$c(\alpha-\beta)\equiv 1$ を満たす $c$ のことです。法 $p$ と $(\alpha-\beta)$ は互いに素なので,そのような $c$ は(法 $p$ においてただ1つ)存在します。合同式の意味とよく使う6つの性質

参考文献:素数と2次体の整数論(青木昇著,共立出版)

合同式を初めて知ったときは,「$a\equiv b\mod p$ なんて書かずに,$a$ と $b$ は $p$ で割った余りが同じ」と書けばいいじゃん,と思ったものですが,今回のように複雑な証明になると,合同式無しでは厳しいですね!