8.7.3. 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.

In this chunk, we define the concept of the greatest common divisor (GCD). The GCD is the largest number that can evenly divide two given integers a and b. If the GCD of two numbers is 1, this indicates the two numbers don't have any other common divisors other than 1; in this case, they are termed as co-prime or relatively prime.

Think of GCD as the largest piece of cake you can cut equally from two different-sized cakes. If two cakes can only share a piece of cake that weighs 1 unit without leaving any leftovers, then you can say that the two cakes are co-prime.

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 a1, a2, an 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.

Here, we discuss one method for finding the GCD through prime factorization. Each integer can be expressed as a product of prime numbers raised to their respective powers. To get the GCD, you take each common prime factor with the lowest exponent across both numbers. Although this method works, it's often impractical for large numbers due to the difficulty of performing prime factorization.

Imagine breaking down a Lego structure into individual blocks that represent prime factors. If one structure has some blocks that another does not, you can only build a new structure using the blocks they both share, and you can use only as many of each block as the smaller structure has.

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.

This chunk introduces Euclid’s GCD algorithm as an efficient method for computing the GCD compared to prime factorization. It's considered one of the oldest algorithms still in use today. Euclid's algorithm is significant not just for computing GCD, but as a foundational example of algorithm design in computer science.

Think of Euclid's algorithm like a systematic method for finding the best pair of socks from two different piles where you keep comparing pairs until you find the most similar ones left.

Now, 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.

This chunk explains a key observation leading to Euclid’s algorithm: for two numbers a and b, we can compute their GCD by replacing a with b and b with the remainder of a divided by b (r). This continues iterating until the remainder is zero, at which point the last non-zero remainder is the GCD.

Imagine you're sharing a batch of cookies between two friends. You keep taking out full handfuls (the bigger number), until there is only a few cookies (the smaller number) left. Eventually, the last handful represents the greatest amount of cookies they can share equally without breaking any.

So, based on this observation, this is a very simple Euclid‟s algorithm, your input pair is a, b where a is greater than b and idea is that in each iteration, we will use this rule: to reduce the magnitude of our a and b till we reach a point where r becomes 0.

In this section, the actual steps for implementing Euclid's algorithm are outlined. You begin by defining two numbers, a and b, and repeatedly replace the larger number with the smaller number, and the smaller number with the remainder from dividing the larger number by the smaller one. This process continues until the remainder is zero, at which point the last non-zero number is the GCD.

Imagine you have a rope of length 'a' and 'b'. You keep cutting pieces of 'b' from 'a' until you no longer have enough rope left. The last length you manage to cut before running out is the greatest length that can be cut evenly from both lengths.

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.

This part makes a vital point about the algorithm's performance: each iteration reduces the values of a and b or the remainders, which means the process will eventually stop. It guarantees that we won’t loop infinitely, making the algorithm efficient.

Think of a countdown timer. Each second that counts down brings you closer to reaching zero; similarly, each iteration in Euclid's algorithm reduces a number towards zero, ensuring you'll eventually reach a conclusion.

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?

This chunk discusses the time complexity associated with Euclid’s algorithm, asserting that it operates in polynomial time relative to the number of bits needed to represent the numbers. Based on Lame's theorem, it shows the connection between the number of iterations needed and the Fibonacci sequence, ensuring that the number of divisions (or steps) is manageable and efficient.

Think about manually checking each equation of a math quiz. You might have a limited number of questions. If you can verify each question quickly, the overall time taken will still be capable of being estimated or predicted, similar to how we can estimate the time complexity of Euclid's algorithm.

So that means Euclid‟s algorithm is actually a polynomial time algorithm polynomial in the number of bits that you need to represent your integers a and b.

The conclusion reinforces the efficiency of Euclid’s GCD algorithm, stating its polynomial time performance in terms of input size, establishing its utility in computational tasks even with the emergence of complex algorithms later in computer science.

Imagine a highly efficient cashier at a supermarket who can quickly handle transactions. The more customers they serve without delays, the more effective and time-efficient they are judged to be—just as Euclid’s algorithm is recognized for speed and efficiency in computing GCD.

--