Euclid’s Algorithm For Finding The Greatest Common Divisor

By Chandrahas M. Halai

Finding the GCD of two small numbers is pretty easy. But what if we have to find the GCD of two very large numbers like 3,87,205 and 12,903? Well, it is very difficult and long procedure to find the GCD by the method one has learnt in the school. Ancient Greek mathematician, Euclid (300 BCE), had given a quick and easy method to calculate the GCD of a pair of numbers.

Let us calculate the GCD of the above pair of numbers by Euclid’s method.

As a first step in the Euclid’s algorithm divide the larger number by the smaller number as shown here:

387205 = (30 x 12903) + 115

We have 30 as the quotient and 115 as the remainder.

Now, as the second step of the algorithm, divide the smaller number by the remainder obtained above. We have

12903 = (112 x 115) + 23

As the next step, divide the previous remainder by the new remainder. We have

113 = (5 x 23) + 0

When we get zero as the remainder, the algorithm terminates. Here, the last non-zero remainder is the GCD.

Hence, we have GCD(387205, 12903) = 23.

Let us use this algorithm to find  the GCD of another pair of integers 16,209 and 15,470.

16269 = (1 x 15470) + 799

15470 = (19 x 799) + 289

799 = (2 x 289) + 221

289 = (1 x 221) + 68

221 = (3 x 68) + 17

68 = (4 x 17) + 0

We have, GCD(16269, 15470) = 17.

Let us now generalise this by finding the GCD of a pair of integers m and n. 

The first step of the algorithm will be

We can enumerate the steps of the algorithm as shown below:

Here, r_n is the GCD of m and n.

If we let

and

then, we have the first step of the algorithm has

Now, the i_th step in the algorithm can be represented as:

Does this algorithm give us the GCD?

Let us analyse this?

Is r_n the common divisor of m and n?

Let us start from the bottom, that is the last step of the algorithm and work our way up.

The last step:

Here, we see that r_n divides r_n-1.

The penultimate step:

Here, r_n divides both r_n as well as r_n-1. Hence, r_n will also divide r_n-2.

Now, the previous step:

We know that r_n divides both r_n-1 and r_n-2, hence it will divide r_n-3.

The step previous to this:

Here, r_n divides both r_n-2 and r_n-3, hence it will divide r_n-4.

In the same way, working our way up we reach the second step:

We know that r_n divides both r₁ and r₂, hence it will also divide n.

Moving up to the first step, we have:

We know that r_n divides r₁ and n, hence it will divide m.

Thus, we establish that r_n is a common divisor of m and n.

But how can we say that r_n is the greatest common divisor?

Let d be any common divisor of m and n. From the first step of the algorithm, we have:

Since d divides both m and n, it will also divide r₁.

Moving to the second step, we have

We now know that d divides r₁ and n, hence it will also divide r₂.

Moving to the next step, we have

We know that d divides r₁ and r₂, hence it will also divide r₃.

Continuing down step by step when we reach the i^th step, we have

From above, at every step we establish that d divides the previous two remainders, hence it will also divide the next remainder. Thus, we have that d divides both r_i-2 and r_i-1. Hence, we say that d also divides r_i.

Eventually, when we reach the penultimate step:

We can say that d divides r_n.

Hence, we can say that if d is any common divisor of m and n then d will divide r_n. Therefore, we say that r_n must be the GCD of m and n.

Will Euclid’s GCD algorithm always terminate?

In the first step, we have:

Here, r₁ can have integer values between 0 to n-1.

In the next step, we have:

Here, r₂ can have values between 0 and r₁ – 1.

In the third step, we have:

Here, r₃ can have values between 0 and r₂ – 1.

We can see that with every successive step we have continually decreasing remainders. That is

r₁ > r₂ > r₃ > …

Eventually we reach a step where the remainder equals 0. Hence, we can say that this algorithm always terminates.