8.7.5. Proof of Euclid’s GCD Algorithm

Now let us next define the greatest common divisor or GCD. So, imagine you are given 2 numbers a and b which are nonzero integers. And the GCD of a and b is the greatest integer which divides both a and b. So, we say integers a and b are relatively prime, we also use the term co-prime if their greatest common divisor is 1. That means so of course, 1 is a common trivial divisor of every a and b. But if 1 happens to be the only common divisor, or if 1 happens to be the greatest common divisor of a and b, then we say that a and b are co-prime or relatively prime. Whereas if we have n values, a to a_n, and they are pairwise, we call them as pairwise relatively prime. If you take any pair of values a_i and a_j in the set of n values which are given to you, they are co-prime to each other.

Greatest Common Divisor (GCD) is a fundamental concept in number theory that refers to the largest positive integer that divides two or more non-zero integers without a remainder. For instance, for the numbers 8 and 12, the GCD is 4 because 4 is the highest number that divides both 8 and 12 evenly. When two numbers have a GCD of 1, they are termed co-prime, meaning they have no common positive factors other than 1. For example, 8 and 15 are co-prime since their only common divisor is 1.

Think of GCD in terms of sharing. If you have 8 apples and 12 oranges, the GCD of 4 represents the largest number of identical fruit baskets you can make without having leftovers. If you wanted to distribute the apples and oranges evenly into baskets, you could create 4 baskets, each containing 2 apples and 3 oranges. If two friends have 10 and 15 candies respectively and want to distribute them among themselves evenly without leaving any behind, they can only do so in groups of 5 candies (GCD is 5).

One approach could be that you use the prime factorization of a and b, what do I mean by that. So, as per the fundamental theorem of arithmetic, a will have its unique prime factorization namely a can be expressed as product of prime powers. So, let the various powers of the primes used in the representation of a are a_1, a_2, a_n and so on. And in the same way, the integer b will have its unique prime power factorization, then it is easy to see that the GCD of a, b will be this value: (p_1^min(a_1, b_1) * p_2^min(a_2, b_2) ... * p_k^min(a_k, b_k)). But to use this algorithm at the first place, you have to come up with a prime power factorization of a and b which in itself is a very computationally heavy task.

The traditional method of finding the GCD of two numbers involves determining their prime factorizations. Every integer greater than 1 can be expressed uniquely as a product of prime numbers raised to specific powers. For instance, if a = 24 can be factored into 2^3 * 3^1 and b = 36 can be factored into 2^2 * 3^2, the GCD can be found by taking the lowest power of each prime factor present in both factorizations. This results in GCD = 2^min(3, 2) * 3^min(1, 2) = 2^2 * 3^1 = 12. However, finding prime factorization is computationally expensive, especially for large numbers.

Imagine sorting a fantastic collection of toy blocks into piles, each defined by their colors. To find out how many blocks can be evenly piled without leftovers, you would determine the prime colors that form each block. However, categorizing them based on their prime colors can become particularly tedious if you have thousands of colorful blocks! The GCD approach, while insightful, isn't the most efficient method for larger collections.

Instead what we use is Euclid's GCD algorithm which is probably one of the oldest algorithms known. In fact, people believe that this is the first instance of an algorithm for any computational task, interesting computational tasks of course addition, subtraction, they are also computational tasks and you have algorithms for that. But this is probably a very interesting computation namely the computing GCD and Euclid gave a very simple algorithm, which we will be seeing soon.

Euclid's GCD algorithm offers a methodical way of finding the GCD of two integers without needing to factor them. Instead of breaking down the numbers into their prime components, the algorithm reduces the problem iteratively. By continuously replacing the larger number with the remainder from dividing the two numbers, this process rapidly converges on the GCD, making it significantly more efficient, especially for larger integers.

Consider the process of simplifying a messy room. Instead of organizing every item and figuring out how many duplicates you have, you could start by moving larger items out of the way, focusing only on smaller sections at a time. Just like this, Euclid's algorithm works by narrowing down the problem step by step until only the essential information (the GCD) remains. This is not only simpler but also saves time and effort!

So, the crucial observation on which the Euclid's GCD algorithm is based upon is the following. Our goal is to find out GCD of a, b. And for simplicity, imagine a is greater than b. So, the idea that is used in the Euclid's GCD algorithm is that if a is some q times b + r, where r may be 0, if a is divisible by b, otherwise, r will be something in the range of 0 to b - 1. So, if a is b times q + r, then we can see that the GCD of a and b is same as the GCD of b and r.

The essence of Euclid's algorithm is that the GCD(a, b) can also be computed as GCD(b, r) where r is the remainder of a divided by b. When implementing this method, it is assumed that a is greater than b. If b divides a evenly, the remainder r is 0, and, consequently, the GCD is b. If not, the process continues by replacing 'a' with 'b' and 'b' with the remainder r, iterating this process until the remainder becomes zero.

Think of a mechanic breaking down a complex car problem into simpler parts. If a car's engine has various components that interact, instead of looking at the engine as a whole, the mechanic identifies faults in one component at a time, gradually narrowing down the problem. Similarly, Euclid's algorithm breaks the problem of finding the GCD into manageable parts, leading to a faster solution.

Now, what is the guarantee that this iteration will eventually terminate what is a guarantee that this is not going to loop forever. The reason that it will eventually terminate is that in each iteration, you are definitely reducing the value of your y by at least 1 because you are now taking; you are updating the sequence of remainders.

Each iteration of the Euclid's algorithm reduces the problem size, ensuring that we get closer to the solution with every calculation. Since the remainder r will always decrease at least by 1 in each step, it guarantees that you cannot repeat indefinitely. Thus, this iterative process will eventually arrive at a point where the remainder becomes 0, signaling the end of the algorithm.

Imagine you’re climbing a mountain and every few minutes you know you’re getting shorter breath, you're taking fewer steps as you approach the peak. The closer you get to the top, the less frequent your steps become until you finally reach the summit. Much like climbing, Euclid’s algorithm guarantees progress by continually reducing the range of possible answers.

So, the now, next question is what is the running time of the Euclid GCD algorithm: is it polynomial in the number of bits that I need to represent my a and b or not? Because that will be our measure get will be our measurement of time complexity. And there is a very interesting result attributed to Lame which says the following and we will use this theorem to conclude that Euclid's running time is polynomial in the number of bits that you need to represent your a and b.

The efficiency of Euclid's algorithm is measured by how many iterations (or divisions) it performs relative to the size of the inputs (in bits). Thanks to Lame's theorem, which states that the number of iterations required correlates with Fibonacci numbers, we can deduce that the time complexity is logarithmic with respect to the smaller input, making it polynomial in terms of the number of bits needed to represent a and b.

Consider a race where you can only take half a step back each time. This method of halving your step size guarantees that you will always finish the race in a limited number of steps, showcasing a predictable and efficient completion time. Similarly, the design of Euclid's algorithm ensures that it runs swiftly through its iterations, avoiding exhaustive possibilities.

--