The Mathematics
Why Use the Euclidean Algorithm?
Explanation of the Algorithm and Connections
Extensions
Before getting into the mathematics, we should clarify some terms first.
•An integer is a whole number. For example -1, 3, and 60 are all integers.
•A divisor is a number that divides into another without a remainder. For example 30, 15, 10, 6, 5, 2 and 1 are all divisors of 30.
•The greatest common divisor of two integers is the largest positive integer that divides both of the integers without a remainder, and the notation is gcd (a,b) = d, where a and b are integers and d is their GCD.
Why Use the Euclidean Algorithm?
Finding the greatest common divisor of two integers may seem like a trivial task, especially if those numbers are smaller. Let’s take 40 and 35 for example. All you would need to do is list all of the divisors of each integer: the set of divisors of 40 = {1, 2, 4, 5, 10, 20, 40}, the set of divisors of 35 = {1, 5, 7, 35}, then choose the largest integer that is common to both sets, which in this case is 5. Therefore gcd (40,30) = 5.
What if you were interested in finding the GCD of two large integers such as 100,576 and 30,084? It would take a while to list out all of the divisors of each integer and then search them to find the largest common divisor. This is where the Euclidean Algorithm comes in handy.
Explanation of the Algorithm and Connections
The basis of the Euclidean Algorithm is the division theorem. The division theorem states an integer can be divided by a positive integer b in such that the remainder is smaller than b. The exact theorem is below:
For integers a and b, with b > 0, there exist unique integers q and r satisfying
a = q∙b + r, 0 ≤ r < b.
Here q is called the quotient and r is the remainder.
Referring back to the definition of a divisor, if b is a divisor of a, then r would be equal to 0.
Let’s do a couple of examples:
Let a = -64 and b = 6, then:
-64 = -11 ∙ 6 + 2, 0 ≤ 2 < 4.
Let a = 36 and b = 4, then:
36 = 9 ∙ 4 + 0, 0 < 4.
Here is an original applet I created to help visualize the division theorem.
We can use the division theorem to find the GCD, the result process is called the Euclidean Algorithm:
Let a and b be two integers whose GCD is wanted, then we can assume 0 < b ≤ a.
We start by applying the division theorem:
a = q1 ∙ b + r1, 0 ≤ r1 < b.
If r1 = 0, then b | a, and since b | b, gcd (a,b) = b. If r1 ≠ 0, divide b by r1 and you will get integers q2 and r2 such that:
b = q2 ∙ r1 + r2, 0 ≤ r2 < r1.
If r2 = 0, then r1 | b, so we stop and gcd (a,b) = r1. If r2 ≠ 0, then we divide r1 by r2 to get:
r1 = q3 ∙ r2 + r3, 0 ≤ r3 < r2
This division continues until a zero remainder appears, this will be the (n + 1)st stage where rn−1 is divided by rn.
a = q1 ∙ b + r1, 0 < r1 < b,
b = q2 ∙ r1 + r2, 0 < r2 < r1,
r1 = q3 ∙ r2 + r3, 0 < r3 < r2,
...
rn-3 = qn−1 ∙ rn-2 + rn-1, 0 < rn-1 < rn-2,
rn-2 = qn ∙ rn-1 + rn, 0 < rn < rn-1,
rn-1 = qn+1 ∙ rn + 0.
rn, the last nonzero remainder in this algorithm, is equal to gcd (a,b). Here’s why:
•rn | rn−1 by the last equation of the above system. From the second to last equation, it follows that rn | rn−2 because rn−2 is a linear combination of rn and rn−1, both of which are divisible by rn. Working backward through these equations, we can see that rn divides each of the preceding remainders. Finally rn | b, and from the first equation a = q1 ∙ b + r1, we get rn | a because a is a linear combination of b and r1 both of which are divisible by rn. Therefore, rn is a positive common divisor of a and b.
• Suppose that d is an arbitrary positive common divisor of a and b. The first of the equations tells us that d | r1 since d | a and a is a linear combination of a and r1. Going further down the list of equations, you can see that d divides r2, r3, . . rn. d | rn, where d and rn are both positive integers, implies that d ≤ rn. Therefore, rn is the largest of the positive common divisors of a and b; thus, gcd (a,b) = rn.
Let’s do an example:
Let a=526 and b= 123, then the gcd (526,123), the last remainder obtained from the Euclidean Algorithm, is 1. The steps of the algorithm are shown below.
526 = 4 ∙ 123 + 34
123 = 3 ∙ 34 + 21
34 = 1 ∙ 21 + 13
21 = 1 ∙ 13 + 8
13 = 1 ∙ 8 + 5
8 = 1 ∙ 5 + 3
5 = 1 ∙ 3 + 2
3 = 1 ∙ 2 + 1
2 = 2 ∙ 1 + 0
Here is an original applet that gives a geogemtrical representation of the Euclidean Algorithm, with questions that can be used for an activity.
Extensions
The gcd (a,b) can always to written as a linear combination of integers a and b. The process by which this is done is an extension of the Euclidean Algorithm called…wait for it… the EXTENDED Euclidean Algorithm. This process is explained below:
We start by rearranging the next-to-last equation from the algorithm into a linear combination of rn-2 and rn-1:
rn = rn-2 – qn ∙ rn−1,
Next we will solve the preceding equation in the algorithm for rn−1 and substitute it into the above equation:
rn = rn−2 − qn(rn−3 − qn−1 ∙ rn−2)
= (1 + qn ∙ qn−1)rn−2 + (−qn)rn−3.
Continuing this process backward through the system of equations, we eliminate the remainders rn−1, rn−2, . . . , r2, r1 until a stage is reached at which rn = gcd (a,b). The result is the existence of integers x and y such that gcd (a,b) = ax + by.
Here is an example:
Let a = 12,378 and b = 3,054, then the application of the Euclidean Algorithm results in these system of equations:
12,378 = 4 · 3054 + 162
3054 = 18 · 162 + 138
162 = 1 · 138 + 24
138 = 5 · 24 + 18
24 = 1 · 18 + 6
18 = 3 · 6 + 0.
Thus, gcd (12,378 , 3,054) = 6. Using the Extended Euclidean Algorithm results the following linear combination:
6 = 24 − 18
= 24 − (138 − 5 · 24)
= 6 · 24 − 138
= 6(162 − 138) − 138
= 6 · 162 − 7 · 138
= 6 · 162 − 7(3054 − 18 · 162)
= 132 · 162 − 7 · 3054
= 132(12,378 − 4 · 3054) − 7 · 3054
= 132 · 12,378 + (−535) · 3054.
Back to top of page