Euclidean Algorithm

Imagine you're trying to find the

Greatest Common Divisor

between two numbers: {a, b}.
In mathematical notation this would be denoted as: gcd(a, b).

You can plug this into a calculator and the result will always be a whole number greater than or equal to 1. The Euclidean Algorithm is the standard systematic method for how this is computed.

Lets look at an example: gcd ( 15, 125 ) .

Here: a=125 and b=15.
Do not get confused because of the order of the numbers; a will always be greater than b. So we know the bigger number can be rexpressed in terms of the smaller number. In this case:
125 = 15 * 8 + 5.

Now whats important to note is the divisor, and the remainder. The remainder ( 5 ) must be smaller than the divisor, if it wasn't we could just simplify the remainder more.
So taking this fact, we can express the divisor in terms of the remainder.

15 = 5 * 3 + 0.

Systematically, we can repeat this process until the remainder is 0. When the remainder is 0 that indicates that the smaller number (the divisor) has gone into the bigger number (the dividend) completely. This systematic repetition is the computational application of Euclid's Algorithm.

I interchangeably use the name "Euclid" and "Euclidean" but both are referring to the same algorithm.

Proof

The Greatest Common Divisor

of our two original numbers {a,b} is the same as the GCD of {b,r}.
We can write the equation:

a = (b * q) + r

where q is the quotient (a divided by b, rounded to a whole number)
and r is the remainder.

Divide the equation by any constant " d " to a or b, and you get:

a/d = (b/d * q) + r/d

We can express r as { a - b*q } by rearranging the original equation.
After grouping like terms and reorganization:

a/d = (b/d * q) + (a - b*q)/d

a/d = (b/d * q) + a/d - b*q/d

a/d - a/d = (b/d * q) - b*q/d

0 = 0.

This shows that the GCD of {a,b} is the same as the GCD of {b,r}, as they are the foundational building blocks of the same two numbers.