斐波那契与公约数
设斐波那契数列第 \(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)}\)。命题得证。
标签：gcd,得证,斐波,Lemma,公约数,那契 From： https://www.cnblogs.com/XP3301Pipi/p/18653244