How do we directly find the HCF without listing all the factors?

Question

Homi · Accepted Answer

Understand the Question

We can directly find the Highest Common Factor (HCF) of numbers without listing all their factors by using the Prime Factorization Method.
Steps of the method:
1. Express each number as a product of its prime factors in exponential form.
2. Identify the common prime factors shared by all the numbers.
3. Find the lowest power (smallest exponent) for each common prime factor.
4. Multiply these powers together to get the HCF.

Step 1 · Find Prime Factorization of the Numbers

To illustrate the method, find the HCF of $60$ and $84$ . Diagram 1

Prime factors of $60$ :

\begin{aligned} 60 \div 2 &= 30 \\ 30 \div 2 &= 15 \\ 15 \div 3 &= 5 \\ 5 \div 5 &= 1 \end{aligned}

$60 = 2 \times 2 \times 3 \times 5 = 2^2 \times 3^1 \times 5^1$

Prime factors of $84$ :

\begin{aligned} 84 \div 2 &= 42 \\ 42 \div 2 &= 21 \\ 21 \div 3 &= 7 \\ 7 \div 7 &= 1 \end{aligned}

$84 = 2 \times 2 \times 3 \times 7 = 2^2 \times 3^1 \times 7^1$

Step 2 · Identify Common Prime Factors and Calculate HCF

Compare the prime factorizations:

Common prime factors are $2$ and $3$ .
Lowest power of $2$ is $2^2$ .
Lowest power of $3$ is $3^1$ .

Multiply the common prime factors with their lowest powers:

\begin{aligned} \text{HCF} &= 2^2 \times 3^1 \\ &= (2 \times 2) \times 3 \\ &= 4 \times 3 \\ &= 12 \end{aligned}

Answer

By using the prime factorization method: find the prime factors of the numbers and multiply the common prime factors taken with their lowest powers.

Common Mistakes

Power Confusion (HCF vs. LCM): Selecting the highest power instead of the lowest power for common prime factors (highest powers give the LCM, not the HCF).
Including Non-Common Factors: Multiplying factors that only appear in one number (e.g., $5$ or $7$ ) instead of only common factors.

Question 3

More questions in FIO