众所周知
众所周知，斐波那契数列有一个性质：
\[\gcd(f_{n},f_{m})=f_{\gcd(n,m)} \]在证明他之前，先来看个引理：
\(\text{Lemma}\ 1\)
\[f_{n+m}=f_{n}\times f_{m-1}+f_{n+1}\times f_{m} \]
这是归纳证的，\(m\le 2\) 时，显然有：
\[f_{n+1}=f_{n}\times f_{0}+f_{n+1}\times f_{1} \]\[f_{n+2}=f_{n}\times f_{1}+f_{n+1}\times f_{2} \]假设对于 \(m\le k\) 均成立，证明 \(m=k+1\) 成立。
\[f_{n+k}=f_{n}\times f_{k-1}+f_{n+1}\times f_{k} \]\[f_{n+k-1}=f_{n}\times f_{k-2}+f_{n+1}\times f_{k-1} \]两个式子相加即得：
\[f_{n+k+1}=f_{n}\times f_{k}+f_{n+1}\times f_{k+1} \]即 \(m=k+1\) 成立。
如果把 \(n+m\) 替换成 \(m\)，这个引理也可以写作：
\[f_{m}=f_{n}\times f_{m-n-1}+f_{n+1}\times f_{m-n} \]接着是一个比较显然的引理：
\(\text{Lemma}\ 2\)
\[\gcd(f_{n},f_{n+1})=1 \]
简单推导一下：
\[\begin{aligned}\ \gcd(f_{n},f_{n+1})&=\gcd(f_{n},f_{n+1}-f_{n})\\ &=\gcd(f_{n},f_{n-1})\\ &\cdots\\ &=\gcd(f_{1},f_{2})\\ &=1 \end{aligned}\]回到最初的证明，类比更相减损推广到辗转相除，如果我们能够证明：
\[\gcd(f_{n},f_{m})=\gcd(f_{n},f_{m-n}) \]就可以证明经过辗转相除后：
\[\gcd(f_{n},f_{m})=\gcd(f_{\gcd(n,m)},f_{0})=f_{\gcd(n,m)} \]把式子大力展开！
\[\begin{aligned} \gcd(f_{n},f_{m})&=\gcd(f_{n},f_{n}\times f_{m-n-1}+f_{n+1}+f_{m-n})\\ &=\gcd(f_{n},f_{n+1}\times f_{m-n})\\ &=\gcd(f_{n},f_{m-n}) \end{aligned}\]证毕。
我所应该知
然后一道题——BZOJ-4833 最小公倍佩尔数。
题解1：推导得到 \(f\) 满足 \(f_{n}=2f_{n-1}+f_{n-2}\)，类比斐波那契数列，这种形如 \(f_{n}=xf_{n-1}+yf_{n_2}\) 的递推式都满足 \(\gcd(f_{n},f_{m})=f_{\gcd(n,m)}\)。
题解2：我们知道……大力归纳……
我：？你说了个鬼？
那么我们来看一下所有满足：
\[\begin{cases} f_{i}=[i=1]&i\le 1\\ f_{i}=xf_{i-1}+yf_{i-2}&i>1 \end{cases}\]的数列 \(f\)，有什么特殊之处吧。
引理 \(1\) 的归纳过程，边界值中 \(m=1\) 时 \(f_1=1\)，\(m=2\) 时 \(f_1=y\)，而 \(f_2=x\) 是无疑的，于是姑且讨论 \(y=1\) 的情况。
重写一下递推式：
\[f_{n}=xf_{n-1}+f_{n-2} \]现在归纳证明引理 \(1\) 对于 \(x\in \mathrm{N}_{+},y=1\) 同样成立。
\(m\le 2\) 时，显然有：
\[f_{n+1}=f_{n}\times f_{0}+f_{n+1}\times f_{1} \]\[f_{n+2}=f_{n}\times f_{1}+f_{n+1}\times f_{2} \]假设对于 \(m\le k\) 均成立，证明 \(m=k+1\) 成立。
\[f_{n+k}=f_{n}\times f_{k-1}+f_{n+1}\times f_{k} \]\[f_{n+k-1}=f_{n}\times f_{k-2}+f_{n+1}\times f_{k-1} \]向上面一样凑出 \(f_{n+k+1}\)：
\[\begin{aligned} f_{n+k+1}&=xf_{n+k}+f_{n+k-1}\\ &=f_{n}\times (xf_{k-1}+f_{k-2})+f_{n+1}\times (xf_{k}+f_{k-1})\\ &=f_{n}\times f_{k}+f_{n+1}\times f_{k+1} \end{aligned}\]证毕。
而对于引理 \(2\)，也是稍作改动即可：
\[\begin{aligned}\ \gcd(f_{n},f_{n+1})&=\gcd(f_{n},f_{n+1}-xf_{n})\\ &=\gcd(f_{n},f_{n-1})\\ &\cdots\\ &=\gcd(f_{1},f_{2})\\ &=1 \end{aligned}\]既然两个引理都同样满足，不难得到相同的结论。
我所后知
\(\text{SoyTony}\)：那 \(y\neq 1\) 时是不是不成立？感觉差一个系数。
\(\text{Jijidawang}\)：那就随便加一个吧。（在引理 \(1\) 的第一项加了个系数 \(y\)。）
他说他是瞎加的，他可不是瞎加的啊！我看是有备而来！
很强的引理：
\(\text{Lemma}\ 3\)
\[f_{n+m}=y\times f_{n}\times f_{m-1}+f_{n+1}\times f_{m} \]
证明略，方法同上，增加了一个系数即可保证 \(m=2\) 的边界同样成立。
这个时候按理说就要证明引理 \(2\) 的相邻互质了，然而同样的方法由于系数变复杂变得很难看。思考另一个问题：什么情况下保证相邻互质？
\(\text{Lemma}\ 4\)
\[\gcd(x,y)=1\Leftrightarrow \gcd(f_{n},f_{n+1})=1 \]
还是归纳一下，\(n=1\) 时显然成立。
假设对于 \(n\le k\) 均成立，证明 \(n=k+1\) 成立。
把 \(f_{n+1}\) 拆开！
\[\begin{aligned} \gcd(f_{n},f_{n+1})&=\gcd(f_{n},xf_{n}+yf_{n-1})\\ &=\gcd(f_{n},yf_{n-1})\\ &=\gcd(f_{n},y) \end{aligned}\]值得注意的一点是，\(f_2=x\)。也就是说 \(\gcd(x,y)=1\) 是满足 \(\gcd(f_{n},f_{n+1})=\gcd(f_{n},y)=1\) 的必要条件，但这并不能满足我们的需求。
而对于任意 \(f_{n}\) 都是由 \(x,y\) 表示出的，辗转相除消去含有 \(y\) 的项后剩下的便是只含有 \(x\) 的一项，于是 \(\gcd(f_{n},y)=1\) 与 \(\gcd(x,y)=1\) 可以互推。
完成辣！
标签：引理,gcd,xf,times,斐波,le,那契,aligned,1.27 From： https://www.cnblogs.com/SoyTony/p/Flowers_on_Jan_27th.html