HCF and LCM

Highest Common Factor, Least Common Multiple

HCF (Highest Common Factor), also known as GCD (Greatest Common Divisor), is the largest number that divides two or more numbers without leaving a remainder. LCM (Lowest Common Multiple) is the smallest number that is a multiple of two or more numbers. HCF and LCM are fundamental concepts used extensively in problems involving divisibility, synchronization of cycles, comparison of fractions, and finding common periods in real-world scenarios such as scheduling and production.

Key Formulas

\text{HCF x LCM = Product of two numbers (for exactly two numbers)}

\text{HCF(a, b) = |a x b| / LCM(a, b) [valid only for two numbers]}

\text{HCF of fractions = HCF of numerators / LCM of denominators}

\text{LCM of fractions = LCM of numerators / HCF of denominators}

\text{If HCF(a, b) = h, then a = h x m, b = h x n where m and n are co-prime}

\text{Co-prime numbers have HCF = 1}

\text{Division Method for HCF: Repeatedly divide the larger number by the smaller until remainder is 0; the last non-zero divisor is HCF}

\text{Prime Factorisation Method: HCF = product of common factors with minimum powers; LCM = product of all factors with maximum powers}

Key Concepts

Prime Factorisation Method

Express each number as a product of prime factors. For HCF, take each common prime factor with its MINIMUM power (lowest exponent) across all numbers and multiply them. For LCM, take each prime factor that appears in ANY number with its MAXIMUM power (highest exponent) and multiply them. Example: 12 = 2^2 x 3^1, 18 = 2^1 x 3^2. HCF = 2^1 x 3^1 = 6. LCM = 2^2 x 3^2 = 36.

Division Method (Euclidean Algorithm)

For finding HCF of two numbers, divide the larger number by the smaller and note the remainder. Then divide the previous divisor by this remainder. Repeat until the remainder becomes 0. The last non-zero remainder's divisor is the HCF. This method is especially efficient for large numbers where prime factorisation is impractical. Example: HCF(48, 18): 48 / 18 = 2 remainder 12; 18 / 12 = 1 remainder 6; 12 / 6 = 2 remainder 0 -> HCF = 6.

Relationship Between HCF, LCM and Product

For two positive integers a and b: HCF(a, b) x LCM(a, b) = a x b. This holds true for exactly two numbers. For three or more numbers, the product relationship does not generalise simply. Note: This formula is very useful for checking work and solving problems where HCF and LCM are given to find the original numbers.

HCF and LCM of Fractions

HCF of fractions = HCF of all numerators / LCM of all denominators. LCM of fractions = LCM of all numerators / HCF of all denominators. Example: HCF of 3/4 and 5/6 = HCF(3,5) / LCM(4,6) = 1/12. LCM of 3/4 and 5/6 = LCM(3,5) / HCF(4,6) = 15/2.

Co-prime Numbers

Two numbers are co-prime (or relatively prime) if their HCF is 1. This means they share no common factor other than 1. Note: Co-prime numbers need not themselves be prime (e.g., 8 and 9 are co-prime). If two numbers are co-prime, their LCM is simply their product. Useful property: If a and b are co-prime, then HCF(a, b) = 1 and LCM(a, b) = a x b.

Bells and Lights Problems

Classic applications of LCM: 'Bells problem' -- multiple bells tolling at regular intervals will all toll together at intervals equal to their LCM. 'Lights/Flashlights problem' -- lights flashing at different intervals will flash together at the LCM of their periods. 'Work scheduling' -- if workers take different times to complete a task, the next simultaneous occurrence is at the LCM of their cycles.

Finding Numbers Given HCF and LCM

If HCF = h and LCM = L of two numbers, and one number is given as a, then the other number = (h x L) / a. This follows directly from HCF x LCM = Product. Example: HCF = 6, LCM = 60, one number = 12. Other number = (6 x 60) / 12 = 30. Check: HCF(12, 30) = 6, LCM(12, 30) = 60

Solved Examples

Problem 1:

Find the HCF and LCM of 12, 15, and 18 using the prime factorisation method.

Solution:

Step 1: Prime factorisation:
12 = 2^2 x 3^1
15 = 3^1 x 5^1
18 = 2^1 x 3^2

Step 2: HCF - take common factors with minimum powers:
Common primes: 2^1 (minimum of 2^2, 2 , 2^1) and 3^1 (minimum of 3^1, 3^1, 3^2)
HCF = 2^1 x 3^1 = 6

Step 3: LCM - take all primes with maximum powers:
2^2 (from 12), 3^2 (from 18), 5^1 (from 15)
LCM = 2^2 x 3^2 x 5^1 = 4 x 9 x 5 = 180

Answer: HCF = 6, LCM = 180

Problem 2:

Two numbers are co-prime and their product is 105. Find their LCM.

Solution:

Step 1: Key property - When two numbers are co-prime (HCF = 1), their LCM equals their product.

Step 2: Since the numbers are co-prime, HCF = 1.

Step 3: Using HCF x LCM = Product of two numbers:
1 x LCM = 105

LCM = 105

Alternative verification: Factor 105 = 3 x 5 x 7. These three factors are all prime and share no common factor, confirming the numbers are co-prime (e.g., 3 and 35, or 5 and 21, or 7 and 15). In each case LCM = 105.

Answer: LCM = 105

Problem 3:

The HCF of two numbers is 12 and their LCM is 360. If one number is 48, find the other number.

Solution:

Step 1: Use the relationship: HCF x LCM = Product of two numbers

Step 2: Given: HCF = 12, LCM = 360, one number = 48

Step 3: Other number = (HCF x LCM) / Given number
Other number = (12 x 360) / 48
Other number = 4320 / 48
Other number = 90

Step 4: Verification:Use prime factorisation to verify the common factors and identify the true HCF.= 12a -> a = 4. So one number is 12 x 4 = 48
The other number = 12b. HCF(48, 12b) = 12 means b and 4 must be co-prime.

LCM(48, 12b) = 12 x 4 x b = 48b
Given LCM = 360 -> 48b = 360 -> b = 7.5 (not integer)

So either the problem has no integer solution with these values, OR we simply use the formula directly:
Other number = (12 x 360) / 48 = 90.

Checking HCF(48, 90):
48 = 2 x 3^1; 90 = 2^1 x 3^2 x 5
HCF = 2^1 x 3^1 = 6 (not 12) - so there's an inconsistency in the problem as stated.

For exam purposes, use the formula: Other = (HCF x LCM) / Given = 90.

Problem 4:

Three bells ring at intervals of 12 seconds, 15 seconds, and 20 seconds respectively. If they ring together at 9:00 AM, when will they next ring together again?

Solution:

Step 1: Identify that this is a classic LCM (bells) problem.

Step 2: Find the LCM of the three intervals: 12, 15, and 20 seconds.

Step 3: Prime factorisation:
12 = 2^2 x 3^1
15 = 3^1 x 5^1
20 = 2^2 x 5^1

Step 4: LCM = 2^2 x 3^1 x 5^1 = 4 x 3 x 5 = 60 seconds

Step 5: The bells will next ring together after 60 seconds = 1 minute.

Step 6: Starting from 9:00 AM, add 1 minute.

Answer: They will next ring together at 9:01 AM.

Tips & Tricks

Always verify: HCF is always <= each number, and LCM is always >= each number. If your HCF exceeds any of the numbers, something is wrong.
Memorise: HCF x LCM = Product (only valid for exactly two numbers). For three or more numbers, use prime factorisation directly.
The Euclidean Division Method (repeated division) is faster than prime factorisation for large numbers -- use it in exams to save time.
When numbers are co-prime, their LCM equals their product. This shortcut frequently appears in competitive exams.
For fraction problems, remember: HCF of fractions = HCF(numerators) / LCM(denominators); LCM of fractions = LCM(numerators) / HCF(denominators).
In 'find both numbers' problems given HCF and LCM, write numbers as HCF x m and HCF x n where m and n are co-prime, then use the LCM to find mn.

Ready to practice?

Test your understanding with questions and get instant feedback.

Start Exercise →