设 \(F\) 是斐波那契数列，其定义是对于 \(x\leq 2\)，\(F(x)=1\)；对于 \(x\geq 3\)，\(F(x)=F(x-1)+F(x-2)\)。
1. \(\gcd(F(x),F(y))=F(gcd(x,y))\) 。
一个非常实用的结论。下面考虑证明。
引理 1：\(F(x)=F(y)\times F(x-y+1)+F(y-1)\times F(x-y)\)。
把递推式逐级展开就可以得到这个式子。
即 \(F(x)=F(x-1)+F(x-2)\Rightarrow F(x)=2F(x-2)+F(x-3)\Rightarrow F(x)=3F(x-3)+2F(x-4)...\)
引理 2：\(\gcd(F(x),F(x-1))=1\)。
仍然是把递推式展开迭代。
即 \(\gcd(F(x),F(x-1))=\gcd(F(x-2)+F(x-1), F(x-1))=\gcd(F(x-2),F(x-1))...\)。最后就可以得到 \(\gcd(F(2),F(1))\)，这时结果显然是 \(1\)。
有了这两个引理就可以证明上述结论了。
先假设 \(x>y\)，那么 \(\gcd(F(x),F(y))=\gcd(F(y)\times F(x-y+1)+F(y-1)\times F(x-y),F(y))\)。把这个式子套用上述两个引理，就有 \(\gcd(F(x),F(y))=\gcd(F(x-y),F(y))\)。可以发现这就是一个辗转相减的形式，直接套用欧几里得就有 \(\gcd(F(x),F(y))=F(\gcd(x,y))\)。