競技数学解説

文献あり

フィボナッチ数列の応用いろいろ

Zsigmondyの定理,フィボナッチ数列,LTEの補題

1229

フィボナッチ数は「指数-指数」と同じようなふるまいをすることに前回までの記事で触れてきました. ので, 「指数-指数」で有名な性質, LTEの補題とZsigmondyの定理を中心に, フィボナッチ数列の応用例をいくつか書いていきます！

証明中の記法など

$F_{n} \dots n$ 番目のフィボナッチ数. $F_{1} = 1, F_{2} = 1, F_{3} = 2, \dots$
$a | b \dots a$ が $b$ の約数である.
$(\binom{a}{b}) \dots$ 二項係数 $_{a} C_{b}$
$φ (n) \dots$ Eulerのトーシェント関数, $n$ と互いに素な $1$ 以上 $n$ 以下の整数の個数
$v_{p} (n) \dots$ 整数 $n$ が素数 $p$ で割り切れる回数の最大値

前回の記事およびそこから飛べる過去の記事の結果を色々使います.

まずはLTEから.

LTEの類似

前回の記事のなかで扱ったフィボナッチ数列におけるLTEの補題の類似を示していきます. といっても, 証明は普通のLTEとほとんど同じです. (そしてじゅんにーさんのこの記事が以下の結果を包含しています. )

追記 OMC040Fの解説にまったく同じ手法が用いられていることを発見しました. 議論の流れ上、該当部分の削除はいたしませんが、その点に十分ご留意ください

任意の正整数 $k$ , 整数 $n$ に対して以下の式が成立する.
$\begin{aligned} 2 F_{k n} & = (\binom{k}{1}) F_{n} L_{n (k - 1)} - 5 (\binom{k}{2}) F_{n}^{2} F_{n (k - 2)} + 5 (\binom{k}{3}) F_{n}^{3} L_{n (k - 3)} - 5^{2} (\binom{k}{4}) F_{n}^{4} F_{n (k - 4)} \\ + \dots \\ + 5^{i - 1} (\binom{k}{2 i - 1}) F_{n}^{2 i - 1} L_{n (k - (2 i - 1))} - 5^{i} (\binom{k}{2 i}) F_{n}^{2 i} F_{n (k - 2 i)} \\ + \dots \end{aligned}$
ここで, $L_{0} = 2, L_{1} = 1, L_{n + 2} = L_{n + 1} + L_{n}$ である(リュカ数列, ルカス数列と呼ばれるもの).
なお, 上の式は有限和である.

概略

$α = \frac{1 + \sqrt{5}}{2}, β = \frac{1 - \sqrt{5}}{2}$ とおく. $((α^{k} - β^{k}) + β^{k})^{n} - α^{k n}$ を二項定理で展開し, $β^{n} = \frac{L_{n} - \sqrt{5} F_{n}}{2}, F_{n} = \frac{1}{\sqrt{5}} (α^{n} - β^{n})$ を代入したのち $\sqrt{5}$ の係数を比較することにより所望の式を得る.

LTEの類似

$p$ を奇素数, $p | F_{n}$ とするとき
$v_{p} (F_{k n}) = v_{p} (F_{n}) + v_{p} (k)$
が成立する

補題1の右辺第一項について考える.
$p | F_{n}$ より $p | F_{n (k - 1)}$ であるが, もし $p | L_{n (k - 1)}$ だと仮定すると $p | 5 F_{n (k - 1)}^{2} - L_{n (k - 1)}^{2}$ より $p | 4$ であるが, これは不適. 従って,
$v_{p} (k F_{n} L_{n (k - 1)}) = v_{p} (F_{n}) + v_{p} (k)$
である. また, 右辺第二項以降について,
$v_{p} ((\binom{k}{i}) F_{n}^{i}) = i v_{p} (F_{n}) + v_{p} ((\binom{k}{i})) = i v_{p} (F_{n}) + v_{p} (\frac{k}{i} (\binom{k - 1}{i - 1})) \geq i - 1 + v_{p} (F_{n}) + v_{p} (k) - v_{p} (i) > v_{p} (F_{n}) + v_{p} (k)$
であるので示された.

$p = 2$ は前回の方法で頑張りましょう.

使ってみよう！

LTEを使ってみます.

素数 $p$ , 正の整数 $n$ に対して $\frac{F_{n p}}{F_{n}} (\in N)$ の素因数を $\frac{x^{p} - 1}{x - 1}$ の素因数と同じように考察してみます.

奇素数 $q | \frac{F_{n p}}{F_{n}}$ を任意にとる.

$q$ が $F_{n}$ を割り切るとき
定理2より $v_{q} (F_{p n}) = v_{q} (F_{n}) + v_{q} (p)$ なので, $p = q$ が従う.
$q$ が $F_{n}$ を割りらないとき
$F_{n p}, F_{q or q \pm 1}$ のどちらも $q$ の倍数なので, $q | F_{gcd (n p, q or q \pm 1)}$ であり, 場合分けの仮定より $gcd (n p, q or q \pm 1) |̸ F_{n}$ である. これより $gcd (n p, q or q \pm 1) |̸ n$ , 従って $p | q or q \pm 1$ である. つまり $q$ は $mod p$ で $\pm 1, 0$ のいずれかに合同である.

また, $2 | \frac{F_{n p}}{F_{n}}$ となるのは前回の補題より $p = 2, 3$ の場合のみなので結局 $\frac{F_{n p}}{F_{n}}$ の素因数は $mod p$ で $\pm 1, 0$ のいずれかに合同なものだけである. 特にすべて $p - 1$ 以上である.
多項式の場合と似た結果が得られました！

$4$ で割って $1$ 余る素数の評価

整数コン 5についてです.

上の結果において, $p$ を $13$ 以上の素数, $n = 1$ とします. このとき, $F_{p}$ は $p - 1$ 以上の素因数しか持たず, $p$ と $q$ の偶奇の考察および $p \neq 5$ なのでこれは $p + 1$ 以上です. さらに,
$F_{p} = F_{(p + 1) / 2}^{2} + F_{(p - 1) / 2}^{2}$
が成立し, $F_{(p + 1) / 2}$ と $F_{(p - 1) / 2}$ が互いに素であることを併せれば, $F_{p}$ の素因数は全て $4$ で割って $1$ 余ります(一般に $a^{2} + b^{2}$ の素因数の議論). 従って, $p = 5$ の場合も考慮に入れれば, すべての $4$ で割って $1$ 余る素数 $p$ に対して $p + 1$ 以上 $F_{p} + 8$ 以下の, $4$ で割って $1$ 余る素数が存在することが言えました.

指数を含む不定方程式への利用

$l (5) = 5, F_{5} = 5$ であることと, LTEより $v_{5} (F_{n}) = v_{5} (n)$ が分かります. これより, $F_{n} = 5^{m}$ なる $n, m$ が存在したとき, $v_{5} (n) = m, n \geq 5^{m}$ となり, $F_{5^{m}} \leq F_{n} = 5^{m}$ となります. これは, $m \geq 2$ で不成立なので, $5$ べきのフィボナッチ数は $5$ だけです.
ところで, これにフィボナッチ数の判定法を用いると,
$5^{2 m + 1} = k^{2} \pm 4$
の解を求めたことになります. $5^{2 m} = k^{2} \pm 4$ の解は, 平方数-平方数の形にできるので, 結局 $5^{m} = k^{2} \pm 4$ の整数解を求められたことになります. 特に, $5^{3} = 11^{2} + 4$ という解はかなり非自明ですごいですよね. ということは, 逆に考えればこういった方程式は三項間漸化式に帰着させて解くことができそうな気がします. やってみましょう.

$3^{m} = n^{2} + 2$ を満たす正の整数 $n, m$ を全て求めよ.

これも $3^{3} = 5^{2} + 2$ という解があるのでやばそうです.

$m$ が偶数の場合は簡単. $m$ が奇数の場合は $3^{(m - 1) / 2}$ を $m$ で置きなおして, $3 m^{2} = n^{2} + 2$ になる.
ここで, $a_{n + 2} = c a_{n + 1} + a_{n}, a_{0} = 0, a_{1} = 1$ についても, フィボナッチ数列同様の乗法定理が成立する:
$a_{n + m} a_{n - m} = a_{n}^{2} - (- 1)^{n + m} a_{m}^{2}$
$m = 1$ として, 漸化式を代入すると
$c a_{n} a_{n - 1} + a_{n - 1}^{2} - a_{n}^{2} - (- 1)^{n} = 0$
$a_{n - 1}$ についての判別式を見ると, $(c^{2} + 4) a_{n}^{2} + 4 (- 1)^{n}$ が平方数になる. さて, これを利用したいのだが定数項の絶対値が $4$ になってしまい困った. ので, 元の式から強引に $4$ を作り出そう.
$\sqrt{2} n$ を $N$ とおけば, $6 m^{2} \pm 4 = N^{2}$ となった. よって, $c = \sqrt{2}$ とすればよさそう. 数列を書いていくと,
$0, 1, \sqrt{2}, 3, 4 \sqrt{2}, 11, 15 \sqrt{2}, 41, 56 \sqrt{2}, 153 \dots$
となる. ここで注目すべきは, 奇数項目である. 偶数項目が $\sqrt{2}$ の整数倍であることから, 判別式 $({\sqrt{2}}^{2} + 4) a_{n}^{2} - 4$ が平方数の $2$ 倍であり, $N$ が $\sqrt{2}$ の整数倍であることと整合性がとれた！

一見常にこのようにうまくいくように見えるが, 整合性がとれたのはただの数値設定上の偶然である.
具体的には,

定数項が $4$ の場合 $\dots (k + 4) m^{2} = k n^{2} \pm 4$
定数項が $2$ の場合 $\dots (k + 2) m^{2} = k n^{2} \pm 2$
定数項が $1$ の場合 $\dots (k + 1) m^{2} = k n^{2} \pm 1$

の場合がこの方法で処理できる(多分). そのほかの場合にはより一般のペル方程式の議論を要する.

つまり, $3 m^{2} = n^{2} + 2$ の整数解は数列 $a_{n}$ の奇数項目で与えられる. 逆も, 詳細は省略するが, この記事の最後っぽいことをすれば示せる.
さて, 上で考えた $a_{n}$ について, $v_{3} (a_{n}) = v_{3} (n)$ が言える.

$a_{3 n} = \frac{1}{a_{n}} (a_{2 n}^{2} - (- 1)^{n} a_{n}^{2}) = a_{n} ((a_{n + 1} + a_{n - 1})^{2} - (- 1)^{n})$
あとは $mod 9$ で頑張る(か, 冒頭のような方法を使う)

ここから, 先の例と同じように不等式評価をするとこの数列の奇数項目に現れる $3$ べきは $1, 3$ だけだと分かった. 以上より, もとの方程式の解もしぼれ, $(1, 1), (3, 5)$ のみだと分かる.

といった感じで, 一見難しそうな不定方程式を解くことができました. 常にというわけにはいかなさそうですが...

最後にZsigmodyの類似の紹介です.

Zsigmondyの定理の類似

INTEGERSのこの記事の手法を応用し, フィボナッチ数列でも類似の結果を得られたので証明をかいてみます. なお, 実際はより一般の数列に対して成立することが知られています( この記事で結果が紹介されています).

Zsigmondyの類似

任意の自然数 $n \neq 1, 2, 6, 12$ に対し, $F_{n}$ の素因数 $p$ であって, $p$ が $F_{1}, F_{2}, \dots F_{n - 1}$ を割り切らないものが存在する. このような素因数を原始的素因数と呼ぶ(上で紹介した記事における原始的約数とは若干異なるので注意).

この証明をしていきます.
証明の大まかな流れとしては, $F_{n}$ の約数のうち, 原始的素因数でないものの積を上から評価するといった感じです. 実際には円分多項式にあたる概念, 円分フィボナッチ数を定義し, それについての評価をしていきます.

周期関数( この記事で紹介)

正整数 $n$ に対し, $F_{m}$ が $n$ の倍数になる正整数 $m$ が存在するので, このうち最小のものを $l (n)$ とかく.

$F_{m}$ が $n$ の倍数のとき, $m$ は $l (n)$ の倍数である.

証明は演習とする.

任意の $k \geq v_{p} (F_{l (p)})$ , 奇素数 $p$ に対し, $l (p^{k}) = p^{k - v_{p} (F_{l (p)})} l (p)$ , 任意の $k \geq 3$ に対して $l (2^{k}) = 2^{k - 2} \cdot 3$ が成立する.

補題2より, $F_{m}$ が $p^{k}$ の倍数のとき $m$ は $l (p)$ の倍数なので, LTEの類似より $k \leq v_{p} (F_{m / l (p)}) = v_{p} (m) + v_{p} (F_{l (p)})$ が成立. これより, $\frac{m}{l (p)} \geq p^{k - v_{p} (F_{l (p)})}$ となるので示された(逆は同様にLTEを使おう). $p = 2$ の場合も同様.

メビウス関数

$μ$ をメビウス関数, すなわち正整数 $n$ に対し $n$ が平方因子を持つ場合 $μ (n) = 0$ , それ以外の場合 $n$ の素因数の個数 $t$ について $μ (n) = (- 1)^{t}$ とする.

メビウス関数には以下の重要な性質がある.

メビウスの反転公式

正の整数に定義される関数(厳密には終域は任意のアーベル群) $f, g$ が
$g (n) = \prod_{d | n} f (n), f (n) = \prod_{d | n} g (n)^{μ (n / d)}$
のそれぞれを満たすことは同値である.

円分フィボナッチ数

正の整数 $n$ に対し, 円分フィボナッチ数列 ${\tilde{F}}_{n}$ を以下で定める:
${\tilde{F}}_{n} = \prod_{d | n} F_{n}^{μ (n / d)}$

${\tilde{F}}_{1}, {\tilde{F}}_{2}, . . .$ は $1, 1, 2, 3, 5, 4, 13, 7, 17, 11, 89, 6, \dots$ となる.

円分フィボナッチ数の性質

$2$ 以上の整数 $n$ に対して,
${\tilde{F}}_{n} = \prod_{p | F_{n} : 素数} p^{max (0, v_{p} (F_{n}) - max_{1 \leq k \leq n - 1} v_{p} (F_{k}))} = \prod_{gcd (m, n) = 1, 1 \leq m \leq n} (\frac{1 + \sqrt{5}}{2} - ζ_{n}^{m} \frac{1 - \sqrt{5}}{2})$
が成立する( $n = 1$ は左の $=$ のみ成立). ここで, $ζ_{n} = e^{2 π i / n}$ は $1$ の原始 $n$ 乗根の一つである. 特に, ${\tilde{F}}_{n}$ は整数である.

(1つ目の $=$ )
素数 $q$ が $\prod_{p | F_{n} : 素数} p^{max (0, v_{p} (F_{n}) - max_{1 \leq k \leq n - 1} v_{p} (F_{k}))}$ を割り切るのは, $n = l (q), l (q^{2}), l (q^{3}), . . .$ の場合のみであることに注意する.
補題6より, $\prod_{d | n} \prod_{p | F_{d} : 素数} p^{max (0, v_{p} (F_{d}) - max_{1 \leq k \leq d - 1} v_{p} (F_{k}))}$
を示せばよいが, 補題 $4$ より, $l (q), l (q^{2}), \dots, l (q^{v_{p} (F_{n})})$ はいずれも $n$ を割り切るため,
$v_{q} (\prod_{d | n} \prod_{p | F_{d} : 素数} p^{max (0, v_{p} (F_{d}) - max_{1 \leq k \leq d - 1} v_{p} (F_{k}))}) = v_{q} (q^{v_{q} (F_{n})}) = v_{q} (F_{q})$
である. よって示された.

(2つ目の $=$ )
$α = (1 + \sqrt{5}) / 2, β = (1 - \sqrt{5}) / 2$ とおく. Binetの公式より,
${\tilde{F}}_{n} = \prod_{d | n} F_{n}^{μ (n / d)} = \prod_{d | n} \frac{1}{\sqrt{5}} (α^{n} - β^{n})^{μ (n / d)} = Φ (α, β) \frac{1}{{\sqrt{5}}^{\sum_{d | n} μ (n / d)}} = Φ (α, β) = \prod_{gcd (m, n) = 1, 1 \leq m \leq n} (α - ζ_{n}^{m} β)$
ここで, $Φ$ は斉次の円分多項式であり, 最後から三つ目の $=$ には一般の円分多項式の性質, 最後から二つ目の $=$ には $\sum_{d | n} μ (d) = 0$ を用いた.

円分フィボナッチ数自体を操作することが円分多項式に比べて難しいため, あらかじめ素因数で記述した. そして, さらに以下の補題によりより明示的に記述できる.

円分フィボナッチ数の性質

奇素数 $p$ , 正整数 $n$ に対して, 以下が成立する.
$max (0, v_{p} (F_{n}) - max_{1 \leq k \leq n - 1} v_{p} (F_{k})) = {\begin{cases} v_{p} (F_{l (p)}) (n = l (p)) \\ 1 (n = p l (p), p^{2} l (p), . . .) \\ 0 (Otherwise) \end{cases}$ ,

$max (0, v_{2} (F_{n}) - max_{1 \leq k \leq n - 1} v_{2} (F_{k})) = {\begin{cases} 1 (n = 3, 2^{2} \cdot 3, 2^{3} \cdot 3, 2^{4} \cdot 3, . . .) \\ 2 (n = 6) \\ 0 (Otherwise) \end{cases}$

左辺が正になるのは $n = l (p), l (p^{2}), \dots$ の場合のみなので, LTE, 補題5より直ちに従う.

さて, $\prod_{d | n} {\tilde{F}}_{n} = F_{n}$ より, ${\tilde{F}}_{n}$ は $F_{n}$ を割り切るので, ${\tilde{F}}_{n}$ に $F_{n}$ の原始的素因数があることを言えばよい. 参照元の記事の記号を用い, 以下のように定義する. 同様に $λ_{n}$ を評価していく.

${\tilde{F}}_{n} = λ_{n} P_{n}$ とおく. ここで, $P_{n}$ は $F_{n}$ の原始的素因数のみを素因数に持ち, $λ_{n}$ は持たない.

λ_{n}

の素因数の考察

$n = 6, 12$ の場合を除き, $λ_{n}$ は $1$ または素数である.

素数 $p$ に対して, $p$ は $F_{l (p)}$ の原始的素因数でないので, 補題7, 8より $p$ が $λ_{n}$ の素因数のとき, $n = p^{s} l (p)$ なる正整数 $s$ をとれる.
$λ_{n}$ が相異なる素因数 $p, q$ を持つとする.
このとき, ある正整数 $s, t$ が存在し,
$n = p^{s} l (p) = q^{t} l (q)$
が成立する. $p, q$ は相異なるので, $l (p), l (q)$ はそれぞれ $q^{t}, p^{s}$ の倍数である. 前回の記事の定理3より, $l (p) \leq p + 1, l (q) \leq q + 1$ なのでこれをあわせると,
$q \leq q^{t} \leq l (p) \leq p + 1, p \leq p^{s} \leq l (q) \leq q + 1$
となる. 従って, 偶奇を考えれば $p, q$ のいずれかは $2$ であり, このときもう一方は $l (2) = 3$ となる. このとき, $n = 12$ である.
それ以外の場合, $λ_{n} = p^{s}$ と記述できるが, 補題8より $n = 6$ の場合を除き $s = 1$ である.

これより, ${\tilde{F}}_{n}$ が十分大きいことを言えれば, $P_{n} > 1$ となりZsigmondyの類似が証明される.

{\tilde{F}}_{n}

の評価

$n = 1, 2, 6, 12$ の場合を除き, ${\tilde{F}}_{n} > λ_{n}$ である.

$α = (1 + \sqrt{5}) / 2, β = (1 - \sqrt{5}) / 2$ とおけば, 補題7より $| {\tilde{F}}_{n} | = \prod_{gcd (m, n) = 1, 1 \leq m \leq n} | α - ζ_{n}^{m} β |$ である. 三角不等式より右辺の各因数は $1$ 以上であり, $n \geq 3$ の場合 $1$ より大きいものが存在するので, $λ_{n} = 1$ の場合は示された.

$λ_{n} = p$ :素数とし, $n$ が $p^{2}$ の倍数とする. このとき, $n = p^{2} N$ とおけば, $1 \leq m \leq N p$ が $gcd (m, n) = 1$ を満たすとき, $gcd (N p - m, n) = 1$ である. これらをペアにして考え, $n - N p \leq m \leq n$ についても同様のペアを考えれば, 合計で $φ (p N) (\geq p - 1)$ 組のペアができる. また, 各ペアについて $| α - ζ_{n}^{m} β | \cdot | α - ζ_{n}^{(N p - m)} β |$ は, 「中心 $α$ 半径 $- β$ の円の原点における方べきの値( $= \sqrt{5}$ )」以上であるため(図を描いて位置関係の議論による), $| α - ζ_{n}^{m} β | \cdot | α - ζ_{n}^{(N p - m)} β | \geq \sqrt{5}$ が示された.
よって, $| {\tilde{F}}_{n} | = \prod_{gcd (m, n) = 1, 1 \leq m \leq n} | α - ζ_{n}^{m} β | \geq 5^{(p - 1) / 2}$ が言え, これは $p$ よりも大きい.

そうでない場合, $n = p N$ とおく. (以下の変形は参照元で利用されているものである.)
$\begin{aligned} | {\tilde{F}}_{n} | & = \prod_{gcd (m, p N) = 1, 1 \leq m \leq p N} | α - ζ_{p N}^{m} β | = \frac{\prod_{gcd (m, N) = 1, 1 \leq m \leq p N} | α - ζ_{p N}^{m} β |}{\prod_{gcd (m, N) = 1, p | m, 1 \leq m \leq p N} | α - ζ_{p N}^{m} β |} \\ = \frac{\prod_{gcd (m, N) = 1, 1 \leq m \leq N} | α^{p} - ζ_{N}^{m} β^{p} |}{\prod_{gcd (m, N) = 1, 1 \leq m \leq N} | α - ζ_{N}^{m} β |} \geq \frac{\prod_{gcd (m, N) = 1, 1 \leq m \leq N} | α^{p} - (- β)^{p} |}{\prod_{gcd (m, N) = 1, 1 \leq m \leq N} | α - β |} \\ \geq \frac{| α^{p} - (- β)^{p} |}{| α - β |} \geq \frac{α^{p} - 1}{\sqrt{5}} \end{aligned}$
この最右辺は $p \geq 7$ で $p$ より大きい. $p = 2, 3, 5$ のとき, $λ_{n} = p$ および $v_{p} (n) = 1$ より, それぞれ $n = 6, 12, (存在しない)$ となり, いずれも除外済みである.

以上より, $n \neq 1, 2, 6, 12$ のとき $P_{n} > 1$ となり, すなわち $F_{n}$ には原始的素因数が存在する.

これでZsigmodyの類似も示されました！
これを利用すると, 例えばJMO2011本選2のフィボナッチ数列版のさらに一般化を考察できたりします(あまりいい感じの応用が思いつかなかった...).

JMO2011本選2, 強化版

$F_{m} = F_{t_{1}} \times F_{t_{2}} \times \dots \times F_{t_{n}}$
を満たす $2$ 以上の整数 $n$ および $3$ 以上の整数 $m, t_{1}, t_{2}, \dots, t_{n}$ の組を全て求めよ.

とか. $F_{m}$ の原始的素因数を取れば $m = 6, 12$ と分かります.

さて, 今までフィボナッチ数列の性質を色々扱ってきましたが, 実はほとんどの命題においてフィボナッチ数列であることは本質的に使っていません. 一般の $a_{0} = 0, a_{1} = 1$ なる三項間漸化式によって定義される数列(特に $a_{n + 2} = c a_{n + 1} + a_{n}$ という形のもの)において多少形は違えどほとんど同じ結果が得られます. ただ, その中でもフィボナッチ数列というのは一番シンプルなだけあり, 得られる結果も綺麗になりやすいです. 今後はもっと二次体とかと絡めた議論をしてみて, より一般的な結果を得たいですね.