Greatest Common Divisor. Euclidean algorithm

The greatest common divisor (GCD) of two numbers, say 12 and 8, is the largest number (in this case, 4) that divides them both 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).

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 the ratio of 12:8 to 3:2. The color mixing guide identifies the color as purple (Fig 1). Thus, the GCD helps the quantities to establish common ground. It is also used to simplify fractions and similar problems.

Fig 1 3 parts blue and 2 parts red make purple. Source: BBC Bitesize

When dealing with small numbers, we can find their GCD by listing all divisors and picking the largest. However, this method becomes increasingly difficult as the numbers get larger. For example, mixing 693 blue and 462 red cans also yields 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 not an easy task. So, is there a way to find the greatest common divisor bypassing the lower ones? The Euclidean algorithm does precisely that.

Proof of the Euclidean algorithm (geometrical method)

Euclid introduced the algorithm in the treatise Elements around 300 BC, using a geometrical approach to explain it. In Fig 2 left, we consider two line segments, AB and CD, which have no numeric values. Their lengths can only be defined relative to each other. Our task is to find the greatest common unit that divides them both without leaving a remainder. This unit is CF, though we don't know it yet. Once identified, this unit can be used to express the length of the segments as AB=10xCF and CD=7xCF, resulting in the ratio of 10:7. Here, 10 and 7 are integers, validating that the GCD condition is satisfied. The question is, how do we find this unit?

The greatest common divisor (GCD) of two lengths is the shorter one, provided it divides the longer one exactly. This would be the case if the starting pair were AE and CF. The GCD can't be greater than the shorter length because dividing a smaller number by a larger number produces a fraction. In our case, we test CD for the GCD by measuring it on AB (Fig 2 mid-left). It goes into AB once with AE left over. This rules out CD as the GCD. The move divides AB into two segments, EB and AE, both divisible by the GCD: EB because it equals CD, and AE because if it were not, AB would comprise one divisible and one indivisible part, rendering it indivisible as a whole. Since AE must also be divisible by the GCD, we can discard EB and replace the original pair, AB and CD, with a new pair, CD and AE.

Fig 2 Euclidean algorithm, geometrical illustration.

This strategy of replacing the longer length with the shorter one forms the basis of the Euclidean algorithm. We can further validate this approach by applying the following logic. By dividing AB into two segments, EB and AE, we essentially replace gcd(AB, CD) with gcd(EB, AE, CD). Given that EB=CD, we can write: gcd(AB, CD) = gcd(EB, AE, CD) = gcd(CD, AE, CD). Discarding the duplicate CD, we get:

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

Continuing with the new pair, CD and AE, Fig 2, mid-right, we test the shorter segment, AE, for the GCD. AE goes into the CD twice with CF left over. This rules out AE as the GCD. The move splits CD into three parts, AE,  AE, and CF, allowing us to write gcd(CD, AE) = gcd(AE, AE, CF, AE) = gcd(AE, CF). It is irrelevant to us how many times the shorter length goes into the longer one. This will affect the ratio (10:7) but not the GCD. We focus exclusively on the remainder (CF) because we use it to create a new pair. Thus, we can rewrite the Euclidean principle as:

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

The remainder (r) will always be smaller than a and b, so we will keep reducing the length of the segments until one exactly fits into the other. Once it happens, the GCD is identified (Fig 2, right).

Applying the Euclidean algorithm to lengths

The Euclidean algorithm is a step-by-step procedure that provides the quickest path to the GCD. At each step, it selects the shorter length for the GCD, eliminates it if proven wrong, and repeats until there is no remainder. This approach guarantees that the final divisor is the greatest. When r=0, the new pair can't be formed, so the lower divisors are never considered. For convenience, we calculate the remainder (r) using division instead of subtraction: r = a - qxb, a = qxb + r, a÷b = q with a remainder of r.

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

We have tested a shorter CD for the GCD and are left with a remainder r=AE. We can eliminate CD from the GCD candidates. Replacing AB and CD with a new pair, CD and AE, we continue:

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

We have a remainder, CF, which eliminates AE from the GCD candidates. We replace CD and AE with a new pair, AE and CF:

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

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

Proof of the Euclidean algorithm (numerical method)

We can demonstrate the algorithm using a numerical approach. In Fig 3, 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 3 Euclidean algorithm, illustrated with a group of 30 dots and a group of 12 dots.

We know that the GCD of two numbers is the smaller one, provided it divides the larger one 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 12, 12, and 6, Fig 4. The rules of arithmetic imply that if numbers 30 and 12 are divisible by the GCD, number 6 must also be divisible by the GCD.

Fig 4 Proof of the Euclidean algorithm, numerical method

We discard the duplicate 12 and get:

 gcd(30, 12) = gcd(12, 12, 6, 12) = gcd(12, 6) where 6 = 30 - 2x12

Assuming 30=a, 12=b, 2=q (quotient), and 6=r (remainder), we arrive at the Euclidean principle stated in the geometrical method: 

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

Applying the Euclidean algorithm to numbers

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, whereas the divisors of 12 are 1, 2, 3, 4, 6, 12. The common divisors are 1, 2, 3, 6, with the greatest being 6. Even though our numbers are not large, this approach is laborious and prone to mistakes. The Euclidean algorithm adopts the reverse top-down strategy, bypassing all irrelevant divisors.

Step 1 30÷12=2  remainder 6

Two divisors have been eliminated in one go: 18 (higher than 12, would yield a fraction); and 12 (left a remainder). The new pair is 12 and 6.

Step 2 12÷6=2 exactly, so gcd(18, 12)=6.  

The GCD is identified. Five divisors have been eliminated in one go: 9 (higher than 6); and 1, 2, 3, 4 (lower than 6).

Additional examples

Example 1. This is the original Euclidean case, illustrated in Fig 2. We have assigned the lengths numerical values AB=130 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 appear 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. Let's start with the two lowest numbers, a and b, and find the gcd(a, b). The GCD of all numbers can't be higher. So, if gcd(a, b)=1, there's no need to proceed with other numbers, 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,  the only possibility left is 1. It is uncommon for a random set of numbers to have a large GCD. 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.