HCF and LCM Using Prime Factorisation
Finding the Highest Common Factor (HCF) and Least Common Multiple (LCM) using prime factorisation is a systematic method taught in CBSE Class 10 (Chapter 1: Real Numbers).
This method is grounded in the Fundamental Theorem of Arithmetic and works for any set of numbers, no matter how large.
Where HCF and LCM are used:
- Finding the largest tile size for a floor
- Determining when two events will coincide
- Simplifying fractions to lowest terms
- Solving ratio and proportion problems
What is HCF & LCM by Prime Factorisation?
Definition: The HCF (Highest Common Factor), also called GCD, of two or more positive integers is the largest positive integer that divides each of them without leaving a remainder.
Example: Factors of 18 = {1, 2, 3, 6, 9, 18}. Factors of 24 = {1, 2, 3, 4, 6, 8, 12, 24}. Common factors = {1, 2, 3, 6}. HCF(18, 24) = 6.
Definition: The LCM (Least Common Multiple) of two or more positive integers is the smallest positive integer that is divisible by each of them.
Example: Multiples of 4 = {4, 8, 12, 16, 20, 24, ...}. Multiples of 6 = {6, 12, 18, 24, ...}. Common multiples = {12, 24, 36, ...}. LCM(4, 6) = 12.
- Write each number as a product of prime powers: n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ.
- HCF = Product of common prime factors, each raised to its smallest power.
- LCM = Product of all prime factors, each raised to its greatest power.
Key relationship:
HCF(a, b) × LCM(a, b) = a × b
Important: This formula applies directly only to two numbers. For three or more, use the prime factorisation method.
HCF and LCM Using Prime Factorisation Formula
Formulas for HCF and LCM:
HCF formula:
HCF(a, b) = p₁min(α₁, β₁) × p₂min(α₂, β₂) × ...
(only primes appearing in BOTH numbers)
LCM formula:
LCM(a, b) = p₁max(α₁, β₁) × p₂max(α₂, β₂) × ...
(ALL primes from EITHER number)
Additional formulas:
- Product relationship: HCF(a, b) × LCM(a, b) = a × b
- Finding LCM from HCF: LCM(a, b) = (a × b) / HCF(a, b)
- Finding HCF from LCM: HCF(a, b) = (a × b) / LCM(a, b)
- For three numbers: LCM(a, b, c) = LCM(LCM(a, b), c). Similarly for HCF.
- Coprime check: If HCF(a, b) = 1, then LCM(a, b) = a × b.
Quick reference:
| Step | HCF | LCM |
|---|---|---|
| 1. Factorise into primes | Same | Same |
| 2. Identify prime factors | Only COMMON primes | ALL primes |
| 3. Choose power | SMALLEST power | GREATEST power |
| 4. Multiply | = HCF | = LCM |
Derivation and Proof
Why does the prime factorisation method work?
The correctness follows from the Fundamental Theorem of Arithmetic and the definitions of HCF and LCM.
Setup: Let a = p₁^α₁ × ... × pₖ^αₖ and b = p₁^β₁ × ... × pₖ^βₖ (using exponent 0 for absent primes).
Proof for HCF:
- A common divisor d of a and b has d = p₁^γ₁ × ... where γ₤ ≤ α₤ and γ₤ ≤ β₤.
- So γ₤ ≤ min(α₤, β₤) for each i.
- The largest d is obtained when γ₤ = min(α₤, β₤) for every i.
- This gives HCF = p₁^min(α₁,β₁) × ... × pₖ^min(αₖ,βₖ).
Proof for LCM:
- A common multiple m of a and b must have δ₤ ≥ α₤ and δ₤ ≥ β₤.
- So δ₤ ≥ max(α₤, β₤) for each i.
- The smallest m is when δ₤ = max(α₤, β₤) for every i.
Proof of HCF × LCM = a × b:
- HCF × LCM = p₁^(min + max) × ...
- For any x, y: min(x, y) + max(x, y) = x + y.
- So HCF × LCM = p₁^(α₁ + β₁) × ... = a × b.
Types and Properties
Types of HCF and LCM problems:
Type 1: Direct computation
Given two or three numbers, find HCF and LCM using prime factorisation.
Type 2: Using the product relationship
Given HCF and one number, find LCM (or vice versa) using HCF × LCM = a × b.
Type 3: Verification problems
Compute HCF and LCM, then verify using the product formula.
Type 4: Word problems — HCF (division/grouping)
Keywords: "largest", "maximum", "greatest", "divide equally", "cut into equal pieces".
- Largest square tile to cover a rectangular floor
- Maximum students in equal rows
- Greatest length of rope that measures given lengths exactly
Type 5: Word problems — LCM (timing/coincidence)
Keywords: "minimum", "smallest", "least", "together again", "coincide".
- When will two bells ring together again?
- Minimum items to distribute equally
- Smallest number divisible by given numbers
Type 6: Finding missing numbers
Given HCF, LCM, and one number, find the other.
Type 7: Three-number problems
The product relationship does NOT apply to three numbers. Compute stepwise: HCF(a, b, c) = HCF(HCF(a, b), c).
HCF vs LCM — Quick comparison:
| Feature | HCF Problem | LCM Problem |
|---|---|---|
| Goal | Largest common divisor | Smallest common multiple |
| Result vs inputs | HCF ≤ smallest input | LCM ≥ largest input |
| Real-world analogy | Cutting/dividing equally | Scheduling/synchronising |
| For coprime numbers | HCF = 1 | LCM = product |
Solved Examples
Example 1: Basic HCF and LCM of two numbers
Problem: Find the HCF and LCM of 336 and 54 by prime factorisation.
Solution:
Prime factorisations:
- 336 = 2⁴ × 3 × 7
- 54 = 2 × 3³
HCF: Common primes: 2 and 3. Smallest powers: 2¹ and 3¹. HCF = 2 × 3 = 6.
LCM: All primes: 2, 3, 7. Greatest powers: 2⁴, 3³, 7¹. LCM = 16 × 27 × 7 = 3024.
Verification: HCF × LCM = 6 × 3024 = 18144. Product = 336 × 54 = 18144. ✓
Answer: HCF = 6, LCM = 3024.
Example 2: HCF and LCM of three numbers
Problem: Find HCF and LCM of 18, 45, and 60 using prime factorisation.
Solution:
Prime factorisations:
- 18 = 2 × 3²
- 45 = 3² × 5
- 60 = 2² × 3 × 5
HCF: Only 3 is common to all three. Smallest power: 3¹. HCF = 3.
LCM: All primes {2, 3, 5} with greatest powers: 2², 3², 5¹. LCM = 4 × 9 × 5 = 180.
Verification: 180/18 = 10 ✓, 180/45 = 4 ✓, 180/60 = 3 ✓.
Answer: HCF = 3, LCM = 180.
Example 3: Using the product relationship to find LCM
Problem: The HCF of two numbers is 18 and one number is 360. If the LCM is 7560, find the other number.
Solution:
Using: HCF(a, b) × LCM(a, b) = a × b
- 18 × 7560 = 360 × b
- b = (18 × 7560) / 360 = 135720 / 360 = 378
Verification: 360 = 2³ × 3² × 5 and 378 = 2 × 3³ × 7. HCF = 2 × 3² = 18 ✓. LCM = 2³ × 3³ × 5 × 7 = 7560 ✓.
Answer: The other number is 378.
Example 4: Word problem — Largest square tile (HCF application)
Problem: A courtyard measures 18 m by 15 m. It is to be paved with square tiles of the largest possible size. Find the tile size and number of tiles needed.
Solution:
Given:
- Tile side must divide both 18 and 15
- Largest tile side = HCF(18, 15)
Finding HCF:
- 18 = 2 × 3² and 15 = 3 × 5
- Common factor: 3. Smallest power: 3¹. HCF = 3
Number of tiles:
- Along length: 18/3 = 6
- Along breadth: 15/3 = 5
- Total = 6 × 5 = 30
Answer: Tile side = 3 m, number of tiles = 30.
Example 5: Word problem — Traffic lights (LCM application)
Problem: Three traffic lights change every 48 seconds, 72 seconds, and 108 seconds. If they all change simultaneously at 7:00:00 AM, when do they next change together?
Solution:
Given: Find LCM(48, 72, 108).
Prime factorisations:
- 48 = 2⁴ × 3
- 72 = 2³ × 3²
- 108 = 2² × 3³
LCM: 2⁴ × 3³ = 16 × 27 = 432 seconds
- 432 seconds = 7 minutes 12 seconds
- 7:00:00 AM + 7 min 12 sec = 7:07:12 AM
Answer: They next change simultaneously at 7:07:12 AM.
Example 6: Finding the greatest length of rope (HCF word problem)
Problem: Three ropes of 630 cm, 735 cm, and 945 cm are to be cut into pieces of equal length. Find the greatest possible length and number of pieces from each rope.
Solution:
Given: Maximum piece length = HCF(630, 735, 945).
Prime factorisations:
- 630 = 2 × 3² × 5 × 7
- 735 = 3 × 5 × 7²
- 945 = 3³ × 5 × 7
HCF: Common primes: 3, 5, 7. Smallest powers: 3¹, 5¹, 7¹. HCF = 3 × 5 × 7 = 105 cm.
Pieces:
- Rope 1: 630/105 = 6
- Rope 2: 735/105 = 7
- Rope 3: 945/105 = 9
- Total = 22 pieces
Answer: Greatest piece length = 105 cm. Pieces: 6, 7, and 9 (22 total).
Example 7: Finding the smallest number with given divisors
Problem: Find the smallest 4-digit number exactly divisible by 12, 18, and 27.
Solution:
Step 1: Find LCM(12, 18, 27).
- 12 = 2² × 3
- 18 = 2 × 3²
- 27 = 3³
LCM: 2² × 3³ = 4 × 27 = 108
Step 2: Smallest 4-digit number = 1000. Find smallest multiple of 108 ≥ 1000.
- 1000 ÷ 108 = 9.259... → Take 10th multiple
- 108 × 10 = 1080
Verification: 1080/12 = 90 ✓, 1080/18 = 60 ✓, 1080/27 = 40 ✓.
Answer: The smallest 4-digit number is 1080.
Example 8: Coprime numbers and their HCF/LCM
Problem: Show that 385 and 432 are coprime and find their LCM.
Solution:
Prime factorisations:
- 385 = 5 × 7 × 11
- 432 = 2⁴ × 3³
Finding HCF:
- No common prime factors → HCF(385, 432) = 1
- They are coprime
LCM: Since they are coprime, LCM = 385 × 432 = 166320.
Answer: 385 and 432 are coprime. HCF = 1, LCM = 166320.
Example 9: Circular track problem (LCM application)
Problem: Two runners start together on a circular track. Runner A completes a lap in 126 seconds, Runner B in 154 seconds. After how many seconds will they be at the starting point together again?
Solution:
Given: They meet at the start after LCM(126, 154) seconds.
Prime factorisations:
- 126 = 2 × 3² × 7
- 154 = 2 × 7 × 11
LCM: 2 × 3² × 7 × 11 = 2 × 9 × 7 × 11 = 1386 seconds
- 1386 seconds = 23 minutes 6 seconds
Answer: They meet at the starting point after 1386 seconds (23 min 6 sec).
Example 10: Challenging problem — Remainder-based HCF
Problem: Find the largest number that divides 2053 and 967, leaving remainders 5 and 7 respectively.
Solution:
Given:
- The number divides (2053 − 5) = 2048 and (967 − 7) = 960 exactly
- Required answer = HCF(2048, 960)
Prime factorisations:
- 2048 = 2¹¹
- 960 = 2⁶ × 3 × 5
HCF: Common prime: only 2. Smallest power: 2⁶ = 64.
Verification: 2053 = 64 × 32 + 5 ✓. 967 = 64 × 15 + 7 ✓.
Answer: The largest such number is 64.
Real-World Applications
Real-world applications of HCF and LCM:
- Construction and Tiling: Finding the largest square tile that fits a rectangular floor. Example: room 4.2 m × 3.6 m needs tiles of side HCF(420, 360) = 60 cm.
- Scheduling and Planning: LCM determines when periodic events coincide. Three machines serviced every 6, 10, and 15 days are all serviced on the same day every LCM(6, 10, 15) = 30 days.
- Music and Rhythm: Polyrhythms (patterns of different lengths) coincide at intervals given by the LCM of pattern lengths.
- Gear Systems: A gear with 24 teeth and one with 36 teeth return to starting alignment every LCM(24, 36) = 72 tooth rotations.
- Fraction Arithmetic: Finding the LCD (Least Common Denominator) for adding fractions is an LCM problem. To add 1/12 + 1/18, LCD = LCM(12, 18) = 36.
- Packaging and Distribution: HCF determines the largest group size for equal distribution. LCM determines the smallest common quantity.
Key Points to Remember
- HCF = product of smallest powers of COMMON prime factors only.
- LCM = product of greatest powers of ALL prime factors.
- HCF(a, b) × LCM(a, b) = a × b. Works for exactly two numbers.
- HCF is always ≤ the smaller number. LCM is always ≥ the larger number.
- If HCF(a, b) = 1, then a and b are coprime, and LCM(a, b) = a × b.
- For three numbers: HCF(a, b, c) = HCF(HCF(a, b), c). Same for LCM.
- HCF problems use keywords: "largest", "maximum", "divide equally".
- LCM problems use keywords: "smallest", "minimum", "together again".
- For remainder-based problems: subtract remainders from each number, then find HCF.
- This topic carries 2–4 marks in CBSE board exams.
Practice Problems
- Find the HCF and LCM of 504 and 980 using prime factorisation. Verify using the product relationship.
- Find the HCF and LCM of 30, 72, and 432 by prime factorisation method.
- The HCF of two numbers is 23 and their LCM is 1449. If one of the numbers is 161, find the other.
- Find the smallest number which, when divided by 35, 56, and 91, leaves a remainder of 7 in each case.
- In a seminar, the number of participants from three schools are 60, 84, and 108. Find the minimum number of rooms required if each room must have the same number of participants, all from the same school.
- Two neon signs are turned on at the same time. One blinks every 16 seconds and the other every 24 seconds. In 480 seconds, how many times do both blink together (excluding the starting moment)?
- If HCF(252, 378) = 126, find LCM(252, 378) without prime factorisation.
- Find the largest number that divides 70 and 125, leaving remainders 5 and 8 respectively.
Frequently Asked Questions
Q1. How to find HCF and LCM by prime factorisation method?
Write each number as a product of prime powers. For HCF, take the smallest powers of common primes and multiply. For LCM, take the greatest powers of all primes and multiply. Example: 48 = 2&sup4; × 3 and 60 = 2² × 3 × 5. HCF = 2² × 3 = 12. LCM = 2&sup4; × 3 × 5 = 240.
Q2. What is the relationship between HCF and LCM of two numbers?
For any two positive integers a and b: HCF(a, b) × LCM(a, b) = a × b. You can find LCM if you know HCF (and vice versa) using LCM = (a × b) / HCF. This holds only for two numbers, not three or more.
Q3. What is the difference between HCF and LCM?
HCF is the largest number that divides both given numbers. LCM is the smallest number that both given numbers divide into. HCF ≤ the smaller number; LCM ≥ the larger number. HCF deals with dividing equally; LCM deals with common timings or multiples.
Q4. Does the formula HCF times LCM equals product work for three numbers?
No. HCF(a, b) × LCM(a, b) = a × b works only for two numbers. For three numbers, compute stepwise: HCF(a, b, c) = HCF(HCF(a, b), c) and LCM(a, b, c) = LCM(LCM(a, b), c).
Q5. How do you know when to use HCF vs LCM in a word problem?
Use HCF when the problem asks for the largest, greatest, or maximum common divisor (e.g., largest tile size, maximum equal rows, greatest common measurement). Use LCM when it asks for the smallest, least, or minimum common multiple (e.g., when events coincide, smallest number divisible by all).
Q6. What is the HCF of two coprime numbers?
The HCF of two coprime numbers is 1. Coprime numbers share no common prime factor. Examples: (8, 15), (17, 31), any two consecutive integers like (14, 15). When HCF = 1, LCM equals the product of the two numbers.
Q7. Can HCF of two numbers be equal to one of the numbers?
Yes, when one number divides the other. Example: HCF(12, 36) = 12 because 12 divides 36. In this case, HCF = the smaller number and LCM = the larger number.
Q8. How to find HCF and LCM of large numbers quickly?
Use the repeated division method: divide each number by the smallest prime (2, then 3, then 5...) until reaching 1. Write as prime powers. Apply HCF/LCM rules. For very large numbers, Euclid's Algorithm may be faster for HCF alone.
Q9. What is the HCF and LCM of two consecutive numbers?
For consecutive integers n and n+1: HCF = 1 (always coprime). LCM = n × (n+1). Example: HCF(99, 100) = 1 and LCM(99, 100) = 9900.
Q10. How are HCF and LCM used in real life?
HCF is used for cutting or dividing equally (largest tile, equal pieces, equal distribution). LCM is used for synchronising events (bus schedules, flashing lights, repeating patterns). Both are used in fraction arithmetic — the LCD for adding fractions is the LCM of denominators.
