image

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.

Get Fibonacci and Lucas Numbers with Applications, Volume 1, 2nd Edition now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.