查看原题'" class='mdui-btn mdui-btn-raised mdui-ripple'>点击加载点击跳转结论: $\gcd(f_n,fm)=f{\gcd(n,m)}$,然后矩阵快速幂加速即可证明:设$m>n$引理:$\gcd(fn,f{n+1})=1$根据辗转相减法, $\gcd(fn,f{n+1})=\gcd(fn,f{n+1}-f_n)=\gcd(fn,f{n-1})$所以 $\gcd(fn,f{n+1})=\gcd(fn,f{n-1})=\dots=\gcd(f_2,f_1)=1$$f_{n+m}=fnf{m-1}+f_{n+1}f_m$数学归纳法:$n=m=1$时……