斐波那契与公约数

设斐波那契数列第 \(i\) 项为 \(f_i\)。

\[f_i=\begin{cases}1 &(i\leq 2)\\f_{i-1}+f_{i-2} &(i>2)\end{cases} \]

Lemma 1

\[\gcd(f_i,f_{i+1})=1 \]

Proof 1

数学归纳法。当 \(i=1\) 时， \(\gcd(f_1,f_2)=\gcd(1,1)=1\)。

设 \(f_k=a,f_{k+1}=b\)，则有 \(f_{k+2}=a+b,f_{k+3}=a+2b\)。

利用更相减损术，可得：

\[\gcd(a+b,a+2b)= \gcd(b,a+b)=\gcd(a,b) \]

于是我们得到

\[\gcd(f_i,f_{i+1})=\gcd(f_{i-1},f_{i}) \]

利用数学归纳，可以得到对于 \(i>1\) 的 \(i\)，也满足 \(\gcd(f_i,f_{i-1})=1\)。命题得证。

Lemma 2

\[\gcd(f_n,f_m)=f_{\gcd(n,m)} \]

Proof 2

不妨假设 \(n<m\)。设 \(f_n=a,f_{n+1}=b\)，则 \(f_{m}=f_{m-n-1}a+f_{m-n}b=f_{m-n-1}f_n+f_{m-n}f_{n+1}\)。

首先我们有

\[\gcd(kx+y,x)=\gcd((kx+y)\bmod x,x)=\gcd(x,y) \]

那么有

\[\gcd(f_n,f_m)=\gcd(f_{m-n-1}f_n+f_{m-n}f_{n+1},f_n) = \gcd(f_{m-n}f_{n+1},f_n) = \gcd(f_m,f_{m-n}) \]

类似于辗转相除法，可以得到 \(\gcd(f_n,f_m)=\gcd(f_{\gcd(n,m)},f_1)=f_{\gcd(n,m)}\)。命题得证。

来源链接：https://www.cnblogs.com/XP3301Pipi/p/18653244