8.7.4. Properties of 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 Greatest Common Divisor (GCD) of two integers a and b is the largest integer that can divide both numbers without leaving a remainder. If the GCD of a and b is 1, we call them co-prime or relatively prime, meaning they have no common factors other than 1. This concept is essential in number theory as it helps understand the relationship between different integers.

Think of the GCD as the largest 'gift package' that two friends can equally share without cutting anything up. For instance, if one friend has 8 apples and the other has 12 oranges, the GCD is 4, meaning they can each get 4 sets of 2 apples and 3 oranges.

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 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: (min(a1, b1) min(a2, b2)...min(an, bn)).

Finding the GCD using prime factorization involves breaking down both integers into their prime factors. Each integer can be expressed as a product of prime numbers raised to certain powers. By comparing these factorizations, the GCD can be found by taking the minimum exponent of each prime factor that appears in both numbers. This method is accurate but computationally intense, especially for large integers as factorization can be a lengthy process.

Imagine you have two fruit baskets, one with 60 apples and another with 48 apples. If we want to find the largest common group the friends can make, we decompose the number of apples into their prime factors. 60 (2^2 * 3 * 5) and 48 (2^4 * 3). The GCD would be 12 (2^2 * 3) since it's based on the minimum power of the common prime factors.

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. 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 algorithm for finding the GCD is an efficient method that uses the principle that the GCD of two numbers also divides their difference. Starting with two numbers a and b, the algorithm repeatedly replaces the larger number by the remainder of dividing the larger one by the smaller one until one of them becomes zero. The non-zero number at this point will be the GCD. This approach is much faster than factorization, especially for large numbers.

Consider you're trying to evenly distribute 40 candies between your friends, but some friends have fewer candies (say 25). The Euclidean algorithm suggests taking the difference of the two amounts repeatedly or taking remainders until you can't divide any further, eventually leading to the exact number of candies each friend could initially receive in their most balanced sharing.

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. .. Hence, the greatest common divisor of a and b is same as the greatest common divisor of b and r.

The key property leveraged in Euclid's algorithm is that GCD(a, b) = GCD(b, r) where r is the remainder of the division of a by b. This means we can simplify the problem without changing the GCD value, by continually replacing a with b and b with r until one of them becomes zero. This iterative method reduces the size of the numbers involved, making it more manageable and leads to efficient computation.

Think of determining the GCD as navigating through a trail towards a goal. Each step forward represents reducing the numbers, like stepping down from higher to lower amounts of candy. The idea is to step closer to the point where you can't divide anymore, thus quickly getting to the exact sharing rate!

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? ... it is actually a polynomial time algorithm polynomial in the number of bits that you need to represent your integers a and b.

Euclid's algorithm is efficient because the number of steps (or iterations) it takes to reach the GCD is logarithmic relative to the size of the numbers involved. Using Lame's theorem, it can be shown that the number of iterations required is at most proportional to the logarithm of the smaller number, making it polynomial in terms of input size. This result establishes that Euclid's method is not only effective, but also computationally feasible even in larger contexts.

Just like when we count down the minutes on a clock, as you get closer to an hour mark, each passing minute reduces the waiting time significantly. The GCD process efficiently narrows down the options, ensuring you find the answer without unnecessary delays.

--