## Posts

Showing posts from March, 2015

### Investigating Bezout's Identity for Fibonacci Numbers

The Fibonacci numbers: $1,1,2,3,5,8,13,21,...$ have a number of interesting properties. A few days ago, I discovered and proved one such property that I find particularly interesting. It turns out that successive Fibonacci numbers are always relatively prime (I will prove this later). Further, Bezout's lemma guarantees the existence of integers $p$ and $q$ such that $p F_n + q F_{n+1} = 1$, where $F_n$ denotes the $n^{th}$ number in the Fibonacci sequence. In this blog post, I will find a general formula for $p$ and $q$. There is a simple result and an elegant proof of that result which I will demonstrate. Before we find a general formula for $p$ and $q$, let me first prove that $F_n$ and $F_{n+1}$ are always relatively prime: Assume for contradiction that $F_n$ and $F_{n+1}$ have a factor, $d > 1$ that they share. Then $F_n = d k_1$ and $F_{n+1} = d k_2$ for some integers $k_1$ and $k_2$.