An Initiative by SAARTHI IAS
Maarg Manthan · Topic 2.1

Highest Common Factor (HCF) by Division and Prime Factorization Method

Quantitative Aptitude › HCF, LCM and Divisibility Rules · Topic 2.1

The Highest Common Factor (HCF), also called the Greatest Common Divisor (GCD), of two or more numbers is the largest number that divides each of them exactly. It is found either by prime factorization, taking the common primes with the smallest powers, or by the division method of repeated division with remainders.

Share:
Highest Common Factor (HCF) by Division and Prime Factorization Method - Quantitative Aptitude - MaargX UPSC Maarg Manthan

Quick Answer

The Highest Common Factor (HCF), also called the Greatest Common Divisor (GCD), of two or more numbers is the largest number that divides each of them exactly. It is found either by prime factorization, taking the common primes with the smallest powers, or by the division method of repeated division with remainders.

At a Glance

  • Also called Greatest Common Divisor (GCD)
  • Method 1 Prime factorization: smallest powers of common primes
  • Method 2 Division method: divide, take remainder, repeat
  • HCF of co-prime numbers 1
  • HCF is never larger than the smallest number
  • Used for Largest tile, equal groups, greatest measure

Where Does It Fit?

This is the first topic of the HCF and LCM macro. It builds on the factors and primes met in Number of Factors, Sum of Factors and Product of Factors of a Number and Prime Numbers, Composite Numbers and Co-Prime Numbers. The next topic, Lowest Common Multiple (LCM) by Division and Prime Factorization Method, finds the matching Lowest Common Multiple, and Relationship Between HCF, LCM and the Product of Two Numbers links the two.

What Is the HCF of Numbers?

In short: the HCF of a set of numbers is the biggest number that goes into every one of them without a remainder.

Numbers Common factors HCF
12 and 18 1, 2, 3, 6 6
20 and 30 1, 2, 5, 10 10
8 and 15 1 1 (co-prime)
24 and 36 1, 2, 3, 4, 6, 12 12
  • Common factor: a number that divides every number in the set exactly.
  • Greatest of them: among all common factors, the largest is the HCF.
  • Co-prime numbers: numbers whose HCF is 1, such as 8 and 15.
  • Bounds: the HCF can be at most the smallest number of the set, and it equals the smallest number when that number divides all the others.

How Do You Find the HCF by Prime Factorization?

In short: write each number as a product of primes, pick the primes that appear in all of them, take each with the smallest power, and multiply.

Prime factorization method

  • Step 1: write each number as a product of prime powers.
  • Step 2: pick only the primes common to all the numbers.
  • Step 3: for each common prime take the smallest power.
  • Step 4: multiply these prime powers to get the HCF.
Number Prime factors
84 2² × 3 × 7
126 2 × 3² × 7
Common, smallest powers 2 × 3 × 7 = 42

This method is best for small numbers. The factor ideas come from Number of Factors, Sum of Factors and Product of Factors of a Number.

How Do You Find the HCF by the Division Method?

In short: divide the larger number by the smaller, then divide the divisor by the remainder, and repeat until the remainder is 0. The last divisor is the HCF.

Division (Euclid) method

  • HCF(a, b) = HCF(b, remainder of a divided by b).
  • Repeat until the remainder is 0; the last non-zero divisor is the HCF.
  • For three numbers, find the HCF of two and then the HCF of that answer with the third.

This method is fast for large numbers where prime factorization is slow. The relation between this HCF and the LCM is explained in Relationship Between HCF, LCM and the Product of Two Numbers.

Solved Examples

Example 1

Question: Find the HCF of 84 and 126 by prime factorization.

  1. 84 = 2² × 3 × 7 and 126 = 2 × 3² × 7.
  2. Common primes are 2, 3 and 7. The smallest powers are 2¹, 3¹ and 7¹.
  3. HCF = 2 × 3 × 7 = 42.

Answer: 42

Example 2

Question: Find the HCF of 408 and 1032 by the division method.

  1. 1032 = 2 × 408 + 216.
  2. 408 = 1 × 216 + 192.
  3. 216 = 1 × 192 + 24, and 192 = 8 × 24 + 0.
  4. The last divisor is 24.

Answer: 24

Example 3

Question: Find the HCF of 72, 108 and 180.

  1. 72 = 2³ × 3²; 108 = 2² × 3³; 180 = 2² × 3² × 5.
  2. Common primes: 2 and 3. Smallest powers: 2² and 3².
  3. HCF = 4 × 9 = 36.

Answer: 36

Example 4

Question: A hall is 624 cm long and 420 cm wide. What is the side of the largest square tile that fits exactly, and how many tiles are needed?

  1. The tile side must divide both 624 and 420, so it is HCF(624, 420).
  2. 624 = 1 × 420 + 204; 420 = 2 × 204 + 12; 204 = 17 × 12 + 0. So HCF = 12.
  3. Tiles along the length = 624 ÷ 12 = 52 and along the width = 420 ÷ 12 = 35.
  4. Total tiles = 52 × 35 = 1820.

Answer: Side 12 cm; 1820 tiles

Example 5

Question: Find the HCF of 2⁴ × 3² × 5 and 2³ × 3³ × 7.

  1. Common primes are 2 and 3.
  2. Smallest powers: 2³ and 3².
  3. HCF = 8 × 9 = 72.

Answer: 72

Shortcuts and Tricks

  • If one number divides the other, the smaller one is the HCF, for example HCF(15, 45) = 15.
  • The HCF of two consecutive integers is always 1, because consecutive integers are co-prime.
  • HCF(a, b) = HCF(a, b − a), so you can subtract the smaller number from the larger before dividing.
  • Use the division method for numbers above three digits, and prime factorization for small numbers.
  • For largest-measure word problems (largest tile, greatest rod, equal groups), the answer is the HCF.

Common Mistakes

  • Taking the highest power of each prime. That gives the LCM, not the HCF; the HCF uses the smallest powers.
  • Including a prime that is missing from one of the numbers. Only primes present in every number count.
  • Stopping the division method one step early. Continue until the remainder is exactly 0.
  • Dividing the smaller number by the larger one. Always divide the larger number by the smaller.
  • Confusing a tiling problem with an LCM problem. Largest piece means HCF; smallest common length means LCM.

Practice Questions

  1. Find the HCF of 36 and 60.
  2. Find the HCF of 45, 75 and 105.
  3. Find the HCF of 221 and 391.
  4. Find the HCF of 1001 and 1859.
  5. What is the HCF of 17 and 19?
  6. Largest square tile for a floor 540 cm by 360 cm: find the side.

Answers: 1) 12; 2) 15; 3) 17; 4) 143; 5) 1; 6) 180 cm.

Why Is This Topic Important?

  • Direct questions HCF problems appear in SSC CGL every year.
  • Word problems Tiling, grouping and measuring use the HCF.
  • Base for LCM The relation in Relationship Between HCF, LCM and the Product of Two Numbers needs both values.
  • Speed The division method solves big numbers in a few lines.

What Comes Next?

The next topic is Lowest Common Multiple (LCM) by Division and Prime Factorization Method, which finds the smallest number that every given number divides.

Key Terms and Formulas

  • HCF Largest number dividing all given numbers exactly
  • GCD Another name for HCF
  • Co-prime Numbers whose HCF is 1
  • Prime factorization Writing a number as a product of primes
  • Euclid method Repeated division with remainders
  • Common factor A number that divides every number in the set

Exam Corner

Points to Remember

  • HCF uses the smallest power of every common prime.
  • The HCF of co-prime numbers is 1.
  • The HCF cannot exceed the smallest of the numbers.
  • In the division method, the last non-zero divisor is the HCF.
  • Largest tile, greatest measure and equal groups are HCF problems.

Do Not Confuse With

  • HCF vs LCM HCF is the biggest common divisor; LCM is the smallest common multiple.
  • Smallest vs highest power HCF uses the smallest power of common primes; LCM uses the highest power of all primes.
  • HCF vs product The product of the numbers is far larger than the HCF.
  • Factor vs multiple The HCF is a factor of every number; the LCM is a multiple of every number.

Memory Hook

HCF means smallest powers of common primes; LCM means highest powers of all primes.

GS Relevance

HCF is a core arithmetic topic for SSC CGL, CAT and CSAT quantitative aptitude, used in tiling, grouping and measurement problems.

Frequently Asked Questions

What is the HCF of two numbers?

The HCF, or highest common factor, of two numbers is the largest number that divides both of them exactly. For example, the HCF of 12 and 18 is 6, because 6 divides both and no larger number does. The HCF is also called the greatest common divisor, or GCD.

How do you find the HCF by prime factorization?

To find the HCF by prime factorization, write each number as a product of primes, pick the primes common to all numbers, take each with its smallest power, and multiply. For 84 and 126 the common primes are 2, 3 and 7, so the HCF is 2 times 3 times 7, which is 42.

How does the division method find the HCF?

The division method divides the larger number by the smaller, then divides the divisor by the remainder, and repeats until the remainder is zero. The last divisor is the HCF. For 408 and 1032 the steps end with a divisor of 24, so the HCF is 24.

What is the HCF of co-prime numbers?

The HCF of co-prime numbers is 1, because co-prime numbers have no common factor other than 1. For example, 8 and 15 are co-prime and their HCF is 1. Two consecutive integers, such as 20 and 21, are always co-prime, so their HCF is also 1.

When do word problems use the HCF?

Word problems use the HCF when the question asks for the largest piece, the greatest measure or the biggest equal groups that fit exactly. Examples are the largest square tile for a floor or the greatest length that measures several ropes exactly, where the answer is the HCF of the given lengths.

PYQ Practice — Statement Analysis

1 The HCF of 12 and 18 is 6.
True

The common factors are 1, 2, 3 and 6, and the greatest is 6.

2 The HCF of two co-prime numbers is 1.
True

Co-prime numbers share no common factor other than 1.

3 The HCF of two numbers can be greater than the smaller number.
False

The HCF divides the smaller number, so it cannot exceed it.

4 The HCF of 24 and 36 is 24.
False

24 does not divide 36. The HCF is 12.

Share: