Greatest Common Divisor. Euclidean algorithm

The greatest common divisor (GCD) of two numbers, say 12 and 8, is the greatest number (in this case, 4) that divides them without a remainder. It is denoted as gcd(12, 8) = 4. Note that numbers 12 and 8 have other common divisors, 1 and 2, lower than 4. The Greatest Common Divisor is also called the Highest Common Factor (HCF).

Fig. 1 Using the Euclidean algorithm, we can manually calculate the greatest common divisor. 

We use the greatest common divisor (GCD) to determine a relationship between different quantities. Consider having 12 blue and 8 red cans of paint. We want to know what color we get by mixing them. The gcd(12, 8)=4 simplifies a ratio 12:8 to 3:2. Now we can reference a color mixing guide and learn that the color will be purple (Fig. 2). The GCD is also used to simplify fractions and related tasks.

Fig. 2.  Three blue and two red parts make purple. Source: BBC Bitesize

When dealing with small numbers, we can find the GCD by listing all divisors and choosing the largest. However, this will get increasingly problematic when numbers grow larger. For example, mixing 693 blue and 462 red cans will also make purple because the gcd(693, 462) = 231 simplifies 693:462 to 3:2. Finding all common divisors, such as 1, 3, 7, 11, 21, 33, 77, and 231, is a time consuming task, prone to mistakes. So, is there a way to find the greatest common divisor, bypassing all the lower ones? The Euclidean algorithm does just that.

Euclidean algorithm (geometrical illustration)

Euclid introduced this algorithm in his treatise Elements around 300 BC, using a geometrical approach to illustrate it. In Fig. 3, left, we consider two lengths, AB and CD, which have no numeric values. We aim to find the greatest common unit that divides them exactly. This unit is CF, though we don't know it yet. Once identified, CF can quantify the lengths as AB=10xCF and CD=7xCF, with a ratio of 10:7. Here, 10 and 7 are integers, proving the GCD stipulation is satisfied. How do we find the unit CF?

The Euclidean algorithm begins its search from the top of the ladder, unlike our previous approach, which started from the bottom. The algorithm selects the highest possible GCD for the two lengths, which is the shorter length, and checks if it fits into AB without a remainder. The GCD can't exceed the shorter length because dividing the smaller by the larger results in a fraction. If we had AE and CF (Fig. 3, right) as the starting pairs, this step would yield the answer immediately, gcd(AE, CF) =CF. Euclid chose a more interesting option.

Fig. 3  Euclidean algorithm, geometrical illustration.

We start with two lengths, AB and CD (Fig. 3, mid-left), where CD is the shortest. CD fits into AB once, with AE left as a remainder. This step splits AB into two segments, EB and AE, which means we can replace gcd(AB, CD) with gcd(EB, AE, CD). Given that EB = CD, we have gcd(AB, CD) = gcd(CD, AE, CD). Discarding a duplicate CD, we arrive at:

gcd(AB, CD) = gcd(CD, AE), where AE = AB - CD

Continuing with the new pair, CD and AE, Fig. 3 mid-right, we again divide the longer CD by the shorter AE and have a remainder CF. This splits CD into three segments, AE, AE, and CF, so we can write gcd(CD, AE) = gcd(AE, AE, CF, AE) = gcd(AE, CF):

gcd(CD, AE) = gcd(AE, CF), where CF = CD - 2xAE

Assuming CD=a, AE=b, 2=q (quotient), and CF=r (remainder), we conclude: 

gcd(a, b) = gcd(b, r), where r = a - qxb

It is irrelevant how many times the shorter length fits into the longer. This will affect the ratio (10:7) but not the GCD. We focus exclusively on the remainder, r=CF, and the shorter length, AE, because they will make the next pair, AE and CF. So, we can replace subtraction with division, and find the remainder using this operation:

 AE ÷ CF = 3 with a remainder of 0 (r=0)

This principle of substituting the longer length with the shorter one is fundamental to the Euclidean algorithm. The remainder (r) will be smaller than a and b, so we will keep reducing the lengths until one divides perfectly into the other.. When this occurs, the GCD is determined (Fig. 3, right).

Applying the Euclidean algorithm to lengths

The Euclidean algorithm is a systematic process that efficiently finds the GCD. During each step, it selects a shorter length as the candidate for the GCD, discards it if proven wrong, and continues the process until the remainder is zero. This approach ensures no greater divisor is overlooked and no smaller divisor is tested. When r=0, no new pair can be formed, eliminating further division.

Let's now see how the algorithm works in practice. First, we divide the longer AB by the shorter CD:

Step 1 AB÷CD = 1 with a remainder of AE

We have a remainder r = AE and will continue with a new pair, CD and AE.

Step 2 CD÷AE = 2 with a remainder of CF

We still have a remainder, r=CF, and continue with a new pair, AE and CF:

Step 3 AE÷CF = 3 exactly (r=0)

There is no remainder. The gcd(AB, CD) = CF.

Euclidean algorithm (numerical illustration)

We can also prove the algorithm using a numerical approach. In Fig. 4, two groups of dots represent numbers 30 and 12. The gcd(30, 12)=6 is the largest unit, comprising 6 dots, that divides them both evenly. Now, we can express the size of each group as 30=5x6 and 12=2x6, simplifying their ratio from 30:12 to 5:2.

Fig. 4  Euclidean algorithm illustrated with dots.

We know that the GCD of two numbers will be the smaller number, provided it divides the larger number without a remainder. This would be the case if we had numbers 30 and 5, for instance. In our case, 30÷12= 2 with a remainder of 6. The division breaks 30 into three numbers, 12, 12, and 6, Fig. 4.

Fig. 5  Proof of the Euclidean algorithm, numerical method

So,rather than calculating gcd(30, 12), we need to determine gcd(12, 12, 6, 12). Discarding the duplicate 12s, we get gcd(30, 12) = gcd(12, 6). In other words, the same principle applies, with a slightly different approach to visualizing the algorithm for clearer understanding.

Applying the Euclidean algorithm to numbers

The approach remains unchanged. So, we'll use this demonstration to explore how the algorithm identifies shortcuts to the solution. Without the Euclidean algorithm, we would have to go through all divisors, starting with the lowest and finishing with the highest. The divisors of 30 are 1, 2, 3, 5, 6, 10, 15, 30, while those of 12 are 1, 2, 3, 4, 6, 12. The common divisors are 1, 2, 3, and 6, with the greatest being 6. Even with the numbers as small as 30 and 12, this method is tedious and prone to errors. Let's see how the Euclidean algorithm eliminates several divisors at each step.

Step 1 30 ÷ 12 = 2 remainder 6

Two divisors are eliminated: 18 for being higher than 12, and 12 for leaving a remainder. The new pair is 12 and 6.

Step 2 12 ÷ 6 = 2 exactly.  

Five divisors are eliminated when gcd(18, 12)=6 is identified: 9 for being higher than 6, and 1, 2, 3, 4 for being lower than 6.

Additional examples

Example 1. This represents the classic Euclidean scenario, depicted in Fig. 2, where we allocate numerical values as AB=130 and CD=91 (ratio 10:7).

Given pair 130 and 91

130 ÷ 91 = 1 remainder 39

New pair 91 and 39

91÷39=2 remainder 13                     

New pair 39 and 13

39÷ 13 =3 (r=0). gcd(130, 91) = 13

Example 2. Using the Euclidean algorithm is crucial when dealing with larger numbers such as 3623 and 1017. These numbers share only one common divisor, which is 1. This is the smallest common divisor possible since every number is divisible by 1.

Given pair 3623 and 1017

3623 ÷ 1017 = 3 remainder 572   

New pair 1017 and 572

1017 ÷ 572 = 1 remainder 445                     

New pair 572 and 445

572 ÷ 445 = 1 remainder 127

New pair 445 and 127

445 ÷ 127 = 3 remainder 64

New pair 127 and 64

127 ÷ 64 = 1 remainder 63

 New pair 64 and 63

64 ÷ 63= 1 remainder 1 (64 = 1x63 +1)

New pair 63 and 1

63 ÷ 1 = 63 (r=0). gcd(3623, 1017) = 1

The GCD of three or more numbers

Finding the GCD of three or more numbers may seem daunting, but it is easier than you think. The key factor is that the GCD of multiple numbers can't exceed the GCD of any two because it must divide each number without a remainder. We choose the two lowest numbers, a and b. If gcd(a, b)=1, then the GCD of all numbers is 1, gcd(a, b, c...)=1. If gcd(a, b)=2, and all remaining numbers are even, then gcd(a, b, c...)=2.  However, if gcd(a, b)=2, and there are odd numbers among the others, then gcd(a, b, c...)=1. This is because if the GCD of all numbers can't be 2 or greater, then the only possibility left is 1. It is uncommon for a random set of numbers to have a high GCD, so the more numbers involved, the greater the likelihood of the GCD being low. In general, the formula is:

gcd(a, b, c) = gcd[c, gcd(a, b)]  

Applying this formula, you can calculate the GCD of as many numbers as you need.