The Euclidean Algorithm – The simplest

The Euclidean algorithm, developed over two thousand years ago by the Greek mathematician Euclid, has been hailed as one of the most revolutionary mathematical discoveries of all time. The algorithm is simple and efficient.

The algorithm may seem unimpactful given that all is does is find the GCD (greatest common divisor) and follows a very simple set of steps. However, its efficiency is unmatched and its simplicity it what makes it great. The algorithm is perfect for use in all fields, be it number theory or computer science. Here’s how the algorithm works:

We are given 2 numbers, say A and B and need to find the GCD. A naive (inefficient) solution would be to check the common factors and find the greatest out of them. Even though the time complexity would be O(n), which can be considered fast, the algorithm is too slow for big numbers.

Euclid came up with a simple answer to this problem using his own division lemma and the fact that GCD(A,B) = GCD(A%B,B) where A%B represents the remainder after A has been divided by B. This slows for a fast algorithm as large numbers can be reduced by dividing and keeping the remainder only. As the remainder gets smaller every time, we get small numbers very quickly.

The remainder can be in the range 0 ≤ r < B where B is the smaller number. As we continue, the remainder only gets smaller and smaller until it is 0. The decrease is exponential on average giving the algorithm a time complexity of O(log n).

An example of the algorithm:

GCD(57,358) where A = 358, B = 57 and we can calculate A%B as 16. Now we get:
GCD(57,16). We follow the same procedure and obtain GCD(16,9) and GCD(9,7).

We can easily see these numbers have GCD 1 but we can continue the algorithm as well.
GCD(7,2) à GCD(1,2) à GCD(1,0)

We will eventually get A%B as 0 and although 0 is not considered to have any factors, it can be divided by every number except 0. 0/x will always give 0 so every number is a divisor of 0.Using this logic, when we get GCD(x,0), we know that x is a divisor of 0 so we can give our answer as x.

This algorithm is recursive as we use GCD(A,B) = GCD(B,A%B) and can be implemented in the following way (in pseudocode):

GCD(A,B):
          IF A=0 THEN RETURN B
          ELSEIF B=0 THEN RETURN A
          IF A>B THEN RETURN GCD(B,A%B)
          ELSE RETURN GCD(A,B%A)