Greatest common divisor and least common multiple
A flying swarm of magicicadas
What’s the greatest common divisor (GCD)?
The greatest common divisor, shortened by the acronym GCD is, as the name itself says, the greatest possible divisor in common among two or more integer numbers.
For example, both 12 and 16 are divisible by 2 because they are both even, but 2 is not the greatest divisor of both.
After a quick calculation, in fact, we can see that they are also divisible by 4, since the respective divisions give as results integer numbers:
By other trials, we can check that there aren’t numbers greater than 4 that are divisors of both. So 4 is said to be the greatest common divisor of 12 and 16.
But trying to compute the greatest common divisor by trials is an uneffected and expensive method, if we have large numbers.
The most effective method for doing this calculation is decomposing into prime factor the numbers which we want to compute the greatest common divisor of, and multiplying the common prime factors, taken once, powered to the least exponent.
Let’s start from factorizing both numbers in order to find the common prime factors. By a quick factorization we’ll obtain that:
We can note how both numbers have in their factorizations the number 7, which has exponent 1 in both. The other prime factors are not common. So, 7 is the greatest common divisor of both:
Let’s start by factorizing both numbers in order to find the common prime factors. By doing a quick decomposition into prime factors we’ll obtain that:
In this situation, both numbers have the common number 2 in their factorization.
However we can note that in 12 it appears twice (the exponent is 2), while in 40 it appears three times (the exponent is 3). So the least exponent for this factor is 2.
In order to compute the greatest common divisor we have to compute the product of the common factors (the ones which appears in both factorizations), but with the least exponent. In this case the only common factor is 2, and its least exponent is 2, so:
Let’s start from factorizing both numbers in order to find the common prime factors:
The numbers have two common prime factors:
- The first is 2. In 270 the exponent is not indicated, so it’s 1, while in 1008 it’s 4; the least exponent is 1, so the first factor of the GCD is 2.
- The second is 3. In 270 it has exponent 3, while in 504 it has exponent 2; the least exponent is 2, so the second factor of the GCD is 3^2.
Let’s multiply the factors we have found: we’ll obtain 2 \cdot 3^2 = 2 \cdot 4 = 8, so:
If the least common multiple between two or more numbers is 1, they are said to be relatively prime, or coprime.
The divisors 3 and 5 appear in both factorizations. Though 5 appears twice in the factorization of 75, it appears only once in the one of 195.
So:
Remember that that by divisor we mean a number such that, when the given number is divided by it, the result is an integer number. In fact:
What is the least common multiple (lcm)?
The least common multiple, shortened by the acronym lcm, is the smallest common multiple between two or more integer numbers.
For example, let’s try to compute the least common multiple between 10 and 15. By definition, we have to find the smallest of the common multiples, so let’s start from listing the multiples of the two numbers, up to finding some in common:
Multiples of 10 are 10 itself, 20, 30, 40, 50, 60, 70, 80, 90 and so on.
Multiples of 15 are 15 itself, 30, 45, 60, 75, 90 and so on.
We can note that the first common multiple which appears in these two sequences is 30, Other common multiples are 60 e 90 (and we’d have found others if we had proceeded), but we are looking for the smallest one. So 30 is the least common multiple for 10 and 15.
Computing the multiples of two or more numbers up to bumping into a common one is an operation that can take a long time.
The most effective method for doing this calculation is to decompose into prime factors the numbers which we want to compute the least common multiple of, and then multiplying the common and non-common prime factors, each taken once, powered to the biggest exponent.
Let’s start from factorizing both numbers in order to find the prime factors. Doing a quick decomposition into prime factors we’ll obtain:
In order to find the least common multiple, we have to consider common and non-common prime factors, taken only once, but this time with the biggest exponent. The overall prime factors of the two numbers, both common and non-common, are the following:
- 2 is common; it has exponent 1 for both given numbers, so the biggest exponent is 1.
- 3 is common; it has exponent 2 for 18, and exponent 1 for 30, so its biggest exponent is 2.
- 5 is a divisor of 30 only.
We can deduce that the least common multiple, shortened with lcm, is:
This means that 90 is the smallest possible number which is divisible both by 18 and by 30.
Now let’s consider the product of all prime factors taken once with the biggest exponent. The solution is:
An useful property
There is another way to compute the least common multiple if we have already computed the greatest common divisor, or vice versa. We can in fact use these relationships:
In a previous example, we have already computed lcm(10, 1 5) = 30.
Now let’s compute the product a \cdot b, i.e. 10 \cdot 15 = 150.
Using the first property just stated, we can obtain that the greatest common multiple between the two numbers is:
Let’s try to use the standard method for computing the GCD between the two numbers. Decomposing them into prime factors we’ll obtain:
We can note that the only common factor, which is powered to 1 in both numbers, is 5. So the greatest common divisor is 5, that is the same result we obtained by applying the property.
Exercises
How did Mathematics help cicadas evolution?
The magicicada lives most of its life underground in the form of nymph, but, after some time, it emerges for mating and lay down the eggs. Among the 7 species of magicicada discovered so far, 4 remain underground for 13 years, while the other ones remain underground for 17 years.
Every how many years would two populations of magicicada of different species compete for resources and survival during the mating period? The answer is indeed lcm(13, 17) = 13 \cdot 17 = 221, i.e. they would meet every 221 years!
Finally, we can note that both 13 and 17 are prime numbers, which by definition are divisible only by 1 or by themselves. In particular they have no common factor: this is why their least common multiple coincides with their product.
Decomposition into prime numbers
Decomposing a number into prime numbers means finding those prime numbers which, multiplied by each other, give as a result the initial number. For example the decomposition (or factorization) of 21 is 3 · 7, while the decomposition of 60 is 2 · 2 · 3 · 5 = 22 · 3 · 5 (in the latter case the number 2 is said to appear twice in the decomposition).In order to decompose a number into prime factors, divisibility rules are often used. They help us to find, one at time, the prime numbers which are part of the decomposition. For example, if the last digit of the number is even (0, 2, 4, 6, 8), then the number is divisible by 2, while if the sum of its digits is divisible by 3, then the number is divisible by 3.
For further details, see the page Prime numbers and factorization.
Prime number
A prime number is an integer number greater than 1 which is divisible only by 1 and by itself.There are infinitely many prime numbers, but it's easy to remember the first ten ones: 2, 3, 5, 7, 11, 13, 17, 23, 29, 31.
Divisibility
Equivalently, the relationship can also be expressed by saying that b is a divisor of a.
Powers
The operation of multiplying a number by itself many times can be written in a more concise way as a power. The exponent indicates how many times the number has been multiplied by itself.8 \cdot 8 \cdot 8 \cdot 8 = 8^4. The exponent of 8 is 4 because 8 has been multiplied by itself four times.
