GCD Full Form

What is the full form of GCD?

“Greatest Common Divisor” is the full form of GCD. It is the highest number that divides two or more numbers without a remainder. It is also called the Greatest Common Factor (GCF) and the Highest Common Factor (HCF). It is used for reducing fractions to be in their lowest terms. For example, the GCD of two numbers, 20 and 28, is 4 since both numbers 20 and 28 are completely divisible by 1, 2, and 4 without leaving the remainder. The largest number among factors 1, 2, and 4 is 4. If m and n are two numbers the greatest common divisor (GCD) of both numbers is written by gcd(m,n).

How to Find the Greatest Common Factor?

We require to understand the following to proceed further with how to find the greatest common divisor.

Factors:

Each of the natural numbers which divide the given number completely is known as the factor of the given number.

For Example, 3 and 4 are factors of 12 because (completely divide) and (completely divide). 12 has other factors also as 1,2,3,4,6 and 12.

Common Factors:

A common factor of two or more numbers is a number that divides each of the numbers completely.

For Example, 2 is a factor of both 6 and 8, therefore 2 is a common factor.

Prime Factors: When a factor of a given number is a prime number that factor is called the prime factor of the given number.

For Example, A factor of 6 and 18 is 3 which is a prime number, therefore 3 is a prime factor.

Methods to Find GCD

The following are the methods to find GCD.

1. Common factor method

2. Prime factor method

3. Long division method

4. Euclid’s division algorithm

Common Factor Method

Step: 1. Find out all the factors of each given number

2. Find out common factors of the given numbers

3. The greatest of the common factors which are found in step no.2, is the required Greatest Common Divisor.

Prime Factor Method

Step: 1. Find out all the prime factors of each given number

2. Find out common prime factors of the given numbers

3. Multiply the common prime factors which are found in step no.2, to get the required Greatest Common Divisor.

Long Division Method

This method of long division is mostly used for large numbers.

Step: 1. Divide the greater number by the smaller number

2. The remainder becomes the new divisor and the previous divisor as the new dividend

3. Continue this process until we get zero remainders. The last divisor is known as the required Greatest Common Divisor.

Euclid’s Division Algorithm

This Euclid's division algorithm is based on Euclid's division lemma

Since the method consists of a precise series of well-defined steps, therefore it is called an algorithm.

1. Apply the division algorithm with the larger number, k as the dividend, and the smaller number, d as the divisor. i.e., express , where 'q' is a positive integer,r is the remainder, and .

2. If, repeat step 1 with 'd' of step 1 as k and 'r' of step 1 as d till we get

3. The divisor of the step in which r = 0 is the GCD of the given numbers.

Applications of The Greatest Common Divisor

The real-time application of the greatest common divisor (GCD) is to equally distribute two or more sets of items into their largest possible grouping.

Other applications like arranging students in rows and columns in equal numbers, measurements, and construction fields.