### 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$. Further, by definition of the recurrence relation, we know $F_{n+1} = F_n + F_{n-1}$ or equivalently $F_{n-1} = F_{n+1} - F_n$. Thus, $F_{n-1} = d k_2 - d k_1 = d (k_2 - k_1)$. This implies $F_{n-1}$ and $F_n$ have $d$ as a common factor, which indicates that d is divisor of all numbers in the sequence, which is a contradiction since $F_0 = 1$ has no divisors greater than $1$.

I've shown that successive terms in the Fibonacci sequence are relatively prime. Now I will find the Bezout identity relating the successive terms; that is, I will find $p$ and $q$ such that $p F_n + q F_{n+1} = 1$. Let's consider a few examples:
\begin{align*} F_5 p + F_6 q &= 1 & F_8 p + F_9 q &= 1 \\ 8 p + 13 q &= 1 & 34 p + 55 q &= 1 \\ 8 (5) + 13 (-3) &= 1 & 34(-21) + 55 (13) &= 1 \\ F_5 F_4 - F_6 F_3 &= 1 & -F_8 F_7 + F_9 F_6 &= 1 \end{align*} Notice anything interesting? In these examples, $p$ and $q$ are just Fibonacci numbers. More specifically, they are the previous two Fibonacci numbers (the next two Fibonacci numbers work as well - the Bezout identity is not unique). Also, it looks like the order of the terms switches depending on the parity of $n$. I conjecture (and will prove) that
$$\begin{cases} &F_{n+3} F_n - F_{n+2} F_{n+1} = 1 \hfill & \text{ if n is even} \\ -&F_{n+3} F_n + F_{n+2} F_{n+1} = 1 \hfill & \text{ if n is odd} \\ \end{cases}$$
In order to prove this, I will use the Fibonacci recurrence to re-write
$$F_{n+3} F_n - F_{n+2} F_{n+1}$$ in terms of only $F_{n+1}, F_{n+2}, F_{n+3},$ and $F_{n+4}$. Since $F_{n+2} = F_{n+1} + F_n$, we know $F_n = F_{n+2} - F_{n+1}$. Substituting into the above equation (in multiple places), we get
$$F_{n+3} (F_{n+2} - F_{n+1}) - (F_{n+4} - F_{n+3}) F_{n+1} \\ F_{n+3} F_{n+2} - F_{n+3} F_{n+1} - F_{n+4} F_{n+1} + F_{n+3} F_{n+1} \\ F_{n+3} F_{n+2} - F_{n+4} F_{n+1}$$  I have shown that
$$F_{n+3} F_n - F_{n+2} F_{n+1} = F_{n+3} F_{n+2} - F_{n+4} F_{n+1}$$ This is a fascinating result, and since my conjecture holds for $n = 0$:
$$F_3 F_0 - F_2 F_1 = 3 (1) - 2 (1) = 1$$ it also holds for all $n$!
\begin{align*} F_3 F_0 - F_2 F_1 &= 1 \\ -F_4 F_1 + F_3 F_2 &= 1 \\ F_5 F_2 + F_4 F_3 &= 1 \\ -F_6 F_3 - F_5 F_4 &= 1 \\ & \vdots \end{align*}