HCF by Prime Factorisation
The HCF (Highest Common Factor) of two or more numbers is the largest number that divides all of them exactly. It is also called the GCD (Greatest Common Divisor).
In Class 5, students learn to find the HCF using the prime factorisation method. This method is systematic and works well for any pair of numbers.
For example, the HCF of 12 and 18 is 6, because 6 is the largest number that divides both 12 and 18 without a remainder.
What is HCF by Prime Factorisation - Class 5 Maths (Factors and Multiples)?
HCF (Highest Common Factor): The greatest number that is a factor of two or more given numbers.
Finding HCF by prime factorisation:
- Find the prime factorisation of each number.
- Identify the common prime factors.
- For each common prime factor, take the one with the smaller (or equal) power.
- Multiply these together. The product is the HCF.
HCF = Product of common prime factors with the lowest powers
Important properties of HCF:
- HCF of two numbers is always less than or equal to the smaller number.
- If one number is a factor of another, the HCF is the smaller number.
- HCF of two co-prime numbers is 1 (they share no common factor except 1).
- HCF of a number and itself is the number: HCF(15, 15) = 15.
HCF by Prime Factorisation Formula
HCF = Product of common prime factors (each raised to the lowest power)
Useful relationship:
HCF(a, b) x LCM(a, b) = a x b
This means if you know the HCF and one of the numbers, you can find the LCM, and vice versa.
Types and Properties
Step-by-step method:
Example: Find HCF of 48 and 36
| Step | 48 | 36 |
|---|---|---|
| Prime factorisation | 2 x 2 x 2 x 2 x 3 | 2 x 2 x 3 x 3 |
| With exponents | 2⁴ x 3¹ | 2² x 3² |
| Common factors | 2 (appears in both) and 3 (appears in both) | |
| Lowest power | 2² (lower of 2⁴ and 2²) and 3¹ (lower of 3¹ and 3²) | |
| HCF | 2² x 3 = 4 x 3 = 12 | |
Other methods to find HCF (for reference):
- Listing factors: Write all factors of each number and find the largest common one. Works for small numbers.
- Long division (Euclid's method): Divide the larger number by the smaller, then divide the divisor by the remainder, repeat until remainder is 0. The last divisor is the HCF.
Solved Examples
Example 1: Example 1: HCF of Two Numbers
Problem: Find the HCF of 24 and 36.
Solution:
Step 1: Prime factorisation of 24 = 2 x 2 x 2 x 3 = 2³ x 3
Step 2: Prime factorisation of 36 = 2 x 2 x 3 x 3 = 2² x 3²
Step 3: Common prime factors: 2 and 3
Step 4: Lowest powers: 2² and 3¹
Step 5: HCF = 2² x 3 = 4 x 3 = 12
Answer: HCF of 24 and 36 = 12
Example 2: Example 2: HCF of Larger Numbers
Problem: Find the HCF of 72 and 120.
Solution:
Step 1: 72 = 2 x 2 x 2 x 3 x 3 = 2³ x 3²
Step 2: 120 = 2 x 2 x 2 x 3 x 5 = 2³ x 3 x 5
Step 3: Common factors: 2 and 3
Step 4: Lowest powers: 2³ and 3¹
Step 5: HCF = 2³ x 3 = 8 x 3 = 24
Answer: HCF of 72 and 120 = 24
Example 3: Example 3: HCF of Three Numbers
Problem: Find the HCF of 36, 48, and 60.
Solution:
Step 1: 36 = 2² x 3²
Step 2: 48 = 2⁴ x 3
Step 3: 60 = 2² x 3 x 5
Step 4: Common factors in all three: 2 and 3
Step 5: Lowest powers: 2² (smallest of 2², 2⁴, 2²) and 3¹ (smallest of 3², 3¹, 3¹)
Step 6: HCF = 2² x 3 = 4 x 3 = 12
Answer: HCF of 36, 48, and 60 = 12
Example 4: Example 4: Co-Prime Numbers
Problem: Find the HCF of 35 and 24.
Solution:
Step 1: 35 = 5 x 7
Step 2: 24 = 2 x 2 x 2 x 3 = 2³ x 3
Step 3: No common prime factors.
Step 4: HCF = 1
Answer: HCF of 35 and 24 = 1 (they are co-prime)
Example 5: Example 5: When One Number is a Factor of the Other
Problem: Find the HCF of 16 and 64.
Solution:
Step 1: 16 = 2⁴
Step 2: 64 = 2⁶
Step 3: Common factor: 2. Lowest power: 2⁴
Step 4: HCF = 2⁴ = 16
Answer: HCF of 16 and 64 = 16 (since 16 is a factor of 64, the HCF is 16 itself)
Example 6: Example 6: Word Problem — Cutting Ribbon
Problem: Aditi has two ribbons of lengths 48 cm and 64 cm. She wants to cut them into pieces of equal length with no ribbon left over. What is the greatest possible length of each piece?
Solution:
Step 1: The greatest length is the HCF of 48 and 64.
Step 2: 48 = 2⁴ x 3
Step 3: 64 = 2⁶
Step 4: Common factor: 2. Lowest power: 2⁴ = 16
Answer: The greatest possible length of each piece is 16 cm.
Example 7: Example 7: Word Problem — Distributing Items
Problem: Rahul has 84 mangoes and 60 oranges. He wants to pack them into baskets so that each basket has the same number of mangoes and the same number of oranges, with no fruit left over. What is the maximum number of baskets?
Solution:
Step 1: Maximum baskets = HCF of 84 and 60
Step 2: 84 = 2² x 3 x 7
Step 3: 60 = 2² x 3 x 5
Step 4: Common factors: 2² and 3
Step 5: HCF = 4 x 3 = 12
Step 6: Each basket: 84/12 = 7 mangoes and 60/12 = 5 oranges
Answer: Maximum 12 baskets, each with 7 mangoes and 5 oranges.
Example 8: Example 8: Word Problem — Tiling
Problem: A room is 90 cm long and 60 cm wide. What is the largest square tile that can cover the floor without cutting?
Solution:
Step 1: Tile side = HCF of 90 and 60
Step 2: 90 = 2 x 3² x 5
Step 3: 60 = 2² x 3 x 5
Step 4: Common factors: 2¹, 3¹, 5¹
Step 5: HCF = 2 x 3 x 5 = 30
Answer: The largest square tile is 30 cm x 30 cm.
Example 9: Example 9: Using HCF to Simplify a Fraction
Problem: Simplify the fraction 84/120 to its lowest terms.
Solution:
Step 1: Find HCF of 84 and 120
Step 2: 84 = 2² x 3 x 7
Step 3: 120 = 2³ x 3 x 5
Step 4: HCF = 2² x 3 = 12
Step 5: Divide both by 12: 84/12 = 7, 120/12 = 10
Answer: 84/120 simplified = 7/10
Example 10: Example 10: HCF and LCM Relationship
Problem: The HCF of two numbers is 6 and their LCM is 180. If one number is 36, find the other.
Solution:
Step 1: Use the formula: HCF x LCM = Product of the two numbers
Step 2: 6 x 180 = 36 x other number
Step 3: 1,080 = 36 x other number
Step 4: Other number = 1,080 / 36 = 30
Answer: The other number is 30.
Real-World Applications
Real-life uses of HCF:
- Cutting and dividing: Finding the largest equal pieces when cutting ribbons, ropes, or cloth of different lengths.
- Packing: Distributing different items into the maximum number of identical groups.
- Tiling: Finding the largest square tile to cover a rectangular floor without cutting.
- Simplifying fractions: Dividing numerator and denominator by their HCF gives the simplest form.
- Scheduling: Combined with LCM, HCF helps solve problems about time intervals and grouping.
Key Points to Remember
- HCF = Highest Common Factor = largest number that divides two or more numbers exactly.
- To find HCF by prime factorisation: take common prime factors with the lowest powers.
- HCF is always less than or equal to the smallest of the given numbers.
- If two numbers are co-prime, their HCF is 1.
- If one number is a factor of another, the HCF is the smaller number.
- HCF x LCM = Product of the two numbers (for any two numbers).
- HCF is used to simplify fractions to their lowest terms.
Practice Problems
- Find the HCF of 42 and 56 using prime factorisation.
- Find the HCF of 108 and 144.
- Find the HCF of 24, 36, and 54.
- Are 51 and 68 co-prime? Find their HCF.
- Two ropes are 120 cm and 96 cm long. What is the greatest length of equal pieces they can be cut into?
- Simplify the fraction 72/108 using HCF.
- The HCF of two numbers is 8 and their LCM is 120. If one number is 24, find the other.
- A farmer has 252 apples and 168 oranges. He packs them into boxes with equal numbers of each fruit. What is the maximum number of boxes?
Frequently Asked Questions
Q1. What is HCF?
HCF stands for Highest Common Factor. It is the largest number that exactly divides two or more given numbers. For example, the HCF of 18 and 24 is 6 because 6 is the biggest number that divides both 18 and 24.
Q2. How do you find HCF using prime factorisation?
First, find the prime factorisation of each number. Then identify the prime factors common to all numbers. For each common factor, take the lowest power. Multiply these together to get the HCF.
Q3. What are co-prime numbers?
Co-prime numbers (or relatively prime numbers) are pairs of numbers whose HCF is 1. They share no common factor other than 1. Examples: (8, 15), (9, 28), (7, 11). Note: co-prime numbers do not have to be prime themselves.
Q4. Can the HCF be larger than the smaller number?
No. The HCF is always less than or equal to the smaller of the given numbers. If one number is a factor of the other, the HCF equals the smaller number. Otherwise, the HCF is smaller than both.
Q5. What is the relationship between HCF and LCM?
For any two numbers a and b: HCF(a, b) x LCM(a, b) = a x b. This means if you know the HCF and one number, you can find the LCM, and vice versa.
Q6. How is HCF used in simplifying fractions?
To simplify a fraction to its lowest terms, divide both the numerator and denominator by their HCF. For example, 36/48: HCF of 36 and 48 is 12. So 36/12 = 3 and 48/12 = 4. The simplified fraction is 3/4.
Q7. What is the HCF of two consecutive numbers?
The HCF of any two consecutive numbers is always 1. Consecutive numbers (like 14 and 15, or 99 and 100) are always co-prime because they share no common factor except 1.
Q8. Is there a quick way to find HCF without prime factorisation?
Yes, the long division method (Euclid's algorithm) is often faster for large numbers. Divide the larger number by the smaller, then divide the divisor by the remainder, and repeat until the remainder is 0. The last non-zero divisor is the HCF.
Q9. Can HCF be found for more than two numbers?
Yes. Find the prime factorisation of all numbers, then identify the prime factors common to ALL of them. Take the lowest power of each and multiply. Or, find HCF of the first two, then find HCF of that result with the third number.
Q10. What is the HCF of a number and zero?
The HCF of any number n and 0 is n itself. This is because 0 is a multiple of every number, so every factor of n is also a factor of 0. The largest of these is n.
