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

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

  • 漸化式で表される数列における,割り算の余りの周期性(受験レベル)

  • 特に,フィボナッチ数列における周期について(難しい)

最後に,関連する入試問題として一橋大学の問題を紹介します。

余りの周期性

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

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

大雑把な説明

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

もう少し丁寧な証明

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

よって,漸化式を使うと,pp で割った余りについて an1+2an2+2an1+3an2+3    \begin{aligned} a_{n_1+2}&\equiv a_{n_2+2}\\ a_{n_1+3}&\equiv a_{n_2+3}\\ &\;\; \vdots \end{aligned} がわかる。つまり,帰納的に,任意の非負整数 NN に対して,

an1+Nan2+Na_{n_1+N}\equiv a_{n_2+N}

であることがわかる。言い換えると,n1n_1 以上である任意の整数 NN' に対して,

aNaN+n2n1a_{N'}\equiv a_{N'+n_2-n_1}

これは,数列の余りがループすること(そして,ループの周期が n2n1n_2-n_1 の約数であること)を表している。

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

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

フィボナッチ数列の余りの周期に関する定理

pp を素数とし,p2,5p\neq 2,5 とする。

pp55 で割った余りが 11 または 44 なら,周期は p1p-1 の約数

pp55 で割った余りが 22 または 33 なら,周期は 2(p+1)2(p+1) の約数

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

定理の証明(余りが 11 または 44 の場合)

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

証明

普通の三項間漸化式と同様に,

x2x+1(modp)x^2\equiv x+1\pmod{p}

という「特性合同式」を考える。以下 modp\mathrm{mod}\:p という記載は省略する。実は,pp55 で割った余りが 11 または 44 なら,この合同式を満たす 11 以上 p1p-1 以下の整数が2つ存在する(→補足1)ので,それらを α,β\alpha,\beta とおく。

普通の三項間漸化式と同様に,一般項は

anC1αn+C2βna_n\equiv C_1\alpha^n+C_2\beta^n

と書けそうである。実際,このようにすれば特性合同式より,an+2an+1+ana_{n+2}\equiv a_{n+1}+a_{n} を満たすので,あとは初期条件を満たすように C1,C2C_1,C_2 をうまく決めればよい。初期条件は,

C1α+C2β1C1α2+C2β21\begin{aligned} C_1\alpha+C_2\beta &\equiv 1\\ C_1\alpha^2+C_2\beta^2 &\equiv 1 \end{aligned}

である。2つめの式に,特性合同式: α2α+1\alpha^2\equiv \alpha+1 などを用いると,

C1(α+1)+C2(β+1)1C_1(\alpha+1)+C_2(\beta+1)\equiv 1

となる。これと1つめの式より,

C1+C20C_1+C_2\equiv 0

この結果と1つめの式より,C1=(αβ)1,C2=(αβ)1C_1=(\alpha-\beta)^{-1},C_2=-(\alpha-\beta)^{-1} となる(→補足2)。

結局,an(αβ)1(αnβn)a_n\equiv (\alpha-\beta)^{-1}(\alpha^n-\beta^n) である。この一般項の式に,フェルマーの小定理を適用すると,

an+p1(αβ)1(αn+p1βn+p1)(αβ)1(αnβn)an\begin{aligned} &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 \end{aligned}

であることがわかる。つまり,周期は p1p-1 の約数である。

補足1(特性合同式に解が存在することの証明):

まず,合同式を平方完成します。
x2x+14x24x+4(2x1)25\begin{aligned} x^2&\equiv x+1\\ 4x^2&\equiv 4x+4\\ (2x-1)^2&\equiv 5 \end{aligned} (法 pp は奇数なので,両辺を 44 倍しても同値であることに注意)

ここで,xx00 から p1p-1 の整数を動くとき,X=2x1X=2x-1 も法 pp において 00 から p1p-1 を1回ずつ動きます。よって,

X25(modp)X^2\equiv 5\pmod{p} に解が2つあることを示せば,もとの特性合同式にも解が2つ存在することがわかります。

ここで,平方剰余の相互法則を使うと,pp55 で割った余りが 11 または 44 なら,X25(modp)X^2\equiv 5\pmod{p} に解が少なくとも1つ存在することがわかります。さらに,X025(modp)X_0^2\equiv 5\pmod{p} なら,(pX0)25(modp)(p-X_0)^2\equiv 5\pmod{p} なので,2つめの解も存在します(pp は奇数なので X0X_0pX0p-X_0 は異なる解である)。

補足2(合同式の割り算):

(αβ)1(\alpha-\beta)^{-1} とは,c(αβ)1c(\alpha-\beta)\equiv 1 を満たす cc のことです。法 pp(αβ)(\alpha-\beta) は互いに素なので,そのような cc は(法 pp においてただ1つ)存在します。合同式の意味とよく使う6つの性質

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

関連する入試問題

2024年一橋大学後期の問題です。

問題

a1=a2=1a_1=a_2=1an+2=an+1+an(n1)a_{n+2}=a_{n+1}+a_n\:(n\geqq 1) で定まる数列 an{a_n} について a2024a_{2024}1313 で割った余りを求めよ。

1313 で割った余りはループするので頑張って計算するだけですが,周期は最大で 132=16913^2=169 になってしまい大変そうです。しかし,さきほどの定理を知っていれば周期が 2828 の約数であることがわかります! つまり,最大で 2828 個くらいまで計算すればOKなので安心してゴリ押しできます。

解答

1313 で割った余りについて,a1=a2=1a_1=a_2=1a3a_3 以降も計算していくと a29a301a_{29}\equiv a_{30}\equiv 1 で周期 2828 のループ。

一方,202420242828 で割った余りは 88 であるので a2024a88a_{2024}\equiv a_{8}\equiv 8 である。

高校数学の問題集 ~最短で得点力を上げるために~ のT161では,余りの周期性に関連する別の問題と2通りの解答を紹介しています。

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