8.7.2. Finding GCD using Prime Factorization

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.

The Greatest Common Divisor (GCD) is the largest number that can divide two or more integers without leaving a remainder. When you hear the term 'GCD of a and b,' think of it as finding the largest 'common factor' between these two numbers. For instance, if we take the numbers 12 and 8, their factors are 1, 2, 3, 4, 6, 12 for 12 and 1, 2, 4, 8 for 8. The GCD here would be 4, as it's the largest number found in both lists.

Imagine you and a friend have collections of fruit. You have 12 apples and your friend has 8. If you both want to make fruit baskets that can only have whole apples and want equal numbers of apples in each basket, the GCD (which is 4) tells you that you can create 4 baskets with 4 apples each, but not more than that.

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.

Two numbers are said to be co-prime if they have no common factors other than 1. For example, numbers like 8 and 15 are co-prime because the only divisor they share is 1, while 8 has factors of 1, 2, 4, and 8, and 15 has factors of 1, 3, 5, and 15. Understanding co-primality is important when working with fractions and simplifying them.

Consider a scenario where you and your friend are each building a wall with bricks. You have 8 small bricks and your friend has 15 large bricks. You want to combine the bricks but only want to use them in groups without breaking any bricks. Here, since your brick sizes and counts don’t allow for an equal split except for using just one brick each, you both are 'co-prime.'

One approach could be that you use the prime factorization of a and b, what do I mean by that.

To find the GCD using prime factorization, you break down each number into its prime factors. For instance, if a = 12 can be factored into 2^2 * 3 and b = 18 can be factored into 2 * 3^2. Then to find the GCD, you take the lowest power of all prime factors that appear in both factorizations. In this case, GCD(12, 18) would be 2^1 * 3^1 = 6.

Imagine you are given different types of LEGO blocks to build two structures: one using 12 blocks of different types and another using 18 blocks. If you want to create a design using the maximum number of the same type of block from each structure, finding the GCD gives you the maximum size of identical blocks you can use (in this case, 6).

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. So, we do not prefer to use this algorithm in general if your a and b are very large quantities.

While using prime factorization offers a systematic way to find the GCD, it can be impractical for large numbers. Calculating the prime factors of large integers can take considerable time. For example, factoring a large number like 123456789 can require significant computation, making this method less attractive in scenarios where speed is important.

Think of prime factorization like searching for buried treasure. If your treasures are small and simple (like smaller numbers), it's easy to dig them up quickly. But when the treasure is a massive chest (large numbers), finding the right spot takes a lot longer and requires more effort.

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 a computational task, interesting computational tasks of course addition, subtraction, they are also computational tasks and you have algorithms for that.

Euclid's GCD algorithm provides a more efficient method for finding the GCD without requiring prime factorization. It operates on the principle that the GCD of two numbers also divides their difference. By taking the two numbers and repeatedly replacing the larger number with the remainder when the larger number is divided by the smaller, you quickly reduce the size of the numbers, converging towards the GCD.

Imagine you need to cut two pieces of ribbon of lengths 54 cm and 24 cm into the longest possible equal pieces without leftover. Instead of measuring and cutting them all down to their prime lengths, you could simply keep checking the remaining lengths until you can't cut anymore. This practical approach mimics how Euclid's algorithm repeatedly finds remainders until it reaches a resolution.

--