HCF means highest common factor. It is also called the GCD (greatest common divisor) or GCF (greatest common factor). They mean the same thing here: the largest positive whole number that divides every given number with no remainder. A factor and a divisor are two names for the same idea. ^{[1] [2]}

For small numbers, the quickest trick is usually this:

Start with the smallest number. Test its factors from largest to smallest. The first factor that divides every number is the HCF.

The fastest trick for small numbers

Find the HCF of 24 and 36.

Start with 24, the smaller number. Its factors are:

24, 12, 8, 6, 4, 3, 2, 1

Test from the top:

• 24 does not divide 36.
• 12 divides 24 and 36.

So, HCF(24, 36) = 12.

You do not need to list every factor of both numbers. Once you find a factor of the smaller number that divides all the others, stop. Nothing larger can work.

With three numbers

Find the HCF of 18, 30, and 42.

Factors of 18, from largest down, are 18, 9, 6, 3, 2, 1.

• 18 does not divide 30.
• 9 does not divide 30.
• 6 divides 18, 30, and 42.

So, HCF(18, 30, 42) = 6.

Notice that 3 is also common, but it is not the highest common factor. Also, a number must divide every number. For example, 6 divides 18 and 30, and it also divides 42. That final check matters.

Use factor listing when the numbers are small and their factors are easy to spot. For larger or awkward numbers, use one of the methods below. Listing every factor always works, but it can become slow. ^[3]

Prime factorisation: the dependable method

A prime factorisation writes a number as a product of prime numbers. For example, 80 = 2⁴ × 5. ^[3]

To find an HCF with prime factors:

1. Write each number as prime factors.
2. Keep only primes that appear in every number.
3. For each shared prime, use its smallest exponent.
4. Multiply those selected factors.

Find the HCF of 72, 108, and 180.

• 72 = 2³ × 3²
• 108 = 2² × 3³
• 180 = 2² × 3² × 5

The primes shared by all three are 2 and 3.

• The smallest power of 2 is 2².
• The smallest power of 3 is 3².

Therefore:

HCF = 2² × 3² = 4 × 9 = 36

Do not include 5. It occurs in 180, but not in the other two numbers. Do not use 2³ or 3³ either. Those powers do not divide every number.

This method is especially useful when repeated factors matter. The general rule is to multiply every common prime raised to its lowest shared power. ^[3]

Euclid’s algorithm: best for large pairs

For two large numbers, repeated division is often faster than factor trees. This is the Euclidean algorithm.

1. Divide the larger number by the smaller number.
2. Replace the larger number with the smaller number, and the smaller number with the remainder.
3. Repeat until the remainder is 0.
4. The last non-zero remainder is the HCF.

Find the HCF of 252 and 105:

• 252 = 2 × 105 + 42
• 105 = 2 × 42 + 21
• 42 = 2 × 21 + 0

The last non-zero remainder is 21.

So, HCF(252, 105) = 21.

Why does this work? Any number that divides both original numbers also divides the remainder after division. So each new pair has exactly the same common factors as the pair before it. ^[4]

For three or more numbers, find the HCF of the first two, then use that answer with the next number.

For example:

• HCF(84, 126) = 42
• HCF(42, 210) = 42

Therefore, HCF(84, 126, 210) = 42.

Quick method chooser

For example, since 12 divides 60 exactly, HCF(12, 60) = 12.

Important special cases

• If the only shared factor is 1, the numbers are coprime (or relatively prime). For example, HCF(14, 25) = 1. ^[5]
• HCF(n, 0) = the positive value of n. For example, HCF(18, 0) = 18. ^[6]
• For negative numbers, ignore the sign when finding the HCF: HCF(−12, 30) = 6. ^[7]
• HCF(0, 0) is often left undefined, although some sources set it to 0. State the convention if this case appears. ^[2]

Do not confuse HCF with LCM, the least common multiple. The HCF is the largest number that divides all the given numbers. The LCM is the smallest positive number that all the given numbers divide into evenly. ^[8]

Try these

1. Find HCF(28, 42).
2. Find HCF(24, 36, 60).
3. Find HCF(150, 210) using prime factors.
4. Find HCF(391, 299) using Euclid’s algorithm.
5. Find HCF(17, 51).

Answers

1. 14. Factors of 28 include 14, and 42 ÷ 14 = 3.
2. 12. Start with 24: 12 divides 24, 36, and 60.
3. 30. 150 = 2 × 3 × 5² and 210 = 2 × 3 × 5 × 7. Shared factors: 2 × 3 × 5.
4. 23. 391 = 1 × 299 + 92; 299 = 3 × 92 + 23; 92 = 4 × 23 + 0.
5. 17. Since 17 divides 51 exactly, the smaller number is the HCF.

The main trick is not one fixed shortcut. Pick the method that fits the numbers, then check that your final HCF divides every number with no remainder.

Sources

1. 1.MathWorld mathworld.wolfram.com
2. 2.ProofWiki proofwiki.org
3. 3.OpenStax openstax.org
4. 4.MathWorld mathworld.wolfram.com
5. 5.MathWorld mathworld.wolfram.com
6. 6.ProofWiki proofwiki.org
7. 7.ProofWiki proofwiki.org
8. 8.OpenStax openstax.org