Ryan's Repository of Random Reflections

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 \).