8.7. Greatest Common Divisor (GCD)

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.

The GCD of two numbers, denoted as GCD(a, b), is the highest number that can exactly divide both a and b without leaving any remainder. In simpler terms, among all the positive integers that divide both numbers equally, the GCD is the largest one. For example, when we take the numbers 8 and 12, their common divisors are 1, 2, and 4, with 4 being the largest, so GCD(8, 12) = 4. When two numbers have a GCD of 1, they are termed 'co-prime' or 'relatively prime', indicating that they share no other common divisor besides 1.

Think of GCD as finding the largest group size for people who want to work together in teams without leaving anyone out. For instance, if you have 8 apples and 12 oranges, the largest number of groups you could form, ensuring each group has the same number of fruits, is 4. Each group consists of 2 apples and 3 oranges.

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.

Co-prime numbers are a special case of the GCD. If two numbers have only one as their common divisor, they are called co-prime. For example, the numbers 8 and 15 are co-prime because their only common divisor is 1. This indicates that they are not divisible by any other common integers. Understanding co-primality helps in various applications, including simplifying fractions and calculating least common multiples.

Imagine two groups of people wanting to trade goods. If one group has 8 oranges and the other has 15 bananas, they cannot exchange evenly (i.e., without leaving some behind) except for one fruit at a time. Hence, they are considered co-prime with respect to their goods, as there's no larger group size that divides both evenly.

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, a,..., and in the same way, the integer b will have its unique prime power factorization.

To find the GCD using prime factorization, you first break both numbers down into their prime factors. For example, if we take 18 and 24: 18 can be factored to 2^1 * 3^2 and 24 to 2^3 * 3^1. The GCD is then found by taking the lowest powers of all prime factors present in both decompositions — here, it would be 2^1 * 3^1 = 6. While this method is effective, it can become computationally heavy for larger numbers.

Think of prime factorization as finding the fundamental building blocks of objects. If 18 and 24 were sets of building blocks, each prime factor represents the kind of block (like colors or shapes). When determining the items they can build together, using the smallest available pieces helps show what they can create collaboratively.

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.

Euclid's GCD algorithm offers an efficient method for calculating the GCD without needing prime factorization. The process relies on the principle that the GCD of two numbers also divides their difference. Specifically, if we have two numbers a and b (with a > b), we can replace a with a - b, and repeat this process until one of the numbers reaches 0. When that happens, the remaining number will be the GCD. This method is not only elegant but also very efficient.

Picture two large piles of building blocks. If you keep removing blocks in equal portions from both piles until you can no longer take a full portion from one of them, the size of the remaining blocks in the smaller pile is analogous to the GCD of the two piles. It shows you how much is left evenly shared between the two original piles.

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

This property simplifies the process of finding the GCD significantly. Instead of directly working with the original numbers a and b, we can repeatedly apply this property — substituting the larger number a with the smaller number b, and the remainder r — until we reach a situation where the remainder reaches zero. At that point, the last non-zero remainder is the GCD. This iterative step reduces the size of the numbers we are working with, making the calculations easier.

Consider a situation where you have 30 apples and 12 apples. By swapping out the larger number with the smaller number and finding the remainder, you simplify your problem of making equal quantities — eventually leading you to the size of the largest equal group of apples you can form without having any leftover.

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?

The running time of Euclid's algorithm is indeed polynomial, which means it handles larger numbers efficiently. This property stems from Lame's Theorem and states that the number of steps (or iterations) required in Euclid's algorithm correlates with Fibonacci numbers. In practice, this means the algorithm runs in a time frame that grows reasonably as the size of the numbers increases, making it feasible for even large integers.

Think of it like using a machine to assemble something. As the materials get larger, the machine still works effectively without slowing down significantly. Euclid's algorithm is like a well-designed machine that continues to process efficiently no matter how large the inputs become.

--