Highest Common Factor (HCF) - Methods and Applications

TL;DR

The Highest Common Factor (HCF) is the largest number that divides exactly into two or more numbers without leaving a remainder. You can find the HCF using prime factorization or by listing factors. HCF is super useful for simplifying fractions and solving real-world sharing problems.

1. The Mental Model

Think of HCF as finding the "biggest shared building block" between numbers. If you have two stacks of LEGO bricks, the HCF is the largest size of brick you could use to build both stacks perfectly without any leftover pieces.

2. The Core Material

The Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD), is the biggest number that divides into two or more numbers evenly. Let's look at how to find it.

2.1 Method 1: Listing Factors

Photo by Markus Winkler on Pexels

This is straightforward for smaller numbers. You list all factors for each number and then pick the largest one they share.

• 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 are 1, 2, 3, 6.
  • The highest common factor is 6.

2.2 Method 2: Prime Factorization (The Go-To Method)

Photo by Black ice on Pexels

This method works well for any size of number and is generally more efficient.

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 with across all factorizations.
4. Multiply these common prime factors (at their lowest powers) together.

Let's illustrate this with a process flow:

graph TD
    A["Start: Get numbers (e.g., 24, 36)"] --> B{"Find Prime Factors for each number"};
    B --> C["Number 1: 24 = 2^3 * 3^1"];
    B --> D["Number 2: 36 = 2^2 * 3^2"];
    C --> E{"Identify COMMON Prime Factors"};
    D --> E;
    E --> F["Common Primes: 2 and 3"];
    F --> G{"Take LOWEST POWER of each common prime"};
    G --> H["For 2: lowest power is 2^2 (from 36)"];
    G --> I["For 3: lowest power is 3^1 (from 24)"];
    H --> J{"Multiply these lowest powers"};
    I --> J;
    J --> K["HCF = 2^2 * 3^1 = 4 * 3 = 12"];
    K --> L["End"];

• 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$ (since it's $2^3$ in 24 and $2^2$ in 36)
  • Lowest power of 3: $3^1$ (since it's $3^1$ in 24 and $3^2$ in 36)
  • HCF = $2^2 \times 3^1 = 4 \times 3 = 12$.

2.3 Applications of HCF

Photo by Roshan Ravi on Pexels

HCF is super useful in a few key areas:

• Simplifying Fractions: To simplify a fraction to its lowest terms, you divide both the numerator and the denominator by their HCF.
  • Example: Simplify 12/18. HCF(12, 18) = 6.
  • $12 \div 6 = 2$
  • $18 \div 6 = 3$
  • So, $12/18 = 2/3$.
• Dividing Items into Equal Groups: If you have different quantities of items and want to divide them into the largest possible equal groups without any leftovers, you're looking for the HCF.
  • Example: You have 24 apples and 36 oranges. What's the largest number of identical fruit baskets you can make without any fruit left over? You need HCF(24, 36), which is 12. You can make 12 baskets, each with 2 apples and 3 oranges.

3. Worked Example

Let's find the HCF of three numbers: 48, 72, and 108.

1. Prime Factorization:

   • 48: Start dividing by primes. $48 \div 2 = 24$, $24 \div 2 = 12$, $12 \div 2 = 6$, $6 \div 2 = 3$, $3 \div 3 = 1$. So, $48 = 2 \times 2 \times 2 \times 2 \times 3 = 2^4 \times 3^1$.
   • 72: $72 \div 2 = 36$, $36 \div 2 = 18$, $18 \div 2 = 9$, $9 \div 3 = 3$, $3 \div 3 = 1$. So, $72 = 2 \times 2 \times 2 \times 3 \times 3 = 2^3 \times 3^2$.
   • 108: $108 \div 2 = 54$, $54 \div 2 = 27$, $27 \div 3 = 9$, $9 \div 3 = 3$, $3 \div 3 = 1$. So, $108 = 2 \times 2 \times 3 \times 3 \times 3 = 2^2 \times 3^3$.

2. Identify Common Prime Factors:
   All three numbers share the prime factors 2 and 3.

3. Take the Lowest Power of Each Common Prime Factor:

   • For the prime factor 2:
     • In 48: $2^4$
     • In 72: $2^3$
     • In 108: $2^2$
     • The lowest power is $2^2$.
   • For the prime factor 3:
     • In 48: $3^1$
     • In 72: $3^2$
     • In 108: $3^3$
     • The lowest power is $3^1$.

4. Multiply These Lowest Powers:
   HCF = $2^2 \times 3^1 = 4 \times 3 = 12$.

So, the HCF of 48, 72, and 108 is 12.

4. Key Takeaways

• The HCF is the largest number that divides evenly into all given numbers.
• Prime factorization is a powerful and reliable method for finding the HCF, especially for larger numbers.
• When using prime factorization, you only include prime factors that are common to all the numbers.
• For each common prime factor, you select its lowest power from all the numbers' factorizations.
• HCF helps simplify fractions and divide collections of items into the largest possible equal groups.

Common Mistakes to Avoid:

Photo by KATRIN BOLOVTSOVA on Pexels

• Don't confuse HCF with LCM (Lowest Common Multiple) – HCF is about what numbers share as divisors, LCM is about what they meet as multiples.
• Forgetting to check all numbers when finding common prime factors; if a prime isn't in one number's factorization, it can't be common.
• Using the highest power instead of the lowest power for common prime factors in the prime factorization method.
• Not fully prime factorizing a number; always break factors down until they are prime.

5. Now Try It

You have 60 red beads, 75 blue beads, and 90 green beads. You want to make identical necklaces using all the beads, with each necklace having the same number of red, blue, and green beads. What is the greatest number of identical necklaces you can make?

What to do: Use the prime factorization method to find the HCF of 60, 75, and 90. This HCF will be your answer.

What success looks like: You should arrive at a single number representing the maximum number of identical necklaces, and you should be able to explain how many of each color bead will be in each necklace.