## DSA Tutorial

DSA HOME DSA Intro DSA Simple Algorithm

## Arrays

DSA Arrays DSA Bubble Sort DSA Selection Sort DSA Insertion Sort DSA Quick Sort DSA Counting Sort DSA Radix Sort DSA Merge Sort DSA Linear Search DSA Binary Search

## Stacks & Queues

DSA Stacks DSA Queues

## Hash Tables

DSA Hash Tables DSA Hash Sets DSA Hash Maps

## Trees

DSA Trees DSA Binary Trees DSA Pre-order Traversal DSA In-order Traversal DSA Post-order Traversal DSA Array Implementation DSA Binary Search Trees DSA AVL Trees

## Graphs

DSA Graphs Graphs Implementation DSA Graphs Traversal DSA Cycle Detection

## Shortest Path

DSA Shortest Path DSA Dijkstra's DSA Bellman-Ford

## Minimum Spanning Tree

Minimum Spanning Tree DSA Prim's DSA Kruskal's

## Maximum Flow

DSA Maximum Flow DSA Ford-Fulkerson DSA Edmonds-Karp

## Time Complexity

Introduction Bubble Sort Selection Sort Insertion Sort Quick Sort Counting Sort Radix Sort Merge Sort Linear Search Binary Search

## DSA Reference

DSA Euclidean Algorithm DSA Huffman Coding DSA The Traveling Salesman DSA 0/1 Knapsack DSA Memoization DSA Tabulation DSA Dynamic Programming DSA Greedy Algorithms

## DSA Examples

DSA Examples DSA Exercises DSA Quiz DSA Certificate

# 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 $$a$$ and $$b$$.

The greatest common divisor is the largest number that divides both $$a$$ and $$b$$ without leaving a remainder.

Finding the greatest common divisor using division.

Result:

{{ msgDone }}

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:

1. Start with the two initial numbers $$a$$ and $$b$$.
2. Do a division with remainder: $$a=q_0 \cdot b + r_0$$
3. Use the remainder ($$r_0$$) and the divisor ($$b$$) from the last calculation to set up the next calculation: $$b=q_1 \cdot r_0 + r_1$$
4. Repeat steps 2 and 3 until the remainder is $$0$$.
5. 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 $$6/3=2$$, 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 $$a$$ and $$b$$, a common divisor is a number that can divide both $$a$$ and $$b$$ 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 $$120$$ and $$25$$.

To do this we use division with remainder.

Step 1: We start with dividing $$120$$ with $$25$$:

\begin{aligned} 120 & = 4 \cdot 25 + 20 \end{aligned}

How many times can we fit $$25$$ inside $$120$$? It is $$4$$ times, right? $$4 \cdot 25$$ is $$100$$. We get the remainder $$20$$ by subtracting $$100$$ from $$120$$.

Step 2: We use the previous remainder $$20$$ in the next step to divide $$25$$:

\begin{aligned} 25 & = 1 \cdot 20 + 5 \end{aligned}

We can fit $$20$$ inside $$25$$ one time. We get the remainder $$5$$ by subtracting $$20$$ from $$25$$.

Step 3: In the next calculation we divide $$20$$ with the previous remainder $$5$$:

\begin{aligned} 20 & = 4 \cdot 5 + 0 \end{aligned}

We get $$0$$ as the remainder, and that means that we are done with the calculations.

The greatest common divisor of $$120$$ and $$25$$ is $$5$$.

## Implementation of The Euclidean Algorithm

To find the greatest common divisor using division, we continue running the algorithm until the remainder calculated is $$0$$.

This is the same as saying we continue to run the algorithm as long as $$b$$ is not $$0$$. 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:

{{ msgDone }}

Calculations

How the Euclidean algorithm with subtraction works:

1. Start with the two initial numbers $$a$$ and $$b$$.
2. Find the difference $$a-b=c$$. The difference $$c$$ shares the same greatest common divisor as $$a$$ and $$b$$.
3. Take the two lowest numbers of $$a$$, $$b$$, and $$c$$, and find the difference between them.
4. Repeat steps 2 and 3 until the difference is $$0$$.
5. 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 $$a$$ and $$b$$, is also the greatest common divisor of the difference between $$a$$ and $$b$$.

This can be shown in just a few lines.

Numbers $$a$$ and $$b$$ have a greatest common divisor $$x$$.

This means that both $$a$$ and $$b$$ can be factorized like this:

\begin{aligned} a & = k \cdot x \\ b & = l \cdot x \end{aligned}

After factorization, subtracting $$b$$ from $$a$$ gives us a very interesting result:

\begin{aligned} a-b & = k \cdot x - l \cdot x \\ & = (k-l) \cdot x \end{aligned}

We can see that the greatest common divisor ($$x$$) of $$a$$ and $$b$$ is also the greatest common divisor of the difference between $$a$$ and $$b$$!

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 $$a$$ and $$b$$ 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 $$120$$ from $$25$$ using subtraction.

\begin{aligned} 120 - 25 & = 95 \end{aligned}

According to the mathematical principle already described, the numbers $$120$$, $$25$$, and $$95$$ all share the same greatest common divisor.

This means we can further reduce our problem by subtracting $$25$$ from $$95$$:

\begin{aligned} 95 - 25 & = 70 \end{aligned}

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:

\begin{aligned} 70 - 25 & = 45 \\ 45 - 25 & = 20 \\ 25 - 20 & = 5 \\ 20 - 5 & = 15 \\ 15 - 5 & = 10 \\ 10 - 5 & = \underline{\textbf{5}} \\ 5 - 5 & = 0 \end{aligned}

The Euclidean algorithm using subtraction is done when the difference is $$0$$.

The greatest common divisor of $$120$$ and $$25$$ can be found in the previous step, it is $$5$$.

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 $$a$$ and $$b$$ is $$0$$, like we have just seen.

This is the same as saying we continue running the algorithm as long as $$a$$ and $$b$$ 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:

1. Use subtraction to find the greatest common divisor of $$120$$ and $$25$$.
2. Use division with remainder to find the greatest common divisor of $$120$$ and $$25$$.
3. Compare the subtraction and division methods.

### 1. Using Subtraction

Finding the greatest common divisor of $$120$$ and $$25$$ using subtraction:

\begin{aligned} 120 - 25 & = 95 \\ 95 - 25 & = 70 \\ 70 - 25 & = 45 \\ 45 - 25 & = 20 \\ 25 - 20 & = 5 \\ 20 - 5 & = 15 \\ 15 - 5 & = 10 \\ 10 - 5 & = \underline{\textbf{5}} \\ 5 - 5 & = 0 \end{aligned}

Using subtraction, the algorithm is finished when the difference is $$0$$.

In the second last calculation we see that the greatest common divisor of $$120$$ and $$25$$ is $$5$$.

Notice how $$25$$ and $$5$$ must be subtracted many times, until finding the GCD.

### 2. Using Division

Finding the greatest common divisor of $$120$$ and $$25$$ using division with remainder looks like this:

\begin{aligned} 120 & = 4 \cdot 25 + 20 \\ 25 & = 1 \cdot 20 + \underline{\textbf{5}} \\ 20 & = 4 \cdot 5 + 0 \end{aligned}

Using division, the Euclidean algorithm is finished when the remainder is $$0$$.

The previous remainder $$5$$ is the greatest common divisor of $$120$$ and $$25$$.

### 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:

\begin{aligned} 120 - 4 \cdot 25 & = 20 \\ 25 - 1 \cdot 20 & = \underline{\textbf{5}} \\ 20 - 4 \cdot 5 & = 0 \end{aligned}

Using subtraction, $$25$$ is subtracted from $$120$$ a total of $$4$$ times, while the division method does this in just one step.

Similarly, the subtraction method subtracts $$5$$ a total of $$4$$ 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.

×

## Contact Sales

If you want to use W3Schools services as an educational institution, team or enterprise, send us an e-mail:
sales@w3schools.com