What is the Euclidean algorithm

Where is it's origin?

Discovered by Greek mathematician, Euclid, known for his major contributions to euclidean geometry and his observations led to his conclusion of some basic universal truths (axioms) in geometry. His contributions occurred around 300 BCE and not much is known of him. The algorithm has improved overtime from Euclid's original solution.

What is the Euclidean algorithm?

It is a simple concept used to find the greatest common divisor between two integers. The GCD of 100 & 75 is 25. There is greater significance to the algorithm than meets the eye. Without this algorithm we would have to factor large numbers to a prime number form to find the overlapping divisor. Factorizing large numbers is highly expensive, aka hard. The algorithm works recursively by removing parts of a whole iteratively until one set (b) is zero, and the populated set (a) should contain the number representing the greatest common divisor. A sentence to describe the algorithm that I found on the internet: given two line segments, find the biggest line segment which cleanly divides both. Why does it work? It just does, it's intuitive to visualize but not easy to conceptualize. The final solution seems to have no relation to the two input numbers, but in actuality, it does.

What is it's significance?

Many critical cryptographic algorithms are build on top of the euclidean algorithm. It is a very important sub-routine and without it the internet would cease to exist in a useable fashion, and there would be no bitcoin.

Example:

Code (java):

public static int gcd(int a, int b) {
   if (b==0) return a;
   return gcd(b, a % b);
}

Time: O(loga). Why log? Because the amount of calls is reduced by half with the modulus operation

Space: O(loga). For the iterative solution it is O(1) due to no call stack.

Summary:

The key piece of logic in this algorithm involves modular arithmetic. Modulus operand returns the remainder. Modulus operations are commonly used to handle overflows when referencing time, although most of us will never think about it this deeply. For example, when we refer to the hour clock, we don't say 13 o'clock. The modulus operation 13%12 returns 1 (o'clock). The hour clock uses mod 12. For days of the week we'd use mod7, months would be mod12, seconds & minutes would be mod60, etc.

Difficulty (1-5) is level two. It is a concise algorithm, but it's recursive nature takes some time to understand. There is an extended euclidean algorithm as well, I'm going to bed.

Thanks for reading!