 # Greatest common divisor

The greatest common divisor (GCD) or highest common factor (HCF) of two numbers is the largest number that divides both the two numbers exactly. In other words, the greatest common divisor is the product of the smallest power of each common prime factor in the prime factorisation of numbers.

## How to find the greatest common divisor

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

What is the prime factorisation?

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.

### 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.

### 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.

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.,

### 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