Among the important concepts in arithmetic that a student of mathematics will address, we find the concepts of the greatest common divisor and the least common multiple of two natural integers. To understand how to calculate them, you must first understand how to determine the factors and multiples of a natural integer.
Let's take, for example, the numbers 18 and 24. To determine the greatest common divisor, we first determine the denominators of 18 and the divisors of 24 as follows:
We note that there are a set of common divisors:
The greatest of this divisors is the greatest common divisor, and we write .
The greatest common divisor of two natural integers is the largest number that divides these two numbers.
in other word, let , and three non-zero natural integers.
If therefore, there exist two natural integers k and k' such that and .
No doubt you have noticed that once we say "Greatest Common Factor" and once we say "Greatest Common Divisor", they are in fact the same thing.
In the previous paragraph, we determined the gcd of two numbers only because it is the most used in arithmetic lessons, but in some cases we have to calculate the greatest common divisor of more than two numbers. In the same way, we display the list of divisors of each number and then take the greatest common divisor.
For example, let's define gcd of the numbers 18, 20 and 28.
We note that there are a set of common divisors: , therefore,
Find: ; and .
After we've done some examples, now you can easily find gcd without going back every time to all the steps in the previous examples. From now on, you will be able to find gcd more quickly just by looking at the two numbers and working out their factors mentally.
Divisors of 36:
Divisors of 16 are:
Divisors of 96:
Divisors of 64 are:
Divisors of 48:
Divisors of 9:
Divisors of 8 are:
if the greatest common divisor of and is 1, we say that and are coprime.
As with the greatest common divisor, we determine the multiples of the two numbers and then compare the common multiples and take the smallest of them, which will be the least common multiple (lcm).
Let's take, for example, the numbers 4 and 6.
So the common multiples are all numbers that are divisible by 4 and 6 at the same time and are an infinite set. In this example, 12 is the smallest common multiple of 4 and 6, and no other number smaller than 12 is divisible by 4 and 6 at the same time.
Thus we write:
The least common multiple of two numbers is the smallest number that is divisible by those two numbers.
Let , and three non-zero natural integers.
if then, there exist two natural integers k and k' such that and such that: and .
Find: and .
Multiple of 7 are:
Multiples of 4 are:
Multiple of 2 are:
Multiples of 3 are:
Multiples of 5 are:
Let's find the and .
Divisors of 6 are:
Divisor of 15 are:
Multiples of 6 are:
Multiples of 15 are:
Can you infer the relationship between the gcd and the lcm in this example?
If you observe carefully, you will find that the product of the gcd and the lcm is equal to the product of 6 and 15.
Let and two non-zero natural integers.
Calculate knowing that .
We know that: