Highest Common Factor or Greatest Common Divisor

Highest Common Factor (HCF)

or 

Greatest Common Divisor ( GCD)

In arithmetic ( mathematics) and number theory, the greatest common divisor (GCD/gcd) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. The greatest number which divides each of the two or more numbers is popularly called HCF or Highest Common Factor (HCF). It is also called the Greatest Common Measure (GCM) and Greatest Common Divisor(GCD).
For any two integers a and b, usually denoted by HCF (a, b), is the largest integer that can divide both numbers a and b. (a , b)  can be also written as for simplicity. 
The HCF of more than two integers is also well-defined: it is the largest integer that can divide to all of them.

What is the Highest Common Factor (HCF)?
It is a method to find the highest common factor between numbers ( any two or more). Generally according to definitions the common factor is a number which is a factor of two or more numbers therefore HCF is used to determine the common factor. 
Example 1:-
If we consider an example, To find HCF of 2 and 3?
The factors/ divisors of 2 = 1, 2.
The factors/ divisors of 3 = 1, 3.
Common factors/ divisors = 1
Therefore the highest among common Factors (HCF) = 1 (where 1 is the highest common factor for numbers 2 and 3 since both numbers have only one factor in common.)
Therefore HCF(2, 3) = gcd (2, 3) = 1 is  the required solution of given numbers.

• Those numbers having only one common factor 1 (HCF = 1) are known as Co-Prime Numbers or Relatively Prime. 
• It is not essential that the Co-prime number must be Prime. 
• if we consider few examples like (1, 2), (1, 10), (1, 100), (5, 2), (3, 4), (5, 6), (19, 20) all are Co-Primes since their HCF = 1, although some of them are not Prime.

Various methods to find HCF of Numbers:-

1. By Factorization Method,
2. By Division Method,
3. By Relation between LCM and HCF ( By Formula) 

By  Factorization

The method to find the highest common factor of any given numbers is such as:-

• First of all write down the  Factors or Divisors of individual numbers.
• Find the common factors/ divisors between them. 
• The product of all common factors/ divisors is our HCF or GCD.

Example 2:-  Find HCF of 12 & 18?

Solution:- 

The factors/ divisors of 12 = 1, 2, 3 , 4, 6, 12.

The factors/ divisors of 18 = 1, 2, 3 , 6, 9, 18.
Common Factors = 1, 2, 3, 6.
Therefore the highest among common Factors (HCF) = 6 (where 6 is the highest common factor for numbers 2 and 3 since both numbers have four factors/ divisors in common). 
Therefore HCF(12, 18) = gcd (12, 18) = 6 is the  required solution.

Example 3:-To find HCF of 20, 30 & 50 ( Three numbers)?     

Solution:- 

 Factors of 20 = 1, 2,  4, 5, 10 & 20 ( Since 1x20= 4x5=2x 10).

The factors of 30 = 1, 2,  3, 5, 6, 15, 30.
The factors of 50 = 1, 2,  5, 10, 25 & 50 ( Since 1 x50 = 2 x 25 = 5 x 10).
Common Factors = 1, 2, 5, 10.
Therefore the highest among common Factors (HCF) = 10 (where 10 is the highest common factor for numbers 20,30 and 50 since all numbers have four factors in common).  
Therefore HCF (20, 30, 50) = gcd (20, 30, 50) = 10 is the required solution.

Example 4:-To find HCF of 18,24 & 54?     

Solution :- 

The factors/ divisors of 18 = 1, 2,  3, 6, 9, 18.

The factors / divisors of 24 = 1, 2,  3, 4, 6, 8,12, 24.

The factors / divisors of 54 = 1, 2,  3, 6, 9, 18, 27, 54.

Common factors / divisors = 1, 2, 3, 6.

Therefore the highest among common Factors (HCF) = 6 (where 6 is the highest common factor for numbers 18,24 and 54 since all numbers have four factors/divisors in common.)  

Therefore HCF (18, 24, 54) = gcd (18, 24, 54) = 6 is  the required solution.

 Example 5:-To find GCD / gcd / HCF  of 6 , 16 & 20 ?

Solution :- There are given three numbers 6, 16, and 20. Now we have to write the prime factors ( so do not write 1) of all three numbers individually.

6 =  2 x 3 

16 = 2 x 2 x 2 x 2 x 1

20 = 2 x 2 x 5

The common prime factors divisors of above numbers we get the HCF. Hence, there are ONE pairs of 2 . So the HCF of 6, 16 and 20 will be 2.
HCF (6, 16, 20) = 2   

By Division Method

We have to know about the method of finding the highest common factor using prime factorization or division.  we have to keep in mind that the division method is nothing but dividing the given numbers simultaneously to get the common factors between them. 

ALGORITHMS to solve problems of HCF by are such as.

• First of all write the given numbers horizontally, in a sequence, by separating it with commas ( It is for tradition to separate by commas) order is not important.
• Find the smallest prime number which can divide the all given number. It should exactly divide the all given numbers and we have to write in the left side.
• Now we have to write the quotients carefully.
• We have to repeat the process, unless and until we reach the stage, where there is no further division is possible for all.
•  We will get the common prime factors as the factors in the left-hand side divides all the numbers exactly. 
• The product of these common prime factors is the HCF of the given numbers is our required answers. 

Now Let us solve problems by the above algorithms to find the HCF by division method with the help of these examples "To find HCF of numbers 12, 24, 36".

Example 6:-To find HCF of 12, 24 & 36 ?     

Solution:- 

For solving this problem we have to follow the above mentioned algorithms.

• 

By  Long Division  Method.

Algorithms to find the HCF of given two numbers, For more than three processes can be done similarly taking two at a time in order.

For two numbers:-

• Identify larger and smaller Numbers,
• Divide larger number by smaller number first, such that

Larger Number/Smaller Number

•  Divide the divisor of the above step by the remainder left.

The divisor of the above step /Remainder

•  Again divide the divisor of the above step by the remainder similar to the previous step.

The divisor of the above step /Remainder

• Repeat the process until the remainder is zero.
• The divisor of the last step is the HCF.
• Example 6:-To find HCF of 135 & 225? 
• Solution:-  Since 225 is greater than 135, so we have to divide 225 to 135. 

Therefore HCF (135, 225) = 45 is our required answer.

• For three numbers:-

Repeat the above process taken two at a time in order.

________________________________________________