證明：

兩個相鄰的斐波那契數【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)相鄰互素。

所以，兩個相鄰的斐波那契數互素。