Highest Common Factor (HCF)

TL;DR

The Highest Common Factor (HCF) is the largest number that divides exactly into two or more numbers. You can find it by listing factors or using prime factorization, which is more efficient for larger numbers. HCF is useful for simplifying fractions or dividing things into equal-sized groups.

1. The Mental Model

Think of HCF as the biggest "shared building block" for a set of numbers. If you have two numbers, HCF is the largest number that can perfectly measure both of them without anything left over. It's about finding common divisors and picking the largest one.

2. The Core Material

The Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD), is the largest positive integer that divides two or more integers without leaving a remainder. Let's look at how to find it.

Listing Factors Method

Photo by Markus Winkler on Pexels

This method is good for smaller numbers. You just list all the factors for each number and then pick the largest one that appears in both lists.

Example: Find the HCF of 12 and 18.
* Factors of 12: 1, 2, 3, 4, 6, 12
* Factors of 18: 1, 2, 3, 6, 9, 18
* Common factors: 1, 2, 3, 6
* The highest common factor is 6.

Prime Factorization Method

Photo by Black ice on Pexels

This method is generally more efficient, especially for larger numbers. You break each number down into its prime factors, then identify the common prime factors and multiply them together.

Steps:
1. Find the prime factorization of each number.
2. Identify all prime factors that are common to all numbers.
3. For each common prime factor, take the lowest power it appears in any of the factorizations.
4. Multiply these common prime factors (at their lowest powers) together.

graph TD
    A["Start: Get Numbers"] --> B["Prime Factorize Number 1"];
    B --> C["Prime Factorize Number 2"];
    C --> D{"Are there more numbers?"};
    D -- "Yes" --> C;
    D -- "No" --> E["Identify Common Prime Factors"];
    E --> F["For each common prime, find its lowest power"];
    F --> G["Multiply these common prime factors (with lowest powers)"];
    G --> H["Result: HCF"];

Example: Find the HCF of 24 and 36.
* Prime factorization of 24: $2 \times 2 \times 2 \times 3 = 2^3 \times 3^1$
* Prime factorization of 36: $2 \times 2 \times 3 \times 3 = 2^2 \times 3^2$

• Common prime factors are 2 and 3.
• Lowest power of 2: $2^2$ (from 36)
• Lowest power of 3: $3^1$ (from 24)
• HCF = $2^2 \times 3^1 = 4 \times 3 = 12$

Applications of HCF

Photo by Roshan Ravi on Pexels

HCF isn't just a math exercise; it has practical uses:

• Simplifying Fractions: To simplify a fraction like $\frac{12}{18}$, you find the HCF of the numerator and denominator (which is 6) and divide both by it: $\frac{12 \div 6}{18 \div 6} = \frac{2}{3}$.
• Dividing into Equal Groups: If you have 24 apples and 36 oranges and want to divide them into the largest possible equal groups, with no fruit left over and each group having the same number of apples and same number of oranges, you'd find the HCF of 24 and 36 (which is 12). This means you can make 12 groups, with 2 apples and 3 oranges in each.

3. Worked Example

Let's find the HCF of 60, 90, and 120 using the prime factorization method.

1. Prime Factorize 60:
   $60 = 2 \times 30$
   $30 = 2 \times 15$
   $15 = 3 \times 5$
   So, $60 = 2 \times 2 \times 3 \times 5 = 2^2 \times 3^1 \times 5^1$

2. Prime Factorize 90:
   $90 = 2 \times 45$
   $45 = 3 \times 15$
   $15 = 3 \times 5$
   So, $90 = 2 \times 3 \times 3 \times 5 = 2^1 \times 3^2 \times 5^1$

3. Prime Factorize 120:
   $120 = 2 \times 60$
   $60 = 2 \times 30$
   $30 = 2 \times 15$
   $15 = 3 \times 5$
   So, $120 = 2 \times 2 \times 2 \times 3 \times 5 = 2^3 \times 3^1 \times 5^1$

4. Identify Common Prime Factors and Lowest Powers:

   • Common prime factor 2: The lowest power is $2^1$ (from 90).
   • Common prime factor 3: The lowest power is $3^1$ (from 60 and 120).
   • Common prime factor 5: The lowest power is $5^1$ (from all three).

5. Multiply them:
   HCF = $2^1 \times 3^1 \times 5^1 = 2 \times 3 \times 5 = 30$

The HCF of 60, 90, and 120 is 30.

4. Key Takeaways

• HCF is the largest number that divides evenly into all numbers in a set.
• The listing factors method is simple but gets tricky with larger numbers.
• Prime factorization is the most reliable method for finding HCF for any size numbers.
• To use prime factorization, break each number down, find common primes, and use their lowest powers.
• HCF helps simplify fractions to their simplest form.
• HCF is useful for dividing groups or quantities into the largest possible equal parts.

Common Mistakes to Avoid:
- Don't confuse HCF with LCM (Lowest Common Multiple); they're related but different.
- When using prime factorization, remember to use the lowest power for each common prime factor, not the highest.
- Forgetting to include a common prime factor in your final HCF calculation.
- Thinking that if numbers don't share any prime factors, their HCF is 0 (it's 1).

5. Now Try It

You're organizing a party and have 48 mini sandwiches and 72 mini pizzas. You want to arrange them on platters so that each platter has the exact same number of sandwiches and the exact same number of pizzas, and you want to use the largest possible number of platters.

1. What's the maximum number of platters you can use?
2. How many mini sandwiches and mini pizzas will be on each platter?

Success means you've correctly identified the HCF of 48 and 72, and then used that HCF to determine the number of items per platter.