Fibonacci and Lucas Numbers with Applications, Volume 1, 2nd Edition

THE EUCLIDEAN ALGORITHM

This chapter continues our investigation of the properties of Fibonacci numbers. We will re-confirm, using the Euclidean algorithm, that any two consecutive Fibonacci numbers are relatively prime. To this end, we first lay the necessary foundation for justifying the algorithm.

Among the several procedures for finding the greatest common divisor (gcd) of two positive integers, one efficient algorithm is the celebrated Euclidean algorithm. Although it seems to have been known before Euclid, it is named after him. Euclid published it in Book VII of his extraordinary work, The Elements.

The next theorem paves the way for the Euclidean algorithm.

Theorem 9.1

Let a and b be any positive integers, where . Let r be the remainder when a is divided by b. Then .

Proof

Let and . To prove that , it suffices to show that and . By the division algorithm, there is a ...