The Euclidean Algorithm
Named after the ancient Greek mathematician Euclid, the Euclidean algorithm is the oldest known non-trivial algorithm, described in Euclid's famous book "Elements" from 300 BCE.
The Euclidean Algorithm
The Euclidean algorithm finds the greatest common divisor (gcd) of two numbers and .
The greatest common divisor is the largest number that divides both and without leaving a remainder.
Finding the greatest common divisor using division.
Result:
Calculations
The algorithm uses division with remainder. It takes the remainder from the previous step to set up the calculation in the next step.
How it works:
- Start with the two initial numbers and .
- Do a division with remainder:
- Use the remainder () and the divisor () from the last calculation to set up the next calculation:
- Repeat steps 2 and 3 until the remainder is .
- The second last remainder calculated is the greatest common divisor.
Continue reading to see how the Euclidean algorithm can be done by hand, with programming, and to understand how and why the algorithm actually works.
Mathematical Terminology
Below are words used to describe the Euclidean Algorithm that you need to know to understand the explanations on this page.
Divisor: A number we can use to divide a number by, without leaving a remainder. We say that 3 is a divisor of 6 because , without leaving a remainder (the remainder is 0).
Remainder: The part you are left with after dividing a number with another number. Dividing 7 by 3 is 2, with a remainder of 1. (So 3 is not a divisor of 7.)
Common divisor: For numbers and , a common divisor is a number that can divide both and without leaving a remainder. The common divisors of 18 and 12 are 2, 3, and 6, because both 18 and 12 can be divided by 2, 3, and 6 without producing a remainder.
Greatest common divisor: The largest of the common divisors. The greatest common divisor of 18 and 12 is 6 because that is the largest of the common divisors 2, 3, and 6.
The greatest common divisor is used in the mathematical field of Number Theory, and in cryptography for encrypting messages.
Note: All numbers used by the Euclidean algorithm are integers.
Manual Run Through
To understand how the Euclidean algorithm works, and to write the code for it, let's first run it manually to find the greatest common divisor of and .
To do this we use division with remainder.
Step 1: We start with dividing with :
How many times can we fit inside ? It is times, right? is . We get the remainder by subtracting from .
Step 2: We use the previous remainder in the next step to divide :
We can fit inside one time. We get the remainder by subtracting from .
Step 3: In the next calculation we divide with the previous remainder :
We get as the remainder, and that means that we are done with the calculations.
The greatest common divisor of and is .
Implementation of The Euclidean Algorithm
To find the greatest common divisor using division, we continue running the algorithm until the remainder calculated is .
This is the same as saying we continue to run the algorithm as long as is not . That is why b != 0
is the condition in the while
loop below.
Example
Finding the greatest common divisor of 120 and 25 using the Euclidean algorithm:
def gcd_division(a, b):
while b != 0:
remainder = a % b
print(f"{a} = {a//b} * {b} + {remainder}")
a = b
b = remainder
return a
a = 120
b = 25
print("The Euclidean algorithm using division:\n")
print(f"The GCD of {a} and {b} is: {gcd_division(a, b)}")
Run Example »
The Original Euclidean Algorithm
Instead of using division like we did above, the original Euclidean algorithm as described in the book "Elements" over 2000 years ago uses subtraction.
Finding the greatest common divisor using subtraction.
Result:
Calculations
How the Euclidean algorithm with subtraction works:
- Start with the two initial numbers and .
- Find the difference . The difference shares the same greatest common divisor as and .
- Take the two lowest numbers of , , and , and find the difference between them.
- Repeat steps 2 and 3 until the difference is .
- The second last difference calculated is the greatest common divisor.
Using subtraction instead of division is not as fast, but both the division method and the subtraction method uses the same mathematical principle:
The greatest common divisor of numbers and , is also the greatest common divisor of the difference between and .
This can be shown in just a few lines.
Numbers and have a greatest common divisor .
This means that both and can be factorized like this:
After factorization, subtracting from gives us a very interesting result:
We can see that the greatest common divisor () of and is also the greatest common divisor of the difference between and !
This principle is why the Euclidean algorithm works, it is what makes it possible.
Finding The Greatest Common Divisor Using Subtraction
Using the principle described above, that the difference between and also shares the same greatest common divisor, we can use subtraction to find the greatest common divisor, like Euclid's original algorithm does.
Let's find the greatest common divisor of from using subtraction.
According to the mathematical principle already described, the numbers , , and all share the same greatest common divisor.
This means we can further reduce our problem by subtracting from :
If we continue like this, always taking the two lowest numbers from the previous step and finding the difference between them, we get these calculations:
The Euclidean algorithm using subtraction is done when the difference is .
The greatest common divisor of and can be found in the previous step, it is .
Now that we can calculate the greatest common divisor using subtraction by hand, it is easier to implement it in a programming language.
Implementation of The Euclidean Algorithm Using Subtraction
To find the greatest common divisor using subtraction, we continue running the algorithm until the difference between and is , like we have just seen.
This is the same as saying we continue running the algorithm as long as and are different values. That is why a != b
is the condition in the while
loop below.
Example
Finding the greatest common divisor of 120 and 25 using the Euclidean algorithm with subtraction:
def gcd_subtraction(a, b):
while a != b:
if a > b:
print(f"{a} - {b} = {a-b}")
a = a - b
else:
print(f"{b} - {a} = {b-a}")
b = b - a
return a
a = 120
b = 25
print("The Euclidean algorithm using subtraction:\n")
print(f"The GCD of {a} and {b} is: {gcd_subtraction(a, b)}")
Run Example »
Comparing The Subtraction Method With The Division Method
To see how good the division method can be to find the greatest common divisor, and how the methods are similar, we will:
- Use subtraction to find the greatest common divisor of and .
- Use division with remainder to find the greatest common divisor of and .
- Compare the subtraction and division methods.
1. Using Subtraction
Finding the greatest common divisor of and using subtraction:
Using subtraction, the algorithm is finished when the difference is .
In the second last calculation we see that the greatest common divisor of and is .
Notice how and must be subtracted many times, until finding the GCD.
2. Using Division
Finding the greatest common divisor of and using division with remainder looks like this:
Using division, the Euclidean algorithm is finished when the remainder is .
The previous remainder is the greatest common divisor of and .
3. Comparison
Take a look at the subtraction and division methods above.
To easier see that the division calculations are basically the same as the subtraction calculations, we can write the division with remainder calculations like this:
Using subtraction, is subtracted from a total of times, while the division method does this in just one step.
Similarly, the subtraction method subtracts a total of times, while the division method does the same in just one calculation.
As you can see, the methods do the same thing, the division method just does many subtractions in the same calculation, so that it finds the greatest common divisor faster.