Fibonacci Numbers and the Euclidean Algorithm

///Fibonacci Numbers and the Euclidean Algorithm

Fibonacci Numbers and the Euclidean Algorithm

As several of you noted in class Thursday, the Fibonacci numbers made a surprise appearance during an otherwise routine calculation of the greatest common divisor of two integers. Their appearance was not a coincidence. Let’s take a look.

The Fibonacci Numbers

If you’re interested in reading about Fibonacci and the Fibonacci numbers in detail, I encourage you to start with Chapter 14 in our text, which is devoted entirely to the subject. To quote the introduction:

Perhaps the greatest mathematician of the Middle Ages was Leonardo of Pisa (1180-1250), who wrote under the name of Fibonacci–a contraction of “filius Bonacci,” that is, Bonacci’s son. Fibonacci was born in Pisa and educated in North Africa, where his father was in charge of a customhouse. In the expectation of entering the mercantile business, the youth traveled about the Mediterranean visiting Spain, Egypt, Syria, and Greece. The famous Liber Abaci, composed upon his return to Italy, introduced the Latin West to Islamic arithmetic and algebraic mathematical practices. A briefer work of Fibonacci’s, the Liber Quadratorum (1225)…is regarded as the most important contribution to Latin Middle-Ages number theory before the works of Bachet and Fermat.

And what of the so-called Fibonacci sequence? In the Liber Abaci Fibonacci posted a problem dealing with rapidly multiplying rabbits. To quote Burton quoting Fibonacci:

A man put one pair of rabbits in a certain place entirely surrounded by a wall. How many pairs of rabbits can be produced from that pair in a year, if the nature of these rabbits is such that every month each pair bears a new pair from which the second month on becomes productive?

I’ll leave it to you to read more about the rabbit problem (see page 285), and I’ll also put aside any questions about inbreeding, rabbit death, etc., and instead just cut to the chase. Under all of the implied assumptions in the problem, the number of pairs of rabbits each month turns out to be given by the sequence

\[
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,\ldots
\]

This is called the Fibonacci sequence, and the terms in this sequence are called the Fibonacci numbers. In modern mathematical terms, this sequence is defined recursively by $f_1=1, f_2=1$, and $f_n=f_{n-1}+f_{n-2}$ for $n\geq 3$. Despite their simple definition, these numbers have been studied extensively and possess a frankly ridiculous number of interesting properties. Below is a tiny sampling of some of them.

  • The sum of the first $n$ Fibonacci numbers is one less than a Fibonacci number: $f_1+f_2+\cdots +f_n = f_{n+2}-1$.
  • Something similar can be said of the sum of every other Fibonacci number: $f_1+f_3+\cdots +f_{2n-1} = f_{2n}$ and $f_2+f_4+\cdots +f_{2n} = f_{2n+1}-1$.
  • The sum of the squares of the Fibonacci numbers is the product of two Fibonacci numbers: $f_1^2+f_2^2+\cdots +f_n^2=f_nf_{n+1}$.
  • They have interesting divisibility properties. For example, $\gcd(f_m,f_n)=f_{\gcd(m,n)}$.
  • Any three successive Fibonacci numbers are pairwise relatively prime: $\gcd(f_n,f_{n+1})=\gcd(f_{n+1},f_{n+2})=\gcd(f_n,f_{n+1})=1$.
  • With the exceptions of $f_1 = f_2, f_6$, and $f_{12}$, every Fibonacci number has a prime factor that is not a factor of any smaller Fibonacci number.
  • Every positive integer can be written as a sum of Fibonacci numbers, where any one number is used once at most.
  • Fibonacci numbers occur in many places in nature, e.g., see Wikipedia.
  • There is an explicit formula for the Fibonacci numbers, and it involves irrational numbers: $f_n = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)$

There are many, many others. For now, however, let’s see how they relate to the Euclidean algorithm.

Connection to the Euclidean Algorithm

If you look back at your notes for Thursday’s class, you’ll see that the example in which the Fibonacci numbers made their surprise appearance was none other the computation of the greatest common divisor of two successive Fibonacci numbers, namely $f_9=34$ and $f_{10}=55$. To quickly recap, our calculation was as follows:

\begin{align*}
55 &= 34\cdot 1+21\\
34 &= 21\cdot 1+13\\
21 &= 13\cdot 1+8\\
13 &= 8\cdot 1+5\\
8 &= 5\cdot 1+3\\
5 &= 3\cdot 1+2\\
3 &= 2\cdot 1+1\\
2 & = 1\cdot 2.
\end{align*}

The remainders are exactly the Fibonacci numbers! Looking at the other examples we worked through in class (and the others you’ll do in the exercises), you might also notice that this $\gcd$ calculation took a lot more steps than “most” $\gcd$ calculations. In fact, Émile Léger and Gabriel Lamé proved that the consecutive Fibonacci numbers represent a “worst case scenario” for the Euclidean algorithm. Here is a precise statement:

Lamé's Theorem

The smallest positive integers $a>b$ for which the Euclidean algorithm requires $n$ steps are $f_{n+2}$ and $f_{n+1}$.

We can prove this by induction. Throughout we assume $a>b$ are positive integers. The base case is when $n=1$, i.e., the Euclidean algorithm ends at the first step. This means $b$ divides $a$ without remainder. The smallest integers for which this is true are $a=2=f_3$ and $b=1=f_2$. So the result holds for $n=1$.

Now assume the result holds for for some $ngeq 1$. Suppose $a>b$ are positive integers for which the Euclidean algorithm requires $n+1$ steps to compute $\gcd(a,b)$. We must prove $a\geq f_{n+3}$ and $b\geq f_{n+2}$. The first step in the Euclidean algorithm gives $a=bq_1+r_1$ and the second step $b=r_1q_2+r_2$. Since it takes $n+1$ steps to compute $\gcd(a,b)$ and the algorithm is recursive, it takes $n$ steps to compute $\gcd(b,r_1)$. (In other words, steps 2 through $n+1$ compute $\gcd(b,r_1)$.) By the induction hypothesis, the smallest integers for which the Euclidean algorithm takes $n$ steps are $f_{n+2}$ and $f_{n+1}$, i.e., $b\geq f_{n+2}$ and $r_1\geq f_{n+1}$. It only remains to prove $a\geq f_{n+3}$. To see this, recall that $a=bq_1+r_1$ and $q\geq 1$ (as $a>b>0$). It follows that $a\geq b+r_1\geq f_{n+2}+f_{n+1}=f_{n+3}$. We’ve therefore proven the claim for $n+1$, and hence the statement holds for all $n$ by induction.

This is only the tip of the iceberg, as far as the Fibonacci numbers are concerned. I encourage everyone to take a peak at Chapter 14 in our textbook and to poke around the web, where you can find many fascinating articles and books devoted to the topic. People have also studied recursive sequences more generally, of which the Fibonacci sequence is only a single famous example. There are myriad other sequences with their own interesting history and properties, and an entire theory built up around such sequences. As is usually the case in mathematics, the story never really ends.

By |2017-01-01T15:39:00+00:00September 30th, 2016|Categories: Courses, Math 341|Tags: , |0 Comments

Leave A Comment

This Is A Custom Widget

This Sliding Bar can be switched on or off in theme options, and can take any widget you throw at it or even fill it with your custom HTML Code. Its perfect for grabbing the attention of your viewers. Choose between 1, 2, 3 or 4 columns, set the background color, widget divider color, activate transparency, a top border or fully disable it on desktop and mobile.

This Is A Custom Widget

This Sliding Bar can be switched on or off in theme options, and can take any widget you throw at it or even fill it with your custom HTML Code. Its perfect for grabbing the attention of your viewers. Choose between 1, 2, 3 or 4 columns, set the background color, widget divider color, activate transparency, a top border or fully disable it on desktop and mobile.