Consecutive Fibonacci Numbers Relatively Prime

Date: 11/17/2001 at 13:32:56
From: Beverly Miner
Subject: Discrete math

I'm trying to show that two consecutive Fibonacci numbers are 
relatively prime. I'm trying proof by induction. I've been working 
with mods but am making little progress.

Date: 11/20/2001 at 13:33:19
From: Doctor Paul
Subject: Re: Discrete math

F_n denotes the nth Fibonacci number.


Proof (1):

Using the Euclidean algorithm for finding the gcd(F_(n+2), F_(n+1)), 
we have:

F_(n+2)=1*F_(n+1) + F_n
F_(n+1)=1*F_n + F_(n-1)
.
.
.
F_4=1*F_3 + F_2
F_3=2*F_2 + 0

Substituting numbers in the last two lines gives:

3 = 1*2 + 1
2 = 2*1 + 0


This means that gcd(F_(n+2),F_(n+1)) = F_2 = 1, and thus any two 
consecutive Fibonacci numbers are relatively prime.


Proof (2) - by contradiction

Let F_n and F_(n+1) be any two consecutive Fibonacci numbers and 
suppose there is an integer d > 1 such that d divides F_n and d 
divides F_(n+1). 

Then F_(n+1) - F_n = F_(n-1) will also be divisible by d (if d divides 
a and d divides b, then a = d*m and b = d*n for some integers m and n.  
Then a - b = d*m - d*n = d * (m-n), so d divides (a - b) as well). But 
now notice that F_n - F_(n-1) = F_(n-2) will also be divisible by d. 

We can continue this way showing that F_(n-3), F_(n-4), ... , and 
finally F_1 = 1 are all divisible by d. Certainly F_1 is not divisible 
by d > 1. Thus we have a contradiction that invalidates the 
assumption. Thus it must be the case that F_n and F_(n+1) are 
relatively prime. 

I hope this helps. Please write back if you'd like to talk about this 
some more.

- Doctor Paul, The Math Forum
  http://mathforum.org/dr.math/