Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

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.

some more.

- Doctor Paul, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Fibonacci Sequence/Golden Ratio
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search