已知 F(n) = F(n-1) + F(n-2) ，以下證明 GCD ( F(n) , F(n-1) )  = GCD ( F(n) , F(n-2) ) = 1

令 GCD ( F(n) , F(n-1) ) = k ，k 是自然數

則可知 k 整除 F(n) 而且  k 整除 F(n-1)  =>  k 整除 ( F(n) - F(n-1) )  =>   k 整除 F(n-2)

( 例  2 | 80 ( 2、80 中間一豎，代表 2 整除 80 )  且  2 | 30 ，則 2 | 80-30  即 2 | 50 )

又由上已知 k | F(n-1) 且 k | F(n-2) ，同上推理可得 k | F(n-3)

依此類推，最後可得 k | F(2)，因為費式數列，定義 F(1) = F(2) = 1

所以得到 k | 1，又已知 k 是自然數，能整除 1 的自然數就只有 1 本身

故 k = 1，亦即最開始假設 GCD ( F(n) , F(n-1) ) = k = 1

兩最大公因數為 1 ，代表兩者互質，得證~~~

至於  GCD ( F(n) , F(n-2) ) 類似上述過程，只要求得 k | F(n-1) ，剩下皆相同

證畢#

PS 上一篇的過程 ，F(30) = F(11) * F(20) + F(10) * F(19)

因為 F(30) 可以拆成兩項的和，其中一項是 F(20) 的倍數，可以忽略

而且上述證明可知，F(20)、F(19) 互質，也可以忽略

因此只要處理剩下的 F(10) 即可