Finding Greatest Common Factor (GCF) And Least Common Multiple (LCM)

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.

Greatest Common Factor (Divisor)

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:

Divisors of 18 are:
Divisors of 24 are:

We note that there are a set of common divisors:

The greatest of this divisors is the greatest common divisor, and we write .

Note:

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 .

Info!

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.

Greatest Common Factor (GCF)
Greatest Common Divisor (GCD)
Highest Common factor (HCF)

Greatest common factor for more than two numbers

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.

Divisors of 18 are:
Divisors of 20 are:
Divisors of 28 are:

We note that there are a set of common divisors: , therefore,

Example1:

Find: ; and .

Solution:

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.

Finding
Divisors of 36:
Divisors of 16 are:
Thus,
Finding
Divisors of 96:
Divisors of 64 are:
Divisors of 48:
Thus,
Finding
Divisors of 9:
Divisors of 8 are:
Thus,

Info!

if the greatest common divisor of and is 1, we say that and are coprime.

Least Common Multiple (LCM)

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.

Multiples of 4 are:
Multiples of 6 are:

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:

Note:

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 .

Example2:

Find: and .

Solution:

Finding
Multiple of 7 are:
Multiples of 4 are:
Thus,
Finding
Multiple of 2 are:
Multiples of 3 are:
Multiples of 5 are:
Thus,

Relationship between LCM and GCD

Let's find the and .

Finding
Divisors of 6 are:
Divisor of 15 are:
Thus,
Finding
Multiples of 6 are:
Multiples of 15 are:
Thus,

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.

Thus,

Note:

Let and two non-zero natural integers.

Example3:

Calculate knowing that .

Solution:

We know that:

Thus,