I would have never expected a link between Fibonacci numbers and the Euclidean algorithm. Yet, Richard E. Borcherds presents us with such relationship in one of his lectures on YouTube, along with an introduction to the Cassini’s Identity.

Firstly, a quick introduction to Fibonacci numbers, of which here follow their two main definitions. The recurrence system is the most common one.

\(
\begin{align*}
F_0 &= 0 \\
F_1 &= 1 \\
F_n &= F_{n-1}+F_{n-2}
\end{align*}
\)

Less known, albeit very useful, is its Binet’s formula.

\(
\begin{equation*}
F_n = \frac{1}{\sqrt{5}} \left( \left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)
\end{equation*}
\)

Both definitions result in the following sequence.

\(
0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ …
\)

The Euclidean algorithm was, instead, devised to efficiently compute the greatest common divisor between two numbers, say \(a\) and \(b\). For \(q_i\) and \(r_i\) representing the quotient and the remainder at the \(i\)-th step, here follows its definition.

\(
\begin{align*}
a &= q_0b+r_0 \\
b &= q_1r_0+r_1 \\
r_0 &= q_2 r_1 + r_2 \\
r_1 &= q_3 r_2 + r_3 \\
&\vdots
\end{align*}
\)

Here, the last non-zero remainder represents the greatest common divisor of \(a\) and \(b\). An example of its usage is shown in the following video.

In his lecture, Borcherds explains how any 2 consecutive elements in the Fibonacci sequence, \(F_n\) and \(F_{n+1}\), represent the worst case scenario for the Euclidean algorithm. This, because for each consecutive division the quotient \(q_i\) is always \(1\), and the remainders at each step of the algorithm are Fibonacci numbers themselves. In short:
\(
r_n = r_{n-1} + r_{n-2}
\)

To show this more clearly, I compute in the following picture the greatest common divisor between the two Fibonacci numbers \(55\) and \(34\). As you can notice, the last remainder \(r_n\) not equal to zero is highlighted, because it represents the greatest common divisor.

Another curious property of the Fibonacci sequence is the Cassini’s identity, according to which the product of the two Fibonacci numbers \(F_{n+1}F_{n-1}\) is equal to \(F_n^2+(-1)^{n+1}\). Equivalently:

\(
F_{n+1}F_{n-1}-F_n^2 = (-1)^{n+1}
\)

The proof by induction of this identity that I found very intuitive, is the one denoted as Proof 1′ in this website. I will expand some of its steps to make them more clear.

Assuming the identity holds for \(n=k>0\), we want to show that the identity also holds for \(n=k+1\). In the first step, we simply substitute \(n\) with \(k\) in the previous formula:

\(
F_{k+1}F_{k-1}-F_k^2 = (-1)^{k+1}
\)

Now, knowing that \(F_{k-1}+F_k=F_{k+1}\), it’s trivially obtained that \(F_{k-1}=F_{k+1}-F_k\). I can, thus, substitute it in the equation:

\(
\begin{align*}
F_{k+1}(F_{k+1}-F_k)-F_k^2 &= (-1)^{k+1} \\
F_{k+1}^2-F_{k+1}F_k-F_k^2 &= (-1)^{k+1}
\end{align*}
\)

By factorising \(-F_k\) in the left hand side, the equation becomes:

\(
\begin{align*}
F_{k+1}^2-F_k(F_{k+1}+F_k) &= (-1)^{k+1}
\end{align*}
\)

Here, \(F_{k+1}+F_k=F_{k+2}\) and therefore:

\(
\begin{align*}
F_{k+1}^2-F_kF_{k+2} &= (-1)^{k+1}
\end{align*}
\)

This is exactly the identity for \(n=k+1\).

I created a visualisation on desmos to show the exceptional growth of the numbers generated by the Cassini’s identity – denoted by black dots, when compared to the Fibonacci numbers.