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

The greatest common divisor (GCD) of two numbers is the largest integer that can divide both of those numbers without leaving a remainder. For example, if you have the numbers 12 and 8, the GCD would be 4, because 4 is the highest number that can divide both evenly (12/4=3 and 8/4=2).

Think of the GCD like a shared toolbox where you and a friend want to divide tools equally. If you have tools numbered '8' and '12', the largest number of tools you can equally share with no leftovers (like running out of a specific tool) is '4' — you both could take home equal portions of '4' tools.

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 integers are called co-prime if their greatest common divisor is 1. This means they have no other common divisors besides 1. For instance, 15 and 28 are co-prime because the only number that divides both without a remainder is 1.

Imagine two friends, one who collects stamps from Country A and another from Country B. If none of their stamps are from the same issue, we can say their collections are co-prime because they only share one common aspect: the empty space where a shared stamp could go.

Now an interesting question is if we are given 2 values a and b, how exactly do we find out the greatest common divisor?

To find the GCD of two numbers, one method is to utilize their prime factorization. Each number can be expressed as a product of its prime factors, and the GCD can be determined by taking the smallest powers of shared prime factors. However, this method can be computationally heavy and inefficient for large numbers.

Think of prime factors like ingredients in a recipe. If you want to make potions (let's say 'GCD potions'), each recipe has unique ingredients (representing prime numbers). To create a potion that fits the needs of both friends, you would need to find the common ingredients — the smallest amount you both agree upon.

Instead what we use is Euclid’s GCD algorithm which is probably one of the oldest algorithms known.

Euclid's algorithm is a more efficient method to compute the GCD of two numbers. The algorithm takes two numbers, a and b, and repeatedly replaces the larger number by the remainder of dividing the larger number by the smaller one, until one of them has a value of 0. The GCD is the last non-zero remainder.

Imagine you have a large piece of rope and a small piece, and you want to cut them into uniform smaller segments. Each time you cut a piece from the larger rope using the length of the smaller rope, you're simulating how the algorithm repeatedly uses the current lengths to find the largest length segment (GCD) that can divide both ropes without leftover.

--