Greatest Common Divisor: Definition, Methods and Examples

GCD stands for Greatest Common Divisor. It is defined as the greatest factor which is present between any given two or more numbers. GCD is basically used to find fewer possible numbers. The Greatest Common Divisor is also known as Greatest Common Factor (GCF) or Highest Common Factor (HCF). GCD has numerous applications like it helps to find commonalities where 2 x 5 = 10 and 5 x 2 = 10 as well.

Read Also: Class 12 Euclid Division Lemma

Key Terms: GCD, HCF, Factorisation Method, Prime Factorisation Method, Division Method

---

Greatest Common Divisor

[Click Here for Sample Questions]

Greatest Common Divisor, also known as HCF, is the Greatest Common Divisor of two or more numbers. It is known to be the largest positive integer that can divide the given numbers without leaving a remainder. Let’s understand by the example below:

Example: Find out what is the Greatest Common Divisor (GCD) of 11 and 22.

Solution: The factors of the given number, 11 are: 1 and 11

The factors of the given number, 22 are: 1, 11, and 22

The common factors of 11 and 22 are: 1 and 11

The greatest among the common factors is: 11

Therefore, we get the Greatest Common Divisor (GCD) of 11 and 22 is =11

Note: This example is done in the Common Factor Method.

Check Important Notes for Boolean Algebra

---

Methods to find GCD

[Click Here for Sample Questions]

There are mainly three methods that are used to find GCD of any given numbers and they are:

• Common Factor Method
• Prime Factorization Method
• Division Method

Common Factor Method: 

This is an easy method that is mostly used to find the GCD of any given numbers. Below are the steps to find GCD in the common factor method.

Step 1: Write down the given numbers separately, and then write the factors of the numbers next to it.

Step 2: Write down the common factors of those given numbers.

Step 3: Find out the Greatest Common Divisors from the list of common factors. 

The Greatest Common Divisor is the GCD of the given numbers. Now to understand better, look at the example below: 

Example of Common Factor Method:

Question: Find out the Greatest Common Divisor of 20 and 44.

Solution: The factors of 22 are: 1, 2, 4, 5, 10 and 20

The factors of 44 are: 1, 2, 4, 22 and 44

The common factors of 22 and 44 are: 1, 2 and 4

The greatest among the common factors is 4

Therefore, the Greatest Common Divisor of 22 and 44 is: 4

Read More: Class 10 Real Numbers

Prime Factorization Method: 

Let’s say, when a number is expressed as a product of its factors, we say that the number has been factorized. Thus, when we write 36=4 8, we say that 36 have been factorized. This is only one of the factorizations of 36. The others are:

In all the above factorizations of 36, we ultimately arrive at only one factorization, which is: 2 2 3 3. In this factorization of the number 36, the only factors 2 and 3 are prime numbers. Such factorization of any number is what we call a prime factorization. 

Now, to find GCD in the prime factorization method, we need to follow the steps that are mentioned below:

Step 1: Draw a long L-shaped line and write the given numbers by separating each of them by a comma.

Step 2: On the left side of the L shaped line, write the smallest prime factor which divides the given numbers without leaving any remainders.

Step 3: After that, divide the given numbers with the prime number and write down their quotient under the L-shaped lines. 

Step 4: Repeat the steps 1, 2 and 3 until there is no common prime factor for the given numbers.

Step 5: The prime factors on the left side is the common prime factor for the given numbers, so write it down separately.

Step 6: To find GCD using the obtained common prime factors, simply multiply the common prime factors.

Let’s look at an example below to understand better the concept of prime factorization method:

Example of Prime Factorization Method

Question: Find the GCD of 12 and 16.

Solution: First, we need to find the prime factors of 12 and 16.

12 = 2 × 2 × 3

16 = 2 × 2 × 2 × 2

The common prime factors are = 2, 2

GCD = 2 × 2 = 4

Therefore, the GCD of 12 and 16 is: 4

Check Important Formulas for Logarithm

Division Method

In this method, we need to divide the largest number by the smallest number among the given numbers until the remainder is 0. The last divisor will be the GCD of the given numbers. There are some steps that need to be followed to find the GCD of any given numbers. Let’s understand them with the example given below:

Example of Division Method: 

Question: Find the GCD of 12 and 18.

Solution: Step 1: Treat the smallest number, i.e., 12 as divisor and the bigger number, i.e., 18 as a dividend.

Step 2: The remainder 6 becomes the divisor and the divisor becomes the dividend.

Step 3: Repeat step 2 until the remainder becomes zero. The last divisor is the GCD. 

Therefore, the GCD of 12 and 18 is: 6

Check Also: Division of Monomial by another Monomial

---

Things to Remember 

[Click Here for Sample Questions]

• The GCD (Greatest Common Divisor) is also known as HCF (Highest Common Factor) or GCF (Greatest Common Factor).
• GCD is defined as the largest positive integer which can divide the given numbers without leaving a remainder.
• There are mainly three methods that are used to find the GCD and they are:
  • Common Factor Method
  • Prime Factorization Method
  • Division Method
• If a factor of a number is also a factor of another number, then we know that it is a common factor for the two numbers. For example - 3 is a factor of 6 and 9. Hence, 3 is a common factor.
• The numbers which are multiplied to obtain another number are called prime factors. For example – 2, 4 and 5 are the prime factors of 40.
• The concept of GCD is used in many real-life incidents such as, dividing a group of people into smaller sections, arranging students in rows and columns in equal numbers.

Read More: Division of Polynomial by another Monomial

---