In this section, let us understand how to calculate the Least Common Multiple (LCM) and Greatest Common Divisor (GCD) of numbers.
Before beginning the discussion, we need to learn what are the factors and multiples of a number.
Factors of a number are the numbers which will divide the given number without leaving any remainder.
For example, the factors of 20 are 1,2,4,5,10 and 20
Multiples of a number are generated by multiplying other integers with the given number.
For example, the multiples of 6 are 6,12,18,24,30…
☛ Greatest Common Divisor (GCD)
The greatest common divisor of two numbers is the largest number that will divide both numbers without leaving a reminder. It is also called as Highest Common Factor (HCF).
☞Consider the numbers 12 and 15
☞Factors of 12 are 1, 2, 3, 4, 6, 12
☞Factors of 15 are 1, 3, 5, 15
☞Common Factor are 1, 3
☞Highest common factor is 3.
☞So, 3 is the Greatest Common Divisor of 12 and 15.
☛ Least Common Multiple (LCM)
The Least Common Multiple of two numbers is the lowest number that is the multiple of both the numbers
☞ Consider the number 10 and 15.
☞ Multiples of 10 are 10, 20, 30, 40, 50, 60, 70, 80, 90, 100…
☞ Multiples of 15 are 15, 30, 45, 60, 75, 90, 105, 120, 135…
☞ Here the common multiples of 10 and 15 are 30, 60, 90…
☞ Therefore, the Least Common Multiple is 30
☛ Note: The same concepts of GCD and LCM can be extended for more than two numbers.
☛ Finding HCF and LCM using Prime Factorization Method
Let’s take two number 30 and 50 for which we want to find the LCM and GCD.
Step 1: Write each number as the product of its prime factors
30 = 2 × 3 × 5
50 = 2 × 5 × 5
Step 2: This is an optional step. To make further calculations easier, write these factors in a way such that each new factor begins in the same place
30 = 2 × 3 × 5
50 = 2 × 5 × 5
This step allows us to match up the factors.
The Greatest Common Divisor is found by multiplying all the factors that are common in both the list.
So, the GCD is 2 × 5 which is 10
- The Least common multiple is found by multiplying all the unique factors that appear in either list, i.e. if the factor is common in both, take once and if factors are not in common, consider all of them.
So, the LCM is 2 × 3 × 5 × 5 which is 150.
☛ Facts about GCD and LCM
- GCD is used to equally distribute two or more sets of items into their largest possible grouping and LCM to figure out when something will happen again at the same time.
- GCD is useful for computing the modular multiplicative inverse. This is used in cryptography; particularly noteworthy is its use in public-key cryptosystems that are used to secure online transactions.
- Coprime numbers are the numbers whose GCD is equal to 1.
- The product of LCM and GCD of two numbers is equal to the product of those two numbers.
- The greatest number that exactly divides the number a, b and c is GCD (a, b, c)
- The greatest number that divides the number a, b and c leaving remainder x, y, z is GCD (a-x, b-y, c-z)
- The greatest number that divides the number a, b and c leaving the same remainder in each case is GCD (a-b, b-c, c-a)
- The least number that exactly divisible the number a, b and c is LCM (a, b, c)
- The least number that exactly divisible the number a, b and c leaving same remainder ‘r’ in each case is LCM (a, b, c) + r
How to use CalculatorHut’s LCM and GCD calculator?
Enter the numbers separated by commas in the box and click Calculate to find out the GCD and LCM of the number. Our LCM and GCD calculator is very useful in finding out LCM and GCD for larger values and many numbers, where it is very difficult to find out manually.
You can also conveniently add our LCM and GCD calculator widget to your website and make calculations instantly. Just let us know your preferred customizations at [email protected], and we would design an attractive and colorful widget as per your taste. And all this is for FREE!!