The greatest common divisor (GCD) of two or more numbers is the greatest common factor number that divides them, exactly. It is also called the highest common factor (HCF). For example, the greatest common factor of 15 and 10 is 5, since both the numbers can be divided by 5.

15/5 = 3

10/5 = 2

If a and b are two numbers then the greatest common divisor of both the numbers is denoted by gcd(a, b). To find the gcd of numbers, we need to list all the factors of the numbers and find the largest common factor. 

Suppose, 4, 8 and 16 are three numbers. Then the factors of 4, 8 and 16 are:

4 → 1,2,4

8 → 1,2,4,8

16 → 1,2,4,8,16

Therefore, we can conclude that 4 is the highest common factor among all three numbers.

How to find the greatest common divisor

Before we move ahead on finding the greatest common factor of numbers, let us understand what a factor and common factors are?

What are Factors?

Factors of a number divides the original number evenly. For example, if 8 is the factor of 64, then 8 can divide 64 into 8 equal parts.

What are Common Factors?

If factor of a number is a factor of another number, then it is said to be a common factor for the two numbers. For example, 2 is a factor of 4 and 8, hence 2 is a common factor.

GCD

GCD is the greatest common factor of two or more numbers. A factor that is the highest among the numbers.

Methods to Find GCD

There are several methods to find the greatest common divisor of given two numbers.

1. Prime factorisation method
2. Long division method
3. Euclid’s division algorithm

Prime factorisation method

Every composite number, i.e. a number with more than one factor can be written as a product of prime numbers.

In the prime factorisation method, each given number is written as the product of prime numbers and then find the product of the smallest power of each common prime factor.

This method is applicable only for positive numbers, i,e. Natural numbers.

Example: Find the Greatest common factor of 24, 30 and 36.

Solution: Prime factors of 24 is 2³ × 3

Prime factors of 30 = 2 × 3 × 5

Prime factors of 36 = 2² x 3²

From the factorisation, we can see, only 2 x 3 are common prime factors.

Therefore, GCD (24, 30, 36) = 2 x 3 = 6

Read more:

• Prime Factors
• Prime Factorisation Of Hcf And Lcm
• Real Numbers For Class 10

Long division method

In this method, the largest number among the given set of numbers should be divided by the second largest number, and again the second-largest number should be divided by the remainder of the previous operation, this process will continue till the remainder is zero. The divisor, when the remainder is zero, is called the greatest common divisor of the given numbers. Learn division method for HCF here in detail.

Euclid’s division algorithm

This method is stated only for positive integers.

Find the below steps in order to get the HCF of two positive integers a and b. Here a > b.

Step 1: Applying Euclid’s division lemma to a and b we get two whole numbers q and r such that, a = bq+r ; 0 r < b.

Step 2: If r = 0, then b is the HCF of a and b. If r ≠0, then apply Euclid’s division lemma to b and r.

Step 3: Continue the above process until the remainder is zero.

Step 4: When the remainder is zero, the divisor at this stage is the HCF of given numbers.

GCD Formula

If a and b are any number, then the greatest common divisor of a and b can be given by:

GCD (a,b) = [|a.b|]/[lcm(a,b)]

Applications of Greatest common divisor

The concept of the greatest common divisor or the highest common factor is used in many real-life incidents as below.

A shopkeeper has 420 balls and 130 bats to pack in a day. She wants to pack them in such a way that each set has the same number in a box, and they take up the least area of the box. What is the number that can be placed in each set for this packing purpose?

In the above problem, the greatest common divisor of 420 and 130 will be the required number.

Other application like arranging students in rows and columns in equal number, diving a group of people into smaller sections,etc.,

Solved Examples

Example 1:

Find the greatest common divisor (or HCF) of 128 and 96.

Solution:

By the method of prime factorisation,

128 = 2 x 2 x 2 x 2 x 2 x 2 x 2

96 = 2 x 2 x 2 x 2 x 2 x 3

HCF (128, 96) = 2 x 2 x 2 x 2 x2 = 32

(OR)

By the method of division,

Hence, 32 is the HCF of 128 and 96.

(OR)

By Euclid’s division algorithm,

128 = 96 x 1 + 32

96 = 32 x 3 + 0

Hence, the HCF of 128 and 96 is 32.

Example 2:

Two rods are 22 m and 26 m long. The rods are to be cut into pieces of equal length. Find the maximum length of each piece.

Solution:

HCF or GCD is the required length of each piece.

22 = 2 x 11

26 = 2 x 13

HCF or the greatest common divisor = 2

Hence, the required maximum length of each piece is 2 m.

The greatest common factor of 3 numbers

We can find the greatest common factor/divisor of 3 three numbers by the prime factorisation method as shown below.

Example 3:

Find the greatest common factor of 24, 148 and 36.

Solution:

Prime factorisation of given numbers is

24 = 2 × 2 × 2 × 3

148 = 2 × 2 × 37

36 = 2 × 2 × 3 × 3

Greatest common factor = 2 × 2 = 4