证明：

两个相邻的斐波那契数【Fibonacci number】互素【即它们的最大公约数是1】。

f0=0, f1=1, f2=1, f3=2,      （0)

fn = fn-1+fn-2

假设fn-1, fn-2互素          （1）

又假定fn, fn-1不互素        (2)

(1)是归纳假定，(2)是反证假定。

由(2),存在q>1，q整除fn, q整除fn-1

因fn - fn-1=fn-2

这又推出q整除fn-2，与(1)矛盾。这说明，

在(1)成立的条件下，fn, fn-1互素。

考虑归纳基础(0)相邻互素。

所以，两个相邻的斐波那契数互素。