## What Is the Greatest Common Divisor (GCD)?

**The greatest common divisor (GCD), also known as “greatest common factor (GCF)” or “highest common factor (HCF)”, of two numbers is the greatest factor that divides both the numbers. In simple words, it is the largest factor shared between two or more numbers. **

#### Recommended Games

## Definition of Greatest Common Divisor

The greatest common divisor (GCD) of two integers can be defined as the largest positive integer that is a divisor of both numbers. It is also called the highest common factor (HCF) or the greatest common factor (GCF).

The GCD of two numbers a and b is sometimes written as GCD(a, b) or gcd(a, b).

For example, the GCD of 8 and 12 is 4.

GCD$(8, 12) = 4$

#### Recommended Worksheets

## What Are Factors?

A factor of a number is a number that divides the given number evenly without leaving a remainder. Factors are numbers that you can multiply together to get another number, called the product. Every number has at least two factors.

**Example 1: **$2 \times 4 = 8$.

So, 2 and 4 are both factors of 8.

**Example 2: **We can write 12 as

$12 = 1 \times 12$

$12 = 2 \times 6$

$12 = 3 \times 4$

Therefore 1, 2, 3, 4, 6, and 12 are all factors of 12.

## What Are Common Factors?

As the name implies, a common factor is a factor common between two or more numbers. In other words, it is a number that can evenly divide a set of two or more numbers.

We can find the common factors of two or more numbers by listing the factors of each number and then identify the factors that are common among them.

**Example 1: Find the common factors of 15 and 20.**

Factors of $15 = 1, 3, 5, 15$

Factors of $20 = 1, 2, 4, 5, 10, 20$

Factors common in 15 and 20 are 1 and 5.

**Example 2: Find common factors of 16 and 24.**

Factors of $16 = 1, 2, 4, 8, 16$

Factors of $24 = 1, 2, 3, 4, 6, 8, 12, 24$

Common factors of 16 and $24 = 1, 2, 4, 8$

## How to Find the GCD (Greatest Common Divisor)

In order to determine the greatest common divisor for a pair of two positive integers (m, n), follow the steps listed below:

**Step 1:** Write the factors of the positive integer “m.”

**Step 2:** Write the factors of the positive integer “n.”

**Step 3: **Identify the common divisors of “m” and “n.”

**Step 4:** Find the divisor that is the largest among the common divisors of “m” and “n.”

## Methods to Find the Greatest Common Divisor

There are numerous ways to determine the biggest common divisor of two numbers. The methods to find G.C.D. are as follows.

1. Listing method

2. Prime factorization method

3. Long division method

4. Repeated division method

5. Euclid’s division algorithm

## GCD by Listing Method

In this method, we list the factors of the given numbers and then highlight the common factors. After identifying the common factors, we find the largest common factor.

**Example: Find the GCD of 24 and 30 using the listing method.**

Factors of $24 = 1, 2, 3, 4, 6, 8, 12, 24$

Factors of $30 = 1, 2, 3, 5, 6, 10, 15, 30$

Common factors of 24 and $30 = 1, 2, 3, 6$

G.C.D. of 24 and $30 = 6$

## GCD by Prime Factorisation Method

In this method, we find the prime factorization of the given numbers using the factor tree method or division method. Using the prime factorization, find the common factors between the two numbers. Multiply these together to find the greatest common divisor. This method is applicable only for positive integers.

**Example 1: Find the greatest common divisor of 24 and 30.**

Let’s find the prime factorization of 24 and 30 using the factor tree method.

Prime factors of $24 = 2 \times 2 \times 3$

Prime factors of $36 = 2 \times 2 \times 3 \times 3$

Common factors of 24 and $36 = 2, 2, 3$

G.C.D. of 24 and $36 = 2 \times 2 \times 3 = 12$

**Example 2:** ** Find the greatest common factor of 168 and 180.**

**Solution: **

Prime factors of $160 = 2^{3} \times 3 \times 7 = 2 \times 2 \times 2 \times 3 \times 7$

Prime factors of $180 = 2^{2}\times 3^{2} \times 5 = 2 \times 2\times 3 \times 3 \times 5$

The common factors are $2 \times 2 \times 3 = 12$

Therefore, greatest common factor of $(168, 180) = 12$

## GCD by Long Division Method

The long division method is more useful for finding GCD of large numbers. The steps to be followed for long division method are as follows:

**Step 1:** Divide the large number by the smaller one.

**Step 2:** Treat the remainder obtained as the new divisor and set the previous divisor as the new dividend.

**Step 3: **Divide the first divisor by the first remainder.

**Step 4:** Divide the second divisor by the second remainder.

**Step 5: **Continue this process till the remainder becomes 0.

**Step 6: **The divisor, which does not leave a remainder, is the G.C.D. of the two numbers and thus, the last divisor is the required G.C.D. of the given numbers.

**Example 1: Find GCD of 105 and 189 using the long division method. **

Since the last divisor that we got is 21, we can say that the greatest common divisor of 105 and 189 is 21.

G.C.D. of 105 and $189 = 21$.

**Example 2: Find GCD of 32, 56, and 46.**

To find the GCD of three numbers, we start by using the long division on any two numbers. Once the division is complete, we divide the remaining number by the last divisor obtained in the first division.

## GCD by Repeated Division Method

This method is pretty similar to the long division method. Let’s understand the steps.

**Step 1:** Divide the given numbers by the smallest common prime factor.

**Step 2:** Divide the quotients thus obtained by their smallest common prime factor.

**Step 3:** Repeat until there is no more common prime factor between the quotients.

**Step 4:** Multiply all the divisors (prime factors).

**Example: Find the G.C.D. of 24 and 36 using repeated division.**

## GCD by Euclid’s Division Algorithm

This method is applicable only for positive integers. Euclid’s division algorithm is based on the Euclid’s division lemma. It is a method used to find GCD of two positive integers.

According to Euclid’s division lemma, if we have two positive integers a and b, then there would be whole numbers q and r that satisfy the equation $a = bq + r$, where $0 \le r \lt b$.

Using this lemma, we express the larger number “a” in terms of the smaller number “b” in the quotient remainder form $a = b q + r$.

If $r = 0$, then b is the G.C.D. of a and b.

If r 0, then we again use the lemma on the numbers b and r as GCD (b, r) $=$ GCD (a, b).

Repeat the above process until the remainder is zero. When the remainder is zero, the last divisor is the GCD of given numbers. (OR the last non-zero remainder is the GCD.)

- If $a = 0$, then GCD $(a, b) = b$

GCD $(0, b) = b$.

- If $b = 0$, then GCD $(a, b) = a$

GCD $(a, 0) = a$.

**Example 1: Find the G.C.D. of 123 and 36.**

**Example 2: Find the G.C.D. of 1180 and 482.**

Thus, gcd$(1180, 482) = 2$

## Greatest Common Divisor Formula

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

** GCD **$(a,b) = \frac{a \times b}{LCM (a, b)}$

## Finding Greatest Common Divisor by LCM Method

The greatest common factor can be found using the LCM method using the following formula:

The steps to calculate the GCD of (a, b) using the LCM method is:

**Step 1:** Find the product of a and b.

**Step 2: **Find the least common multiple (LCM) of a and b.

**Step 3: **Divide the product by LCM.

**Step 4: **The obtained value is the greatest common divisor of (a, b).

**Example: If the LCM(24, 36) = 72, find the GCD(24, 36).**

GCD $(a, b) = \frac{a \times b}{LCM (a, b)}$

GCD $(24, 36) = \frac{24 \times 36}{LCM (24, 36)}= \frac{24 \times 36}{72} = 12$

## Applications of Greatest Common Divisor

- To simplify fractions or ratios, to reduce them to their simplest form.

Example: To find the simplest form of $\frac{35}{50}$, we find the gcd(35, 50).

GCD$(35,50) = 5$

Divide both the numerator and denominator by the gcd.

$\frac{35 \div 5}{50 \div 5} = \frac{7}{10}$

- To find the LCM of the given numbers.

LCM $(a, b) = \frac{a \times b}{GCD(a, b)}$

- The concept of GCD is used in many real-life situations, such as dividing a group of people into smaller sections, arranging students in rows and columns of equal numbers.
- GCD has interesting applications in geometry as well. For example, we can determine the side of the largest square tile that can cover the rectangular floor of dimensions “a b” by finding the GCD(a,b).

## Facts about Greatest Common Divisor

- The GCD (Greatest Common Divisor) is also known as HCF (Highest Common Factor) or GCF (Greatest Common Factor).
- The formal definition of GCD is credited to Euclid who discussed it in his book “elements.”
- Two numbers are said to be relatively prime if their greatest common factor (GCD) is 1.
- When one number is a multiple of the other, the smaller number is the GCD and the greater number is the LCM.
- The GCD of two prime numbers is always 1.

## Conclusion

In this article, we have learned about the greatest common divisors and methods of finding them. Let us solve some greatest common divisor examples using those methods.

## Solved Examples on the Greatest Common Divisor

**1. Find GCD of 16 and 60 using the long division method. **

Since last divisor is 4, GCD of 16 and 60 = 4

**2. Find the greatest common factor of 150 and 180 by using the prime factorization method.**

**Solution: **

Prime factors of $150 = 2 \times 3 \times 5^{2} = 2 \times 3 \times 5 \times 5$

Prime factors of $180 = 2^{2}\times 3^{2}\times 5 = 2 \times 2 \times 3 \times 3 \times 5$

The common factors $= 2, 3, 5$

GCD $(150, 180) = 2 \times 3 \times 5 = 30$

Therefore, greatest common factor of $(150, 180) = 30$

**3. If the LCM of 15 and 70 is 210, find the greatest common divisor of 15 and 70.**

**Solution: **

$a = 15 , b = 70$

The greatest common divisor of 15 and 70 can be calculated using the given formula:

GCD $(a,b) = \frac{a \times b}{LCM (a, b)}$

Thus, GCD $(a,b) = \frac{15 \times 70}{210} = 5$

Therefore, the greatest common divisor of (15, 70) is 5.

## Practice Problems on the Greatest Common Divisor

## Greatest Common Divisor (GCD): Definition, Methods, Examples

### Greatest common divisor (GCD) is also known as

GCM (Greatest Common Measure), GCF (Greatest Common Factor), HCF (Highest Common Factor) are other names for GCD.

### What is the GCD of 8 and 12?

GCD is the largest positive integer that divides each of the integers.

Factors of $8 = 1, 2, 4, 8$

Factors of $12 = 1, 2, 3, 4, 6, 12$

Common factors $= 1, 2, 4$

So, the GCD of 8 and 12 is 4.

### GCD$(5, 7) =$

5 and 7 are relatively prime numbers. The only common factor between them is 1.

GCD$(5, 7) = 1$

## Frequently Asked Questions about Greatest Common Divisor

**What are co-prime numbers ?**

Co-prime numbers, also known as relative prime or mutually prime numbers, are numbers that have no common factor other than 1. A set of co-prime numbers must consist of at least two numbers. Co-prime numbers have only one common factor between them. For example, 4 (an even square number) and 7 (prime number) are co-prime.

**What is LCM?**

LCM is the short form for “Least Common Multiple.” It is defined as the smallest multiple that two or more numbers have in common.

Consider two integers, 2 and 3.

Multiples of 2: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20…

Multiples of 3: 3, 6, 9, 12, 15, 18, 21, 24, 27, 30 …

6, 12, 18, … are common multiples of 2 and 3. The number 6 is the smallest. Therefore, 6 is the least common multiple of 2 and 3.

**What is the difference between GCD and LCM?**

GCD, or Greatest Common Divisor, is the largest number that will divide all the other numbers of the group without leaving a remainder. So, it is smaller than all the numbers or, at the most, is equal to the smallest number of the group.

LCM or Lowest Common multiple is the smallest number that is a multiple of all the other numbers of the group. So, it is larger than all the numbers or, at the most, is equal to the largest number of the group.

**What is the difference between multiples and factors?**

A multiple is a product that we get when the given number is multiplied by an integer. For example: 12 is a multiple of 3 because $3 \times 4 = 12$

A factor is a number that divides a given number completely without leaving a remainder.For example: 3 and 4 are factors of 12 because $3 \times 4 = 12$.

**What is the meaning of GCD? Are GCD and HCF the same?**

GCD stands for the greatest common divisor. It is the largest positive integer that divides both the given numbers. HCF stands for highest common factor. HCF and GCD mean the same thing.