HCF: Formulas, Methods, Tricks and Examples

HCF, or Highest Common Factor, is the greatest positive integer that divides two or more numbers without leaving a remainder. This page covers HCF formulas, prime factorisation, the division method, useful shortcuts, properties and solved examples for quantitative aptitude questions.

On this page

What is HCF?

The HCF of two or more numbers is the greatest positive integer that divides each number exactly. It is also called the greatest common divisor (GCD).

For example, the factors common to 18 and 24 are 1, 2, 3 and 6, so HCF(18, 24) = 6. The HCF of a set of numbers cannot be greater than the smallest number in that set.

HCF Formula & Tricks

Important Formulas

Prime factorisation formula
HCF = product of common prime factors with the smallest powers

Write each number as a product of primes, select only the primes common to all numbers, and use the least exponent of each selected prime.

Euclidean algorithm
If a = bq + r, then HCF(a, b) = HCF(b, r), where 0 ≤ r < b

Repeatedly divide the larger number by the smaller number. The last non-zero remainder is the HCF.

HCF-LCM relation
For two positive integers a and b: HCF(a, b) × LCM(a, b) = a × b

If the HCF and one number are known, the LCM can be found by dividing the product of the two numbers by their HCF, and vice versa.

HCF of fractions
HCF of fractions = HCF of numerators ÷ LCM of denominators

This formula applies when the fractions are first written in their lowest terms.

Quick Tricks

Use the remainder method for large numbers

Replace the larger number with the remainder obtained after division. Continue until the remainder becomes zero. The preceding non-zero remainder is the HCF.

Example: For 867 and 255: 867 = 255 × 3 + 102; 255 = 102 × 2 + 51; 102 = 51 × 2 + 0. Therefore, HCF = 51.
Check divisibility before calculating fully

If one number divides another exactly, the smaller number is the HCF. If the numbers have no common prime factor, their HCF is 1.

Example: Since 14 divides 70 exactly, HCF(14, 70) = 14. Also, HCF(25, 36) = 1 because they have no common prime factor.
Use differences when numbers are close

The HCF of two numbers is also the HCF of the smaller number and their difference: HCF(a, b) = HCF(b, a − b), when a > b.

Example: HCF(391, 299) = HCF(299, 92) = HCF(92, 23) = 23.

HCF Concepts

HCF by prime factorisation

In the prime factorisation method, the HCF is obtained by multiplying the common prime factors with their smallest powers.

Factorise every number into primes. A prime factor is included only if it occurs in all the numbers. For each common prime, choose the minimum exponent.

Example: 36 = 2² × 3² and 60 = 2² × 3 × 5. Therefore, HCF(36, 60) = 2² × 3 = 12.

HCF by the division method

The division method finds the HCF by repeatedly dividing the larger number by the smaller number and using the remainder as the next divisor.

For two positive integers a and b, divide a by b and write a = bq + r. Then replace the pair (a, b) with (b, r). When r becomes zero, the last non-zero divisor is the HCF.

Example: For 252 and 105: 252 = 105 × 2 + 42; 105 = 42 × 2 + 21; 42 = 21 × 2. Hence, HCF = 21.

HCF of three or more numbers

Find the HCF successively: first find the HCF of two numbers, then find the HCF of that result with the next number.

The operation is associative, so HCF(a, b, c) = HCF(HCF(a, b), c). The final result must divide every number in the set.

Example: For 24, 36 and 60: HCF(24, 36) = 12, and HCF(12, 60) = 12. Thus, the HCF is 12.

HCF and LCM relationship

For two positive integers, the product of the HCF and LCM equals the product of the two numbers.

If HCF(a, b) = h and LCM(a, b) = l, then h × l = a × b. This relation is valid for two numbers; it cannot be directly extended as a product formula for three or more numbers.

Example: For 18 and 24, HCF = 6. Therefore, LCM = (18 × 24) ÷ 6 = 72.

HCF in remainder-based questions

When the same number leaves equal remainders on division by given numbers, the HCF of the divisors divides the difference between the original number and that remainder.

If a number N leaves remainder r when divided by a and b, then a and b divide N − r. Hence, the greatest possible common divisor of a and b can be found using HCF(a, b), or by applying the relation to the relevant differences.

Example: If a number leaves remainder 5 when divided by 24 and 36, then the required common divisor of the divisor conditions is HCF(24, 36) = 12, and 12 divides the number after subtracting 5.

HCF Video Lessons

Watch short topic-wise lessons for quick revision.

14 Lessons
Lesson 1 of 14 Quick Revision

HCF Using Prime Factorisation and Euclidean Algorithm

Learn to calculate the Highest Common Factor using prime factorisation and the Euclidean algorithm, with a clear understanding of how both methods work.

Continue with more lessons and practice in PrepShots.Watch More in App - Start ₹1 Trial →
More HCF Lessons Scroll to explore →

Practice HCF Questions

Practise published questions related to this topic.

1A three-digit number is such that the sum of the number and its square root is 132 . Find the number.→ 2Find the LCM of the numbers 780, 2080 and 2600.→ 3The square root of the sum of squares of two numbers is 25. If one number is 15, find the other number.→ 4What is the smallest 4-digit number that is divisible by 36?→ 5What is the least number which should be added to 539, so that the number obtained is exactly divisible by 10, 15 and 3?→ 6If 15² = 225 , then find the approximate value of √22.5+√2.25+25.→ 7Which of the following numbers is divisible by 11?→ 8Which of the following is a pair of co-primes?→ 9The number of two-digit numbers divisible by 6 is:→ 10A rectangular courtyard, 4.56 meters long and 7.68 meters wide is paved exactly with square tiles of same size. Find the size (in cm) of the largest tile that can be used for this purpose.→

HCF Quick Quiz

Attempt 5 questions and check your score instantly.

Quick Revision Notes

HCF Quick Revision

Remember these definitions, formulas and calculation rules for HCF questions.

  • HCF is the greatest positive integer that divides every given number exactly.
  • By prime factorisation, use common prime factors with their smallest exponents.
  • In the Euclidean method, the last non-zero remainder is the HCF.
  • For two positive integers, HCF × LCM = product of the numbers.
  • If one number divides another, the smaller number is the HCF.
  • If two numbers have no common prime factor, their HCF is 1.
  • For three or more numbers, calculate the HCF successively.
  • The HCF cannot exceed the smallest number in the given set.

HCF FAQs

What is the HCF of 48 and 180?

48 = 2⁴ × 3 and 180 = 2² × 3² × 5. Therefore, HCF = 2² × 3 = 12.

How is HCF calculated using the Euclidean algorithm?

Divide the larger number by the smaller number and replace the pair with the divisor and remainder. Repeat until the remainder is zero; the last non-zero remainder is the HCF.

What is the HCF of two co-prime numbers?

The HCF of two co-prime numbers is 1. For example, HCF(17, 28) = 1.

What is the HCF of 0 and a non-zero number?

HCF(0, a) = |a| for a non-zero integer a. Therefore, HCF(0, 15) = 15.

If the HCF of 20 and 30 is 10, what is their LCM?

LCM = (20 × 30) ÷ 10 = 60.

What is the HCF of 3/4 and 9/10?

HCF of numerators = HCF(3, 9) = 3, and LCM of denominators = LCM(4, 10) = 20. Therefore, the HCF is 3/20.

Continue learning HCF on PrepShots

Continue on PrepShots