The greatest common divisor (GCD) of two numbers, say 12 and 8, is the largest number (in our 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, smaller than 4. The Greatest Common Divisor can also be called the Highest Common Factor (HCF).
The greatest common divisor is used when we need to examine the relationship between different quantities. Let us have 12 blue and 8 red cans of paint. We want to know what colour we get by mixing them. The gcd(12, 8)=4 will simplify the ratio 12:8 to 3:2. The colour mixing guide will identify the colour of the mixture as purple (Fig 1). If we mix 693 blue and 462 red cans, we get the same purple colour because gcd(693, 462) = 231 simplifies the ratio 693:462 to 3:2. The GCD helps different quantities to find common ground.
Fig 1 3 parts of blue and 2 parts of red make purple.
Source: BBC Bitesize
When numbers are small, we can calculate the GCD by listing all common divisors and selecting the highest. However, this method becomes increasingly problematic when numbers get larger. For example, establishing that numbers 693 and 462 have common divisors 1, 3, 7, 11, 21, 33, 77, and 231 is not an easy task. So, can we establish a procedure that delivers us straight to the greatest common divisor, bypassing all the smaller ones on the way? The Eucleadian algorithm does just that.
Proof of the Euclidean algorithm (geometrical approach)
Euclid described the algorithm in his treatise Elements, c. 300 BC. As a geometer, he chose a geometrical approach to proving it. In Fig 2, we consider two lengths, AB and CD. Note the lengths have no numerical value. Their unit of measurement is the gcd(AB, CD)=CF, which fits into both lengths evenly. We can now write AB=10xCF and CD=7xCF. Here, 10 and 7 are integers, as they must be to satisfy the condition of no remainder imposed on the GCD. Applying basic arithmetic, we get:
AE = AB - CD = 10xCF - 7xCF = 3xCF
Number 3 is also an integer because the difference between two integers can't make a fraction. Consequently, we can state that if the unit CF fits exactly into the lengths AB and CD, it must also fit exactly into their difference AE= AB - CD. This conclusion allows us to replace the lengths (AB and CD) with the new ones (CD and AE). This principle forms the basis of the Euclidean algorithm. Assuming AB=a, CD=b, and AE=r (remainder), we can notate this principle as:
gcd(a, b) = gcd(b, r), where r = a - b
Fig 2 Euclidean algorithm, geometrical illustration.
Source: wikipedia.org
The unit CF is marked in yellow on AB and CD to help you visualise this principle. The marks coincide because the unit is common. It fits exactly into EB because EB=CD, and so it does into AE because it must continue doing so to complete AB in the same fashion. The number of times the unit CF goes into AB and CD affects the ratio (10:7), not the GCD. We're only interested in the remainder. Replacing subtraction with division, we get:
AB÷CD= 1 with a remainder of AE -> AB= CDx1+AE
Assuming AB=a, CD=b, 1=q (quotient), and AE=r (remainder), we can generalise the principle as follows:
gcd(a, b) = gcd(b, r), where a=bxq + r
Note that this formula works for the lower common divisors as well. We can divide the unit CF into two or more parts, and the principle will hold. We know the fraction 10/7 is irreducible as 10 and 7 have no other common divisors than 1. This proves that CF is the largest common unit. But how does the algorithm ensure this?
The GCD of two lengths will be the shorter, provided it fits exactly into the longer one. The GCD can't be higher than the smaller number because dividing the smaller by the larger will make a fraction. So first, the algorithm tests the shorter length for the GCD:
Step 1 AB÷CD=1 with a remainder of AE
We have a remainder and can eliminate CD from the GCD candidates. The formula replaces the original pair (a=AB, b=CD) with a new pair (b=CD, r=AE). In the second step, the algorithm tests AE for the GCD:
Step 2 CD÷AE= 2 with a remainder of CF
Again, we have a remainder, so eliminate AE from the GCD candidates. The formula replaces the pair (a=CD, b=AE) with the new pair (b=AE, r=CF). In the third step, the algorithm tests CF for the GCD:
Step 3 AE÷CF= 3 exactly (r=0)
There is no remainder, so the gcd(AB, CD) = CF. If r≠0, we continue repeating these steps until r=0. The GCD will always be the last divisor when r=0.
Step after step, the algorithm tests the greatest common candidate allowed for the given pair and eliminates it if proven wrong. Since a remainder is always smaller than a divisor, the candidates gradually get smaller until one is small enough to fit exactly into the paired length. This approach ensures the GCD can't be missed and replaced with the lower option. When r=0, we won't have a new pair to continue divisions. So, there is no room for mistakes. The Euclidean algorithm is a step-by-step procedure that finds the GCD safely and with minimal effort.
Proof of the Euclidean algorithm (numerical approach)
The Euclidean algorithm is not restricted to geometry. It works for all physical quantities: time, mass, etc. Fig 3 offers a numerical approach to visualising the algorithm. Here, two groups of dots represent numbers 18 and 12. The gcd(18, 12)=6 is the largest common unit, consisting of 6 dots, which divides completely into both groups. We can say that the group of 18 dots comprises 3 units (18=6x3), and the group of 12 dots comprises 2 units (12=6x2).
Fig 3 Euclidean algorithm explained with dots.
The steps are identical. Again, the GCD of two numbers is the smaller one, provided it is divided evenly into the larger one. So first, the algorithm determines if number 12 is the GCD:
Step 1 18÷12=1 with a remainder of 6 -> 18= 12x1+6, q=1, r=6
We have a remainder and can eliminate 12 from the GCD candidates. Applying basic arithmetic (Fig 4) and bearing in mind that number 12 repeats, we get gcd(18, 12) = gcd(12, 6, 12) = gcd(12, 6).
Fig 4 Numerical proof of the Euclidean algorithm
Assuming 18=a, 12=b, 1=q, and 6=r, we arrive at the same formula as before:
gcd(a, b) = gcd(b, r), where a=bxq + r
The formula replaces the pair (18 and 12) with a new pair (12 and 6). Again, the algorithm tests the smaller number 6 for the GCD:
Step 2 12÷6=2 exactly, so gcd(18, 12)=6.
The algorithm always searches for the GCD from the top, so the lower divisors are never considered. Let's see how it works in practice.
Number 18 has divisors 1, 2, 3, 6, 9,18
Number 12 has divisors 1, 2, 3, 4, 6, 12.
Step 1. The algorithm:
a) eliminates candidate 18 because it is higher than 12
b) eliminates candidate 12 because there is a remainder. Creates new pair (12 and 6).
Step 2. The algorithm:
a) eliminates candidate 9 because it is higher than 6
b) identifies 6 as the GCD because there is no remainder. The lower common divisors 1, 2, 3 and a divisor 4 never get their turn.
Example
This is the case, illustrated in Fig 2. The lengths have been given the numerical values AB=130 CD=91. We can shorthand the notation 130÷91=1 with a remainder of 39 to 130÷91=1 r39.
Given numbers 130 and 91
130 ÷ 91 = 1 r39
New numbers 91 and 39
91÷39=2 r13
New numbers 39 and 13
39÷13=3 (r=0). The last divisor 13 is the GCD, gcd(130, 91) = 13
Example
We have numbers 3623 and 1017. Without the algorithm, it wouldn't know where to start. The algorithm finds the GCD smoothly.
Given numbers 3623 and 1017
3623 ÷ 1017 = 3 r572
New numbers 1017 and 572
1017÷572=1 r445
New numbers 572 and 445
572÷445=1 r127
New numbers 445 and 127
445÷127=3 r64
New numbers 127 and 64
127÷64=1 r63
New numbers 64 and 63
64÷63=1 r1
New numbers 63 and 1
63÷1=63 (r=0). The last divisor 1 is the GCD, gcd(3623, 1017) = 1
Finding the GCD of three or more numbers
The GCD of three or more numbers can't be higher than the GCD of any two of them. Start with the two smaller numbers, a and b. If gcd(a, b) = 1, you don't need to go any further, the GCD of all numbers is 1. If not, we replace a and b with the gcd(a, b) and pair it with the next number c. The formula is:
gcd(a, b, c) = gcd(c, gcd(a, b))
By applying this formula, we can calculate the GCD of as many numbers as we need.
Comments