Greatest Common Divisor (GCD) Explained: Definition, Properties, Formula & Solved Examples

The Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF), is the largest number that divides two or more numbers without leaving a remainder. It’s widely used in simplifying fractions, solving problems involving divisibility, and breaking numbers into smaller, equal parts. GCD plays an essential role in number theory and real-world applications.

Get Homework Help

1. Introduction to the Greatest Common Divisor:

The Greatest Common Divisor (GCD), also known as the Highest Common Factor (HCF), is a fundamental mathematical concept that deals with finding the largest integer that can exactly divide two or more given numbers. It is widely used in various areas of mathematics, such as simplifying fractions, solving number theory problems, and more. Understanding GCD helps in breaking down complex numbers into simpler terms.

2. What is the Greatest Common Divisor:

The Greatest Common Divisor (GCD) of two or more numbers is the largest positive integer that divides each of the numbers without leaving a remainder. In other words, GCD is the greatest factor that is common to two or more numbers.

Example: For the numbers $12$ and $18$:

• Factors of $12$: $1, 2, 3, 4, 6, 12$

• Factors of $18$: $1, 2, 3, 6, 9, 18$

• The largest common factor is $6$, so the GCD of $12$ and $18$ is $6$.

3. How to Find the Greatest Common Divisor:

There are several methods for finding the GCD of two or more numbers. Let's explore the most common methods:

(i) Finding GCD Using Prime Factorization Method

In this method, you find the prime factorization of the given numbers and then identify the common prime factors with the smallest exponents.

Steps:

1. Find the prime factorization of each number.

2. Identify the common prime factors.

3. Take the lowest power of each common prime factor and multiply them together to get the GCD.

Example:

Find the GCD of $36$ and $60$ using prime factorization.

• Prime factorization of $36$: $36 = 2^2 \times 3^2$

• Prime factorization of $60$: $60 = 2^2 \times 3 \times 5$

The common prime factors are $2^2$ and $3$. Therefore, the GCD is:
$GCD(36, 60) = 2^2 \times 3 = 4 \times 3 = 12$

(ii) Finding GCD Using Listing Out the Factors Method

This is a straightforward method where you list each number's factors and then find the largest common factor.

Steps:

1. List all the factors of each number.

2. Identify the common factors.

3. The largest common factor is the GCD.

Example:

Find the GCD of $16$ and $24$.

• Factors of $16$: $1, 2, 4, 8, 16$

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

The common factors are $1, 2, 4, 8$. The largest common factor is $8$, so the GCD of $16$ and $24$ is $8$.

(iii) Finding GCD Using Repeated Division Method

This method involves dividing the larger number by the smaller number and continuing the process until the remainder is zero.

Steps:

1. Divide the larger number by the smaller number.
2. Replace the larger number with the remainder and repeat the process.
3. The last non-zero remainder is the GCD.

Example:

Find the GCD of $48$ and $18$ using the repeated division method.

1. Divide by: $\frac{48}{18} = 2$ $(\text{remainder} \space 12)$

2. Divide by: $\frac{18}{12} = 1$ $(\text{remainder} \space 6)$

3. Divide by: $\frac{12}{6} = 2$ $(\text{remainder} \space 0)$

The GCD is $6$.

(iv) Finding GCD Using Euclidean Algorithm

The Euclidean Algorithm is an efficient way to find the GCD by using repeated subtraction or division.

Steps:

1. Divide the larger number by the smaller number.
2. Replace the larger number with the remainder from the division.
3. Repeat until the remainder is zero. The divisor at this point is the GCD.

Example:

Find the GCD of $56$ and $98$ using the Euclidean Algorithm.

1. Divide by: $\frac{98}{56} = 1$ $(\text{remainder} \space 42)$

2. Divide by: $\frac{56}{42} = 1$ $(\text{remainder} \space 14)$

3. Divide by: $\frac{42}{14} = 3$ $(\text{remainder} \space 0)$

The GCD is $14$.

4. Rules for Greatest Common Divisor:

• Rule 1: The GCD of two numbers is always less than or equal to the smaller number.

• Rule 2: If one number is a divisor of the other, the GCD is the smaller number.

• Rule 3: The GCD of two prime numbers is always $1$ because they have no common factors other than $1$.

• Rule 4: The GCD of a number and $1$ is always $1$.

• Rule 5: If both numbers are equal, the GCD is the number itself.

5. Greatest Common Divisor Formula:

For two numbers $a$ and $b$, the relationship between the GCD and the LCM (Least Common Multiple) is given by the formula:

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

This formula highlights the relationship between GCD and LCM, showing that their product equals the product of the two numbers.

6. Properties of Greatest Common Divisor:

• Commutative Property: $\text{GCD}(a, b) = \text{GCD}(b, a)$

• Associative Property: $\text{GCD}(a, b, c) = \text{GCD}\bigg(\text{GCD}(a, b), c\bigg)$

• Distributive Property: $\text{GCD}(a, b c) = \text{GCD}\bigg(\text{GCD}(a, b), \text{GCD}(a, c)\bigg)$

• $\text{GCD}$ of a Number and Itself: $\text{GCD}(a, a) = a$

• $\text{GCD}$ of a Number and $0$: $\text{GCD}(a, 0) = a$

7. Relationship Between GCD and LCM:

The Greatest Common Divisor (GCD) and the Least Common Multiple (LCM) are two closely related concepts in number theory. They are connected by an important formula that links their values to the product of the numbers involved. This relationship allows us to easily calculate one value if the other is known alongside the product of the numbers.

Explanation of the Relationship:

The relationship between the $\text{GCD}$ and $\text{LCM}$ of two numbers is given by the following formula: $\text{GCD}(a, b) \times \text{LCM}(a, b) = a \times b$

This equation tells us that the product of the $\text{GCD}$ and $\text{LCM}$ of two numbers always equals the product of the numbers themselves.

• $\text{GCD}$ represents the largest factor that both numbers share.

• $\text{LCM}$ represents the smallest multiple that both numbers share.

Thus, this relationship highlights how the $\text{GCD}$ deals with the common factors of two numbers, while the $\text{LCM}$ deals with the multiples of the same numbers.

Why Does the Relationship Hold?

This relationship holds because:

• The GCD focuses on the shared factors of two numbers (their overlap in divisibility).

• The LCM ensures that both numbers are included as multiples in a larger number.

When you multiply the GCD and LCM, you effectively ensure that every factor (both shared and individual) of the numbers is included exactly once, resulting in the product of the two numbers.

Example: Finding GCD and LCM of $20$ and $50$

Find the GCD and LCM of $20$ and $50$ and verify the relationship.

1. Step 1: Find GCD using prime factorization

   • Prime factorization of $20$: $20 = 2^2 \times 5$

   • Prime factorization of $50$: $50 = 2 \times 5^2$

   The common factors are $2^1$ and $5^1$, so the GCD is: $\text{GCD}(20, 50) = 2 \times 5 = 10$

2. Step 2: Find LCM using prime factorization

   • Take the highest powers of all prime factors: $2^2 \times 5^2$

   • So, the LCM is: $\text{LCM}(20, 50) = 2^2 \times 5^2 = 4 \times 25 = 100$

3. Step 3: Verify the relationship
   According to the relationship formula: $\text{GCD}(20, 50) \times \text{LCM}(20, 50) = 20 \times 50$

   Substituting the values: $10 \times 100 = 20 \times 50$

   Both sides equal $1000$, verifying the relationship: $1000 = 1000$

8. Difference Between GCD and LCM:

• GCD: The largest factor common to two or more numbers.

• LCM: The smallest multiple commons to two or more numbers.

Key Differences:

• GCD is based on division, while LCM is based on multiplication.

• GCD is used to find the greatest factor, while LCM is used to find the smallest common multiple.

Example: Let’s consider the numbers $12$ and $18$.

Step 1: Factors of $12$ and $18$

• Factors of $12$: $1, 2, 3, 4, 6, 12$

• Factors of $18$: $1, 2, 3, 6, 9, 18$

• The highest common factor is $6$.

Step 2: Multiples of $12$ and $18$

• Multiples of $12$: $12, 24, 36 \dots$

• Multiples of $18$: $18, 36 \dots$

• The lowest common multiple is $36$.

Thus:

• $\text{GCD}(12, 18) = 6$ (the largest common divisor).
• $\text{LCM}(12, 18) = 36$ (the smallest common multiple).

9. Greatest Common Divisor Solved Examples:

Question: 1

Find the GCD of $45$ and $75$ using prime factorization.

Solution:

• Prime factorization of $45$: $45 = 3^2 \times 5$

• Prime factorization of $75$: $75 = 3 \times 5^2$

The common prime factors are $3^1 \times 5^1 = 15$.

So, $\text{GCD}(45, 75) = 15$.

Question: 2

Find the GCD of $40$ and $60$ using the Euclidean algorithm.

Solution:

1. Divide by: $\dfrac{60}{40} = 1$ $(\text{remainder} \space 20)$

2. Divide by: $\dfrac{40}{20} = 2$ $(\text{remainder} \space 0)$

So, $\text{GCD}(40, 60) = 20$.

Question: 3

Find the GCD of $48$ and $64$ Using the Listing Out the Factors Method.

Solution:

• Factors of $48$: $1, 2, 3, 4, 6, 8, 12, 24, 48$

• Factors of $64$: $1, 2, 4, 16, 32, 64$

Final Answer

$\text{GCD}(48, 64) = 16$.

Question: 4

Find the GCD of $84$ and $36$ Using the Repeated Division Method.

Solution:

1. Divide by: $\dfrac{84}{36} = 2$ $(\text{remainder} \space 12)$

2. Divide by: $\dfrac{36}{12} = 3$ $(\text{remainder} \space 0)$

Final Answer:

The GCD of $84$ and $36$ is $12$.

Question: 5

Use the formula to Find the GCD of 24 and 36.

Solution:

Step 1: Find the LCM of $24$ and $36$

Using prime factorization, we will first find the $LCM$ of $24$ and $36$.

• Prime factorization of $24$: $24 = 2^3 \times 3$

• Prime factorization of $36$: $36 = 2^2 \times 3^2$

To find the LCM, take the highest powers of all prime factors:

• Highest power of $2$: $2^3$

• Highest power of $3$: $3^2$

Thus, the LCM of $24$ and $36$ is: $LCM(24, 36) = 2^3 \times 3^2 = 8 \times 9 = 72$

Step 2: Apply the GCD Formula

Now, use the formula to calculate the GCD:

$\text{GCD}(24, 36) = \dfrac{24 \times 36}{\text{LCM}(24, 36)} = \dfrac{24 \times 36}{72}$

Step 3: Simplify

First, multiply $24$ and $36$: $24 \times 36 = 864$

Now, divide $864$ by $72$: $\dfrac{864}{72} = 12$

Final Answer:

The $\text{GCD}$ of $24$ and $36$ is $12$.
$GCD(24, 36) = 12$

10. Practice Questions on Greatest Common Divisor:

Q:1. Find the GCD of $28$ and $35$ using the prime factorization method.

Q:2. Use the Euclidean algorithm to find the GCD of $48$ and $72$.

Q:3. Find the GCD of $50$ and $75$ by listing all the factors.

Q:4. Use the repeated division method to find the GCD of $36$ and $84$.

Q:5. Find the GCD of $25$, and $45$ using the GCD formula.

11. FAQs on Greatest Common Divisor:

What is the Greatest Common Divisor (GCD)?

The Greatest Common Divisor (GCD), or the Highest Common Factor (HCF), is the largest number that divides two or more numbers without leaving a remainder. It is the greatest factor that is common to the numbers.

How is the GCD different from the LCM?

The GCD finds the largest common factor between two or more numbers, while the LCM (Lowest Common Multiple) finds the smallest common multiple. GCD focuses on divisors, whereas LCM focuses on multiples.

Can the GCD of two numbers be greater than either?

No, the GCD of two numbers is always less than or equal to the smaller of the two numbers. It is the largest number that divides both.

What is the GCD of two prime numbers?

The GCD of two prime numbers is always $1$, as prime numbers only have $1$ as their common factor.

How can I find the GCD of two numbers?

You can find the GCD using methods such as prime factorization, listing out the factors, repeated division, or the Euclidean Algorithm, which is one of the fastest and most efficient methods.

Can the GCD be used to simplify fractions?

Yes, the GCD is often used to simplify fractions by dividing the numerator and the denominator by their GCD to reduce the fraction to its simplest form.

What is the relationship between GCD and LCM?

The product of the GCD and LCM of two numbers is equal to the product of the two numbers: $GCD(a, b) \times LCM(a, b) = a \times b$

12. Real-life Application of Greatest Common Divisor:

In real life, LCM synchronizes repeating events, such as scheduling. For example, if two buses arrive at intervals of $15$ minutes and $20$ minutes, the LCM of $15$ and $20$ ($60$) will tell you that both buses will arrive together every $60$ minutes. LCM is also used to simplify fractions, especially when adding or subtracting fractions with different denominators.

13. Conclusion:

The Greatest Common Divisor (GCD) is an essential mathematical concept that simplifies many problems, from reducing fractions to dividing items into equal parts. Understanding the methods for finding the GCD, whether through prime factorization, listing, or the Euclidean algorithm, gives you the flexibility to solve problems efficiently. GCD also connects to the LCM and provides foundational tools for higher mathematics and real-world applications.

If you have any suggestions regarding the improvement of the content of this page, please write to me at My Official Email Address: [email protected]

$\fcolorbox{black}{lightpink}{\color{blue}{Get Assignment Help}}$
Are you Stuck on homework, assignments, projects, quizzes, labs, midterms, or exams?
To get connected to our tutors in real-time. Sign up and get registered with us.

$\color{red} \bold{Related \space Pages:}$
Solving Algebraic Equations Calculator
Algebra Cheat Sheet
Pre Algebra Operation Calculators
Quadratic Equation Calculator
Prime Factorisation Calculator