フィボナッチ数列の最大公約数について

Codeforces#140「Anniversary」で出てきた

(Fib(x), Fib(y)) = Fib((x, y))

を簡単に導出してみようと思います。

隣り合うフィボナッチ数は互いに素

隣り合うフィボナッチ数が互いに素ではなかったと仮定します。そのとき、

(Fib(x), Fib(x+1)) = d, d>0
となるようなdが存在します。このとき、フィボナッチ数の定義より、

Fib(x-1) = Fib(x+1) - Fib(x)
なので、d | Fib(x-1) となります。これを繰り返すと、d| Fib(1)となりますがこれはFib(1) = 1と矛盾します。 よって背理法より、隣り合うフィボナッチ数は互いに素となります。

フィボナッチ数の加法定理

x>2,   y>1について、

Fib(x+y) = Fib(x)Fib(y+1) + Fib(x-1)Fib(y)

という性質が成り立ちます。数学的帰納法を使うと証明できるそうですが、ここでは簡単に上の定理が正しいことを説明します。

Fib(x)は階段を１段ずつ、または１段飛ばしで登っていき、x段目に辿り着いたときの上り方のパターン数と考えることができます。Fib(x+y)はx+y段目まで登るとき（最下段からx+y-1段登ったとき）のパターン数です。
最下段からx+y-1段登るときのパターン数を、x段目を通るか通らないかに場合分けすると、

(x+y-1段登るときのパターン数)
= (x段目を通るパターン数) + (x段目を通らないパターン数)
= (x-1段登ったあと、y段登るパターン) + (x-2段登った後、1段飛ばしをして、y-1段登るパターン)
= (x-1段登るパターン数 * y段登るパターン数) + (x-2段登るパターン数 * y-1段登るパターン数)

ということで、まさにこれが加法定理と同じです。

(Fib(x), Fib(y)) = Fib((x,y))

さて、いよいよ目的の定理を考えます。まずは、Fib(x)とFib(x+y)の最大公約数を考えてみます。

(Fib(x), Fib(x+y))
= (Fib(x), Fib(x)Fib(y+1) + Fib(x-1)Fib(y))     (∵加法定理より)
= (Fib(x), Fib(x-1)Fib(y))     (∵ Fib(x) | Fib(x)Fib(y+1)より)
= (Fib(x), Fib(y))     (∵ (Fib(x), Fib(x-1)) = 1より)

はい、来ました。 (Fib(x), Fib(x+y)) = (Fib(x), Fib(y))
です。これを再帰的に繰り替えしていくとユークリッドの互除法（の引き算バージョン）によって、

(Fib(x), Fib(x+y)) = Fib((x, x+y))

となります。よって、目的の定理が成り立ちます。