HCF: highest common factor

Common factors

A factor of a number divides it exactly. A common factor of two or more numbers divides each of them. Common factors answer questions about cutting things into equal parts. Suppose a floor is 12 ft by 16 ft and we want equal square tiles with whole-foot sides, with no cutting. The side must divide 12 (to fit across) and 16 (to fit along), so it must be a common factor of 12 and 16.

Factors of 12: 1, 2, 3, 4, 6, 12. Factors of 16: 1, 2, 4, 8, 16. Common factors: 1, 2 and 4. To use as few tiles as possible, choose the biggest, 4 ft, which needs 3 × 4 = 12 tiles. Allowing fractional sides does not help: a side that fits both lengths a whole number of times can be at most 4 ft.

The highest common factor

The HCF (highest common factor) is the greatest of the common factors; another name is the GCD, the greatest common divisor. Whenever a problem asks for the largest equal size that fits several quantities exactly, the answer is the HCF. If 84 kg and 108 kg of rice are packed in equal bags, each holding rice from one farm only, the common factors of 84 and 108 are 1, 2, 3, 4, 6 and 12. The fewest bags come from 12 kg bags: 7 + 9 = 16 bags.

The Jump Jackpot game shows the same idea on a number line. Starting at 0, a jump size lands only on its multiples, so to land on both treasures it must be a common factor of their positions. The longest such jump is the HCF: 10 for treasures at 30 and 50, and 14 for 28 and 42.

Using prime factorisation

Listing every factor is slow for large numbers, and a missed factor gives a wrong answer. Prime factorisation is safer. Every factor of a number is a part of its prime factorisation, so a common factor must be a part of every factorisation. The biggest shared part is the HCF:

• keep only the primes that appear in all the numbers;
• take each of them the fewest times it appears.

For 72 = 2 × 2 × 2 × 3 × 3 and 120 = 2 × 2 × 2 × 3 × 5, both have three 2s, and the smaller number of 3s is one; 5 is not shared. So HCF = 2 × 2 × 2 × 3 = 24. For 225 = 3 × 3 × 5 × 5 and 750 = 2 × 3 × 5 × 5 × 5, the HCF is 3 × 5 × 5 = 75. The same rule works for three numbers: 42 = 2 × 3 × 7, 75 = 3 × 5 × 5 and 24 = 2 × 2 × 2 × 3 share only one 3, so their HCF is 3.

Be careful to break numbers all the way into primes. Writing 72 = 6 × 12 and 144 = 8 × 18 might suggest that nothing is shared, but in primes 72 = 2 × 2 × 2 × 3 × 3 and 144 = 2 × 2 × 2 × 2 × 3 × 3, so the HCF is 72.

When the HCF is 1

If two numbers share no prime at all, their only common factor is 1, and they are called co-prime. For example, 96 = 2 × 2 × 2 × 2 × 2 × 3 and 275 = 5 × 5 × 11 have HCF 1. Two consecutive numbers, such as 20 and 21, are always co-prime, because a number bigger than 1 cannot divide two numbers that are only 1 apart.

Why it matters

The HCF tells us the largest equal share: the biggest tile, the longest piece of rope, the largest group with nothing left over. It is also used to simplify fractions, since dividing the numerator and denominator by their HCF gives the lowest terms. Next, see LCM: least common multiple and relation between HCF and LCM. Answers to the textbook questions are in the NCERT solutions for Part 2 Chapter 3; see all of Part 2 Chapter 3 notes.