Greatest common divisor

What is the abc conjecture | Open and solved problems | Consequences | The algorithm

In an abc triple the numbers a, b and c have to have a greatest common divisor of 1. On this page we will explain the concept of the greatest common divisor and why it must be 1.

What is so special about even numbers? What do even numbers have in common? If you think about it for a while, you will realize the answer: all even numbers are divisible by 2. Mathematicians say that all even numbers have a common divisor, namely 2. There are more numbers with a common divisor. For example 14 and 21 have common divisor 7, as they are both divisible by 7.

Divisors

A divisor of a number is a number which divises the first number. 2 is a divisor of 6 as 6 is divisible by 2. 5 is a divisor of 10, 17 is a divisor of 170 and so on. 1 is a special case as every integer is divisible by 1. If a number has exactly 2 divisors (1 and itself) it is called a prime number.

Let have a look at all divisors of 12. They are 1, 2, 3, 4, 6 and 12. And all divisors of 15 are 1, 3, 5, and 15. You may see that 12 and 15 have a pair of divisors in common: 1 and 3. We call them the common divisors of 12 and 15. So the greatest common divisor of 12 and 15 is 3. We abbreviate this by saying 3 is the GCD of 12 and 15. For any 2 numbers you can find the greatest common divisor. Let's have look at another example: The divisors of 27 are 1, 3, 9 and 27. The divisors of 18 are 1, 2, 3, 6, 9 and 18. So the GCD of 27 and 18 is 9. This is the greatest divisor of both 18 and 27.

Relatively prime

Two numbers always share a common divisor, which is 1. It may occur that the 2 numbers have no other divisors in common. 2 and 3 for example: 2 has divisors 1 and 2, 3 has divisors 1 and 3, so the GCD is 1. We say 2 and 3 are relatively prime. This is a special property required for abc triples. When you have an abc triple, a and b should be relatively prime. Why should this be the case? Because it would be very easy to create abc triples for numbers with a GCD larger than one. For example, You could say 2ⁿ + 2ⁿ = 2ⁿ⁺¹, so the radical would always be 2, no matter how big n is.

It may be nice to know if 2 numbers are relatively prime. If you know the GCD of 2 numbers, you can make them relatively prime, by dividing them by the GCD. So if you have 27 and 18, which have a GCD of 9, you can make them relatively prime by dividing 27 and 18 by 9. The result is 3 and 2.

Euclid's algorithm

It is pretty hard to find all divisors of a number. Fortunately, we can find the GCD of 2 numbers without finding all divisors of the numbers. To do this, we use Euclid's algorithm. Euclid was a Greek mathematician who lived in the 3^rd century B.C. He found a way to find the GCD of 2 numbers very quickly. We will show you how this works with an example:

We will find the GCD of 4403 and 5406. We will keep repeating the following 2 steps.

Subtract the smallest number from the largest number as many times as you can.
Replace the largest number with the number you just found.

We can subtract 4403 only once from 5406: 5406 - 4403 = 1003. We now replace 5406 by 1003 and repeat the steps with these numbers:

4403 - 4 × 1003 = 391

1003 - 2 × 391 = 221

391 - 221 = 170

221 - 170 = 51

170 - 3 × 51 = 17

51 - 3 × 17 = 0

Now that we reached 0 we terminate the algorithm. The number found before 0 is the GCD of the numbers you started with.

Proof of correctness

For proving the correctness of this algorithm we are going to prove that any divisor of a and b will survive the algorithm. To do this we are going to assume k is a number dividing both a and b. This means we can write a = k × l and b = k × m. So a - i × b = k × (l - i × m) and we see k is a divisor of a - i × b. Since all we do is subtract numbers of the form k × m of k × l, k will survive all steps of the algorithm.