Finding GCD or HCF

What is GCD or HCF?

GCD (Great Common Devisor) or HCF (High Common Factor) is the biggest common devisor or factor of two or more numbers. There are a few algorithms out there to find GCD or HCF, such as Prime Factor and Euclid's Division Algorithm.

Prime Factorization

Prime Factorization is a method of finding GCD by calculating the factors of each number and comparing them for matching. 

 

For instance, we are finding the GCD of 64 and 12, 

64 = 2 x 2 x 2 x 2 x 2 x 2 = 2^6

12 = 2 x 2 x 3 = 2^2 x 3

 

We can see that 64 and 12 have 2 as the same common. So to find the GCD of both numbers, we take out the biggest common number and choose the smallest one. so between 2^6 and 2^2, 2^2 or 4 is the CGD of 64 and 12. 64 and 12 can have 4 as their biggest common divisor.

Euclid's Division Algorithm

Apart from Prime Factorization, the Euclid Division algorithm finds GCD or HCF in different ways. First, between two numbers, we take the bigger number and divide it by the smaller one. If there is no remainder, it means that the smaller number is the greatest common divisor. Otherwise, in case there is a remaining, we need to take the smaller number and divide it by the remaining. Let's find the GCD of 64 and 12:

 

First step: 64% 12 = 5, remainder = 4

Second step: 12 % 4 = 3, remainder = 0

As can be seen, 12 % 4 has a remainder 0, which means that 4 is the greatest common factor of 64 and 12.