HCF Using Prime Factorisation for CBSE Class 10 Mathematics

The Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD), of two or more positive integers is the largest positive integer that divides each of the given numbers without leaving a remainder. In Class 10 Mathematics, the prime factorisation method based on the Fundamental Theorem of Arithmetic provides the cleanest and most reliable way to determine the HCF of numbers and algebraic expressions.

What You Will Learn

• Conceptual definition and significance of HCF
• The fundamental rule of HCF using prime factorisation
• Step-by-step method to compute HCF of two and three numbers
• Finding HCF of algebraic expressions with variable exponents
• The product relationship: $\text{HCF}(a, b) \times \text{LCM}(a, b) = a \times b$
• Important tips and typical examination pitfalls

1. What is HCF?

For two positive integers $a$ and $b$, their common factors are the numbers that divide both $a$ and $b$. The greatest among these common factors is their Highest Common Factor (HCF).

Prime Factorisation Rule for HCF

HCF is the product of the smallest power of each common prime factor involved in the numbers.

$\text{HCF}(a, b) = \prod_{i} p_i^{\min(a_i, b_i)}$

Important: <u>Only include prime factors that appear in ALL given numbers. If a prime factor is not shared by all numbers, it must not be included in the HCF.</u>

2. Step-by-Step Procedure

To calculate the HCF of two or more numbers using prime factorisation:

1. Step 1: Express each number as a product of its prime factors in exponential (canonical) form.
2. Step 2: Identify the prime factors that are common to all numbers.
3. Step 3: For each common prime factor, select the smallest exponent (power) present in the factorisations.
4. Step 4: Multiply these common factors with their lowest exponents to get the HCF.

3. Solved Examples

Solved Example 1: Two Numbers

Problem: Find the HCF of $144$ and $180$ using the prime factorisation method.

Solution:

• Step 1: Find the prime factorisations: $144 = 2 \times 2 \times 2 \times 2 \times 3 \times 3 = 2^4 \times 3^2$ $180 = 2 \times 2 \times 3 \times 3 \times 5 = 2^2 \times 3^2 \times 5^1$
• Step 2: Identify the common prime factors: The prime factors appearing in both numbers are $2$ and $3$ (5 is not common).
• Step 3: Select the smallest power for each common factor:
  • For prime $2$: $\min(4, 2) = 2 \implies 2^2$
  • For prime $3$: $\min(2, 2) = 2 \implies 3^2$
• Step 4: Calculate HCF: $\text{HCF}(144, 180) = 2^2 \times 3^2 = 4 \times 9 = 36$

Solved Example 2: Three Numbers

Problem: Find the HCF of $72$, $126$, and $168$ using prime factorisation.

Solution:

• Prime factorise each number: $72 = 2^3 \times 3^2$ $126 = 2^1 \times 3^2 \times 7^1$ $168 = 2^3 \times 3^1 \times 7^1$
• Common prime factors across all three numbers: Only $2$ and $3$ are common to 72, 126, and 168 (7 is not a factor of 72).
• Smallest powers:
  • For $2$: $\min(3, 1, 3) = 1 \implies 2^1$
  • For $3$: $\min(2, 2, 1) = 1 \implies 3^1$
• Result: $\text{HCF}(72, 126, 168) = 2^1 \times 3^1 = 6$

Solved Example 3: Algebraic Variables (CBSE Board PYQ)

Problem: If two positive integers $a$ and $b$ are expressible in the form $a = x^3 y^2$ and $b = x y^3$, where $x$ and $y$ are prime numbers, find $\text{HCF}(a, b)$.

Solution:

• Prime factors of $a$: $x^3 \times y^2$
• Prime factors of $b$: $x^1 \times y^3$
• Both $x$ and $y$ are common prime factors.
• Select the minimum exponent for each factor:
  • For $x$: $\min(3, 1) = 1 \implies x^1$
  • For $y$: $\min(2, 3) = 2 \implies y^2$
• Thus: $\text{HCF}(a, b) = x^1 y^2 = x y^2$

4. Fundamental Relationship Between HCF and LCM

For any two positive integers $a$ and $b$: $\text{HCF}(a, b) \times \text{LCM}(a, b) = a \times b$

This means: $\text{HCF}(a, b) = \frac{a \times b}{\text{LCM}(a, b)}$

Warning: <u>This formula holds strictly for TWO numbers only. It is NOT valid for three or more numbers! That is: $\text{HCF}(a, b, c) \times \text{LCM}(a, b, c) \ne a \times b \times c$.</u>

5. Summary and Examination Tips

Remember: If two numbers have no common prime factors, their HCF is $1$, and the numbers are called co-prime.

Common Mistake: Including non-common factors in the HCF calculation. If a factor does not appear in every number, it has an effective exponent of $0$ in the missing number, so $\min(k, 0) = 0$.