Greatest common divisor

The numbers when multiplied together to get another number are called the factors of the number. For example consider the number fourteen, 2 when multiplied with 7 gives 14 and hence 2 and 7 are the factors of the number 14 which includes 1 and also 14. The factors of 6 are 1, 2, 3 and 6.
The factors of 9 are 1,3 and 9. The common factors of 6 and 9 are 1 and 3. So, we can define common factors as the factors which are common to all the numbers considered.

 Let us now learn about Greatest common factor which is also called Highest Common Factor and at times Greatest Common Divisor. It can be defined as the greatest integer which divides the number evenly that is without any remainder. In short it is called GCD.

For example, GCD of 12 and 18 is 6 as 6 is the greatest integer which divides 12 and 18 evenly. Let us now find the Greatest Common Divisor of the numbers 36 and 72. The first step to find the GCD would be to write all the factors of each of the numbers, factors of 36 are 1, 2, 3, 4, 6, 9, 12, 18 and 36; factors of 72 are 1, 2, 3, 4, 6, 9, 12, 18, 36 and 72.

The next step is to identify the greatest integer which is common to both the lists, 36 is the largest integer common to both the lists and hence GCD of 36 and 72 is 36.

There are different methods to find the GCD of two or more numbers the simplest being the prime factorization method where prime factors of each numbers are listed and then the greatest prime factor common is determined.

The other method is Euclid’s algorithm which involves a process of repeated division given by the Greatest Common Divisor formula, gcd(a,b)=gcd(b, a mod b) where [a mod b] is got by { a – b[a/b]}, mod here means modulus. There are variations in the formula according to the values of a and b.

Let us now learn about properties of GCD which can be given as:

• For any integers ‘a’ and ‘b’ there exist integers ‘p’ and ‘q’ such that [p.a+q.b]=gcd(a,b)
• If ‘a’ and ‘b’ are relatively prime integers then there exist an integer ‘p’ such that pa=1(mod b)
• If ‘a’, ‘b’ and ‘c’ are relatively prime integers and if a divides bc then a divides c