The Euclidean Algorithm

The Euclidean Algorithm is one of the oldest numerical algorithms still in use today. Attributed to ancient Greek mathematician Euclid in his book “Elements” written approximately 300 BC, the algorithm serves as an effective method for finding the greatest common divisor of two whole numbers.

The greatest common divisor (GCD) of two whole numbers is the largest natural number that divides evenly into both without a remainder.

We’ll begin with the formal definition and then work an example. If mathematical notation makes your eyes glaze over, hang in there! It’s actually pretty straightforward when you see the example.

Formal Notation

In the initial setup, the values for a-0 and b are the two values we want to find the GCD of, a-o being the larger of the two. The goal of each step is to find the quotient q and remainder r that makes the equation true.

Initial Setup

The Euclidean Algorithm is a k-step iterative process that ends when the remainder is zero. (In other words, you keep going until there’s no remainder.) The GCD will be the last non-zero remainder.

First Iteration (I have a typo: r-0 is the same as r in the initial setup)

Final Iteration

Example:

Find the GCD of 1015 and 231

Don’t worry too much about the equations above, in practice it is rather simple. Let’s find the GCD of 1015 and 231.

Step 1: Begin by setting a = 1015 and b = 231. Determine how many times 231 goes into 1015 and the remainder leftover.

Since 231 x 4 = 924, replace q with 4. The remainder r will be 1015–924 = 91.

Step 2: Each iteration resets the equation with values from the previous step. Repeat step 1 with the new values 231 and 91.

To indicate it is the 1st iteration, q and r are marked with subscripts of 1.

231 ÷ 91 = 2 with a remainder of 49

Step 3: Reset the equation and increase the indexing to q-2 and r-2. Determine the quotient and remainder.

91 ÷ 49 = 1 with a remainder of 42

Step 4: Reset the equation and repeat the process.

49 ÷ 42 = 1 with a remainder of 7

Step 5: Because 7 x 6 is 42 exactly, this is our final step! The greatest common divisor of 1015 and 231 is 7.

I’ll leave it to the reader to think about why this process produces the largest number that divides nicely into both values…

Check out the visual walkthrough in the next post, it’s pretty cool →

Why Does the Euclidean Algorithm Work?

Thanks for reading!

Please click the ❤ to let me know you learned something new!

Related Reading

How Do We Know Prime Numbers are Infinite?

Intro to Modular Arithmetic

Prime Numbers & The Sieve of Eratosthenes