Skip to main content

Section 10.1 Divisibility properties

For \(n = 1\) and \(n = 2\) we have that \(\gcd(1, 1) = 1\) and \(\gcd(1, 2) =1.\) For \(n\geq 3\) we use the Euclidean algorithm and the definition of the Fibonacci numbers to give

\begin{align*} f_{n+1} \amp = 1 \cdot f_n + f_{n-1}\\ f_{n} \amp = 1 \cdot f_{n-1} + f_{n-2}\\ \amp \vdots \\ f_{4} \amp = 1 \cdot f_{3} + f_{2}\\ f_{3} \amp = 2 \cdot f_{2} \end{align*}

Thus \(\gcd(f_{n+1}, f_n) = f_2 = 1.\)

Note that as an example we can show that \(\gcd(21, 13) = 1.\) We have

\begin{align*} 21 \amp = 1 \cdot 13 + 8\\ 13 \amp = 1 \cdot 8 + 5\\ 8 \amp = 1 \cdot 5 + 3\\ 5 \amp = 1 \cdot 3 + 2\\ 3 \amp = 1 \cdot 2 + 1\\ 2 \amp = 2 \cdot 1 \end{align*}

We will return to this example when we come to the next chapter on continued fractions.

The above theorem generalizes in the following way.

To prove this theorem we will need first a few of lemmas.

We proceed by induction. When \(n = 1\) we have

\begin{equation*} f_{m+1} = f_{m-1}+f_m =f_{m-1}f_{1}+f_{m}f_{2}, \end{equation*}

so the result holds. Suppose that the result holds for all \(n\leq k.\) By the induction hypothesis, we have both

\begin{equation*} f_{m+k} = f_{m-1}f_k +f_{m}f_{k+1} \end{equation*}

and

\begin{equation*} f_{m+(k-1)} = f_{m-1}f_{k-1} +f_{m}f_{k}. \end{equation*}

Adding these two equations gives

\begin{equation*} f_{m+k}+f_{m+(k+1)} = f_{m-1}(f_k+f_{k-1}) +f_{m}(f_{k+1}+f_k). \end{equation*}

Using the recurrence relation, we have

\begin{equation*} f_{m+k+1} = f_{m-1}f_{k+1} +f_{m}f_{k+2}, \end{equation*}

which is exactly what we wanted to show. Thus by induction the result holds for all \(n,\) and since \(m\) was arbitrary, for all \(m\geq 2\) and \(n\geq 1.\)

Again, we prove this by induction. For \(n = 1\) this holds trivially. So suppose that the result holds for \(n\leq k,\) and note then that \(f_m\vert f_{mk}.\) Using the previous lemma, we have that

\begin{equation*} f_{m(k+1)} = f_{mk-1}f_m + f_{mk}f_{m+1}. \end{equation*}

Since \(f_m\vert f_m\) and \(f_m\vert f_{mk},\) we have that \(f_m\) divides the linear combination \(f_{mk-1}f_m + f_{mk}f_{m+1}\) which is exactly \(f_m\vert f_{m(k+1)}.\) This proves the lemma.

Write \(m = qn + r.\) Then we have by one of the above lemmas that

\begin{equation*} \gcd(f_m, f_n) = \gcd(f_{qn+r}, f_n) = \gcd(f_{qn-1}f_r + f_{qn}f_{r+1}, f_n). \end{equation*}

We recall a fact from the divisibility chapter. Note that if we write \(a = qb+r\) and \(b\vert c\) then we have that \(a + c = q'b + r\) and so

\begin{equation*} \gcd(a, b) = \gcd(b, r) = \gcd(a + c, b). \end{equation*}

Using this and the fact that \(f_n\vert f_{qn},\) we have

\begin{equation*} \gcd(f_m, f_n) = \gcd(f_{qn-1}f_r + f_{qn}f_{r+1}, f_n) = \gcd(f_{qn-1}f_r, f_n). \end{equation*}

If we can show that \(\gcd(f_{qn-1}, f_n) = 1\) then we would be done.

To this end, set \(d = \gcd(f_{qn-1}, f_n).\) Then since \(d\vert f_n\) and \(f_n\vert f_{qn},\) we have that \(d\vert f_{qn}.\) But we have also that \(d\vert f_{qn-1}\) so that \(\gcd(f_{qn}, f_{qn-1})\geq d.\) Since consecutive Fibonacci numbers are coprime we have that \(d = 1,\) and the desired result follows.

Without loss of generality assume that \(m\geq n.\) We apply the Euclidean algorithm to give the system

\begin{align*} m \amp = q_1n + r_1 \hspace{15mm} 0 \lt r_1 \lt n\\ n \amp = q_2r_1 + r_2 \hspace{14mm} 0 \lt r_2 \lt r_1\\ r_1 \amp = q_3r_2 + r_3 \hspace{14mm} 0 \lt r_3 \lt r_2\\ \amp \vdots \\ r_{n-2} \amp = q_nr_{n-1} + r_n \hspace{8.5mm} 0 \lt r_n \lt r_{n-1}\\ r_{n-1} \amp = q_{n+1}r_n + 0. \end{align*}

By the previous lemma we have

\begin{equation*} \gcd(f_m, f_n) = \gcd(f_n, f_{r_1}) = \gcd(f_{r_1}, f_{r_2}) = \cdots = \gcd(f_{r_{n-1}}, f_{r_n}). \end{equation*}

Because \(r_n\vert r_{n-1},\) we have that \(f_{r_n}\vert f_{r_{n-1}},\) so that \(\gcd(f_{r_{n-1}}, f_{r_n}) = f_{r_n}.\) Since \(r_n = \gcd(m, n),\) we have that \(\gcd(f_m, f_n) = f_{\gcd(m,n)}.\)

As an immediate corollary of this theorem we have