How to find HCF

What is HCF?

The Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of two or more numbers is the largest positive integer that divides each of the numbers without leaving a remainder.For example, the HCF of 18 and 48 is 6, because 6 is the largest number that divides both 18 and 48 evenly.The HCF of 12 and 36 is also 12.There are a few key properties of HCF:

• The HCF of two or more numbers divides each of the numbers without a remainder
• The HCF is always less than or equal to each of the numbers
• The HCF of two or more prime numbers is always 1

Also Check: Full Form of HCF

Methods of Finding HCF

To find the HCF (Highest Common Factor) of any two numbers, you can use one of the following methods:

(i) Prime Factorization Method
(ii) Division Method

Also Check: Prime Numbers from 1 to 100

HCF Using Prime Factorization Method

Step 1: Start by expressing each number as a product of its prime factors. This process is known as prime factorization.

Step 2: Identify the common prime factors of the numbers.

Step 3: The HCF is the product of the lowest powers of all common prime factors.

Example: Find the HCF of 60 and 75.

Solution: Write each number as a product of its prime factors.
2² x 3 x 5 = 60
3 x 5²= 75

Product of all common prime factors is the HCF

In this case, the common prime factors are 3 & 5.
The lowest power of 3 is 3 and 5 is 5.
So, HCF = 3 x 5 = 15

HCF By Division Method

• List the Numbers: Write the given numbers separated by commas in a horizontal line.
• Identify the Smallest Prime Factor: Determine the smallest prime number that can divide the given numbers exactly. Start dividing from the left side.
• Record the Quotients: Write down the results of the division.
• Repeat the Process: Continue this process until you are left with numbers that have no common prime factors.
• Determine the HCF: The common prime factors on the left-hand side, which divide all the numbers perfectly, will be used to find the HCF. Multiply these common prime factors to get the HCF.

Also Check: Even Numbers

Problem:Consider the HCFs of 30 and 75.

It is evident that the prime factors listed on the left side divide all the numbers completely.

Therefore, these are the common prime factors. The numbers at the bottom have no common prime factors.

Hence, the HCF is 3 × 5 = 15.

HCF by Shortcut method

Step 1: Divide the larger number by the smaller number.
Step 2: Use the remainder from step 1 as the new divisor and divide the previous divisor by it.
Step 3: Repeat this process with the new remainder.
Step 4: Continue until the remainder is zero.
Step 5: The HCF is the divisor from the last non-zero remainder step.