Topic 2 Euclidean Algorithm

”[The Euclidean algorithm] is the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day.”

– Donald Knuth, The Art of Computer Programming Vol. 2, p. 318

The Euclidean algorithm (sometimes referred to as Euclid’s algorithm) is an algorithm in number theory that is used to compute the greatest common divisor (i.e., gcd) between two integers. The algorithm is named after the Greek mathematician Euclid who first published this algorithm in his work Elements:

Figure 2.1: A Photo of Euclid’s Elements

As you may recall from the first video lecture of BS1009, an algorithm is a series of well-defined steps (i.e., instructions) that aim to achieve something. The Euclidean algorithm is a practical example of the latter; yet, in spite of the algorithm’s aformentioned use, it can also be used for many other purposes: cryptography, reducing fractions, and in the case of this document, converting numbers from decimal to other number systems!