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.