GCD

Introduction to GCD (Greatest Common Divisor)

When working with numbers, especially in problems involving fractions, ratios, or divisibility, it is often useful to find the largest number that divides two or more integers exactly - without leaving any remainder. This number is called the Greatest Common Divisor, or GCD.

For example, if you want to simplify the fraction \(\frac{48}{180}\), you need to find the greatest number that divides both 48 and 180. This helps reduce the fraction to its simplest form. GCD also plays a crucial role in solving equations where integers are involved, such as Diophantine equations, and is a frequent topic in competitive exams.

In this chapter, we will explore what GCD is, how to find it using different methods, and how to apply it effectively in problem-solving.

Definition and Basic Properties of GCD

The Greatest Common Divisor (GCD) of two integers \(a\) and \(b\) (not both zero) is the largest positive integer that divides both \(a\) and \(b\) without leaving a remainder.

Mathematically,

Definition of GCD

\[GCD(a,b) = \max\{d \mid d \mid a \text{ and } d \mid b\}\]

The greatest divisor that divides both a and b

a,b = integers

d = common divisor

For example, consider the numbers 12 and 18:

Factors of 12: 1, 2, 3, 4, 6, 12
Factors of 18: 1, 2, 3, 6, 9, 18

The common factors are 1, 2, 3, and 6. The greatest among these is 6, so GCD(12, 18) = 6.

Basic Properties of GCD

Commutative: \( \mathrm{GCD}(a,b) = \mathrm{GCD}(b,a) \)
Associative: \( \mathrm{GCD}(a, \mathrm{GCD}(b,c)) = \mathrm{GCD}(\mathrm{GCD}(a,b), c) \)
GCD with zero: \( \mathrm{GCD}(a,0) = |a| \) (the absolute value of \(a\))
Non-negativity: GCD is always a positive integer

Finding GCD by Prime Factorization

One straightforward way to find the GCD of two numbers is to break each number down into its prime factors and then identify the common prime factors with the smallest exponents.

Recall that a prime number is a number greater than 1 that has no positive divisors other than 1 and itself. Every number can be expressed as a product of primes, called its prime factorization.

Steps to find GCD by prime factorization:

Find the prime factorization of each number.
Identify the common prime factors.
For each common prime factor, take the minimum power (exponent) it has in both factorizations.
Multiply these common prime factors with their minimum powers to get the GCD.

From the factor trees:

48 = \(2^4 \times 3\)
180 = \(2^2 \times 3^2 \times 5\)

Common prime factors are 2 and 3.

Minimum power of 2 is \(2\) (since 48 has \(2^4\), 180 has \(2^2\))
Minimum power of 3 is \(1\) (48 has \(3^1\), 180 has \(3^2\))

Therefore,

\[\mathrm{GCD}(48,180) = 2^2 \times 3^1 = 4 \times 3 = 12\]

Euclidean Algorithm

While prime factorization is straightforward, it can be time-consuming for large numbers. The Euclidean algorithm is a faster, more efficient method to find the GCD using repeated division.

The key idea is based on the fact that the GCD of two numbers also divides their difference.

Given two integers \(a\) and \(b\) where \(a > b\), the Euclidean algorithm uses the following recursive relation:

Euclidean Algorithm Step

\[GCD(a,b) = GCD(b, a \bmod b)\]

Recursive step to find GCD using remainder

a,b = integers

\(a \bmod b\) = remainder when a is divided by b

This means you replace the pair \((a,b)\) with \((b, a \bmod b)\) and repeat until the remainder is zero. The divisor at that step is the GCD.

graph TD    A[Start with numbers a and b (a > b)]    B[Divide a by b to get remainder r]    C{Is r = 0?}    D[Yes: GCD is b]    E[No: Replace a with b, b with r]    F[Repeat division]    A --> B --> C    C -->|Yes| D    C -->|No| E --> F --> C

Worked Examples

Example 1: Finding GCD of 48 and 180 using Prime Factorization Easy

Find the greatest common divisor (GCD) of 48 and 180 using prime factorization.

Step 1: Find prime factors of 48.

48 = 2 x 24 = 2 x 2 x 12 = 2 x 2 x 2 x 6 = 2 x 2 x 2 x 2 x 3 = \(2^4 \times 3\)

Step 2: Find prime factors of 180.

180 = 2 x 90 = 2 x 2 x 45 = 2 x 2 x 3 x 15 = 2 x 2 x 3 x 3 x 5 = \(2^2 \times 3^2 \times 5\)

Step 3: Identify common prime factors with minimum powers.

Common prime factors: 2 and 3
Minimum power of 2: 2
Minimum power of 3: 1

Step 4: Multiply these to get GCD.

\(\mathrm{GCD} = 2^2 \times 3 = 4 \times 3 = 12\)

Answer: The GCD of 48 and 180 is 12.

Example 2: Finding GCD of 252 and 105 using Euclidean Algorithm Medium

Find the GCD of 252 and 105 using the Euclidean algorithm.

Step 1: Divide 252 by 105 and find the remainder.

252 / 105 = 2 remainder 42 (since \(252 = 105 \times 2 + 42\))

Step 2: Replace (252, 105) with (105, 42).

Step 3: Divide 105 by 42.

105 / 42 = 2 remainder 21 (since \(105 = 42 \times 2 + 21\))

Step 4: Replace (105, 42) with (42, 21).

Step 5: Divide 42 by 21.

42 / 21 = 2 remainder 0 (since \(42 = 21 \times 2 + 0\))

Step 6: Since remainder is 0, GCD is 21.

Answer: The GCD of 252 and 105 is 21.

Example 3: Simplifying the fraction 462/770 using GCD Easy

Simplify the fraction \(\frac{462}{770}\) to its lowest terms.

Step 1: Find GCD of numerator and denominator.

Use Euclidean algorithm:

770 / 462 = 1 remainder 308

462 / 308 = 1 remainder 154

308 / 154 = 2 remainder 0

GCD = 154

Step 2: Divide numerator and denominator by GCD.

\(\frac{462}{770} = \frac{462 \div 154}{770 \div 154} = \frac{3}{5}\)

Answer: The simplified fraction is \(\frac{3}{5}\).

Example 4: Dividing INR 360 and INR 480 into Equal Parts using GCD Medium

Two amounts, INR 360 and INR 480, need to be divided into equal parts without any remainder. What is the maximum value of each part?

Step 1: Find the GCD of 360 and 480.

Using Euclidean algorithm:

480 / 360 = 1 remainder 120

360 / 120 = 3 remainder 0

GCD = 120

Step 2: The maximum value of each part is INR 120.

Step 3: Number of parts for each amount:

360 / 120 = 3 parts
480 / 120 = 4 parts

Answer: The amounts can be divided into parts of INR 120 each.

Example 5: Finding Missing Number using GCD and LCM Relation Hard

The GCD of two numbers is 12, and their LCM is 180. If one number is 36, find the other number.

Step 1: Recall the relation between GCD and LCM:

Relation between GCD and LCM

\[GCD(a,b) \times LCM(a,b) = |a \times b|\]

Product of GCD and LCM equals the product of the two numbers

a,b = integers

Step 2: Substitute known values:

\[ 12 \times 180 = 36 \times b \] \[ 2160 = 36 \times b \]

Step 3: Solve for \(b\):

\[ b = \frac{2160}{36} = 60 \]

Answer: The other number is 60.

Formula Bank

Definition of GCD

\[ \mathrm{GCD}(a,b) = \max\{d \mid d \mid a \text{ and } d \mid b \} \]

where: \(a, b\) are integers; \(d\) is a common divisor

Relation between GCD and LCM

\[ \mathrm{GCD}(a,b) \times \mathrm{LCM}(a,b) = |a \times b| \]

where: \(a, b\) are integers

Euclidean Algorithm Step

\[ \mathrm{GCD}(a,b) = \mathrm{GCD}(b, a \bmod b) \]

where: \(a, b\) are integers; \(a \bmod b\) is remainder of \(a\) divided by \(b\)

Tips & Tricks

Tip: Use the Euclidean algorithm for large numbers instead of prime factorization.

When to use: When numbers are large and prime factorization is time-consuming.

Tip: Remember that \(\mathrm{GCD}(a,0) = |a|\).

When to use: When one of the numbers is zero, this shortcut quickly gives the GCD.

Tip: Use the relation \(\mathrm{GCD} \times \mathrm{LCM} = \text{product of numbers}\) to find missing values.

When to use: When either GCD or LCM is missing in a problem.

Tip: Check divisibility rules before starting prime factorization to quickly identify factors.

When to use: Before factorization to save time and avoid errors.

Tip: For simplifying fractions, always find the GCD of numerator and denominator first.

When to use: When asked to reduce fractions to their lowest terms.

Common Mistakes to Avoid

❌ Confusing GCD with LCM

✓ Remember that GCD is the greatest common divisor, while LCM is the least common multiple.

Why: Both involve factors and multiples but serve different purposes in problems.

❌ Not taking minimum powers of common primes in prime factorization.

✓ Take the lowest exponent of each common prime factor when calculating GCD.

Why: GCD is the product of common prime factors with minimum powers, not maximum.

❌ Stopping the Euclidean algorithm too early.

✓ Continue the algorithm until the remainder becomes zero; the divisor at that step is the GCD.

Why: Premature stopping leads to incorrect GCD calculation.

❌ Ignoring negative signs in numbers.

✓ Always use absolute values when calculating GCD.

Why: GCD is always a positive integer regardless of sign.

❌ Applying divisibility rules incorrectly.

✓ Review and apply divisibility rules carefully before factorization.

Why: Incorrect application leads to wrong factors and wrong GCD.

The Joy of Learning

Login

The Joy of Learning

Sign-up

The Joy of Learning

Forgot Password

Introduction to GCD (Greatest Common Divisor)

Definition and Basic Properties of GCD

Definition of GCD

Basic Properties of GCD

Finding GCD by Prime Factorization

Euclidean Algorithm

Euclidean Algorithm Step

Worked Examples

Relation between GCD and LCM

Formula Bank

Tips & Tricks

Common Mistakes to Avoid

Try Practice next.

Rank

eBook

Online Test Series + eBook

Book is added to your cart!