Greatest Common Divisor (GCD): How to Calculate It

The Greatest Common Divisor (GCD) is one of the fundamental concepts in arithmetic and algebra. Finding the GCD of two or more numbers is an essential operation for simplifying fractions, solving divisibility problems, and tackling numerous practical applications. In this comprehensive guide, we explain what the GCD is, how to calculate it using different methods, and when to use it.

What Is the Greatest Common Divisor (GCD)

The Greatest Common Divisor of two or more integers is the largest positive integer that divides all the given numbers without a remainder. In other words, it is the largest divisor that the numbers have in common.

Formal definition: Given two integers a and b (not both zero), GCD(a, b) is the largest positive integer d such that d divides a and d divides b.

For example, the divisors of 12 are: 1, 2, 3, 4, 6, 12. The divisors of 18 are: 1, 2, 3, 6, 9, 18. The common divisors are: 1, 2, 3, 6. The greatest among these is 6, so GCD(12, 18) = 6.

Fundamental Properties of the GCD

• Commutativity: GCD(a, b) = GCD(b, a)
• Associativity: GCD(a, b, c) = GCD(GCD(a, b), c)
• GCD with 0: GCD(a, 0) = |a| for every non-zero integer a
• GCD with 1: GCD(a, 1) = 1 for every integer a
• Coprime numbers: if GCD(a, b) = 1, the numbers a and b are said to be coprime (or relatively prime)
• Positivity: the GCD is always a positive number

Method 1: Prime Factorization

The classic method for calculating the GCD involves decomposing each number into its prime factors and then taking the product of the common factors with the smallest exponent.

Procedure

1. Decompose each number into its prime factors
2. Identify the prime factors common to all numbers
3. For each common factor, take the one with the smallest exponent
4. Multiply the selected factors together

Example: GCD(60, 90)

Prime factorization:

• 60 = 2² x 3 x 5
• 90 = 2 x 3² x 5

Common factors with the smallest exponent:

• 2: present with exponents 2 and 1 → we take 2¹
• 3: present with exponents 1 and 2 → we take 3¹
• 5: present with exponents 1 and 1 → we take 5¹

GCD(60, 90) = 2 x 3 x 5 = 30

Example: GCD(84, 120, 168)

Factorization:

• 84 = 2² x 3 x 7
• 120 = 2³ x 3 x 5
• 168 = 2³ x 3 x 7

Common factors to all three: 2 (minimum exponent: 2) and 3 (minimum exponent: 1). The factor 5 appears only in 120 and 7 does not appear in 120.

GCD(84, 120, 168) = 2² x 3 = 4 x 3 = 12

Method 2: Euclidean Algorithm

The Euclidean algorithm is the most elegant and efficient method for calculating the GCD of two numbers. It dates back to the 3rd century BC (Euclid's Elements, Book VII) and is considered one of the oldest mathematical algorithms still in use.

Principle

The algorithm is based on the property: GCD(a, b) = GCD(b, a mod b), where "a mod b" denotes the remainder of dividing a by b. This property is applied repeatedly until the remainder is zero.

Procedure

1. Divide the larger number by the smaller and calculate the remainder
2. Replace the larger number with the smaller and the smaller with the remainder
3. Repeat until the remainder is 0
4. The GCD is the last non-zero remainder (i.e., the divisor of the last division)

Example: GCD(252, 105)

The remainder has become 0, so GCD(252, 105) = 21 (the last divisor).

Example: GCD(462, 1071)

GCD(462, 1071) = 21

Why the Euclidean Algorithm Is Superior

The Euclidean algorithm is preferable to prime factorization for several reasons:

• Efficiency: it runs in logarithmic time, much faster than factorization (which is a computationally hard problem)
• Large numbers: applicable even to very large numbers for which factorization would be impractical
• Simplicity of implementation: it only requires successive divisions with remainder

GCD and LCM: The Fundamental Relationship

The GCD (Greatest Common Divisor) and LCM (Least Common Multiple) are closely linked by the following relationship:

GCD(a, b) x LCM(a, b) = a x b

From which we derive:

LCM(a, b) = (a x b) / GCD(a, b)

This relationship is extremely useful because it allows you to calculate the LCM once the GCD is known (which can be efficiently computed using the Euclidean algorithm).

Example

Calculate the LCM of 12 and 18:

• GCD(12, 18) = 6 (calculated earlier)
• LCM(12, 18) = (12 x 18) / 6 = 216 / 6 = 36

Differences Between GCD and LCM

Practical Applications of the GCD

1. Simplifying Fractions

To reduce a fraction to its lowest terms, divide both the numerator and denominator by their GCD.

Example: simplify 84/120

• GCD(84, 120) = 12
• 84/120 = (84 ÷ 12) / (120 ÷ 12) = 7/10

2. Subdivision Problems

Problem: a gardener has 48 red roses and 36 white roses. He wants to create identical bouquets using all the roses, with the maximum number of bouquets possible. How many bouquets can he make?

• GCD(48, 36) = 12
• He can create 12 bouquets, each with 4 red roses and 3 white roses

3. Tiling

Problem: a room measures 360 cm x 480 cm. What is the side length of the largest square tile that covers the floor exactly without cutting?

• GCD(360, 480) = 120
• The tile can have a maximum side of 120 cm (3 tiles in width x 4 in length = 12 tiles total)

4. Gears and Periodicity

If two gears have 60 and 45 teeth respectively, GCD(60, 45) = 15 indicates that the same teeth will mesh again every 15 positions. This is relevant for calculating wear and mechanical synchronization.

5. Cryptography (Brief Mention)

The RSA algorithm, the foundation of modern cryptography, uses the GCD and the extended Euclidean algorithm to generate cryptographic keys. Two numbers are suitable as key components only if their GCD meets certain conditions.

The GCD in Programming

The Euclidean algorithm translates elegantly into code. Here are the recursive and iterative versions:

Recursive version (pseudocode):

function gcd(a, b): if b = 0, return a; otherwise return gcd(b, a mod b)

Iterative version (pseudocode):

function gcd(a, b): while b is not 0, calculate remainder = a mod b, then a = b, b = remainder; return a

The iterative version is generally preferred in programming because it does not risk stack overflow for very large numbers.

GCD of More Than Two Numbers

Thanks to the associative property, the GCD of three or more numbers is calculated by proceeding in pairs:

GCD(a, b, c) = GCD(GCD(a, b), c)

Example: GCD(24, 36, 60)

1. GCD(24, 36): using Euclid's algorithm, 36 ÷ 24 = 1 remainder 12, then 24 ÷ 12 = 2 remainder 0 → GCD = 12
2. GCD(12, 60): 60 ÷ 12 = 5 remainder 0 → GCD = 12

Therefore GCD(24, 36, 60) = 12

Summary Table: GCD of Common Pairs

Frequently Asked Questions (FAQ)

What is the difference between GCD and LCM?

The GCD is the largest number that divides all the given numbers, while the LCM is the smallest number that is divisible by all the given numbers. The GCD is used to simplify fractions, and the LCM is used to find the common denominator.

Is the GCD of two prime numbers always 1?

Yes, if the two numbers are different primes, the GCD is always 1 because each has only 1 and itself as divisors. If the two prime numbers are equal (for example GCD(7,7)), the result is the number itself.

How do you calculate the GCD of negative numbers?

The GCD is always defined as a positive number. For negative numbers, take the absolute values: GCD(-12, 18) = GCD(12, 18) = 6.

Can the GCD equal one of the given numbers?

Yes, when one of the numbers is a divisor of the other. For example, GCD(5, 15) = 5, because 5 divides both 5 and 15.

When are two numbers coprime?

Two numbers are coprime (or relatively prime) when their GCD is 1. This does not mean they are prime numbers: for example, 8 and 15 are not prime, but GCD(8, 15) = 1, so they are coprime.

Does the Euclidean algorithm always work?

Yes, the Euclidean algorithm always terminates in a finite number of steps and always produces the correct result. It can be shown that the number of steps is at most proportional to the logarithm of the smaller number, making it extremely efficient even for very large numbers.

What is the GCD used for in everyday life?

The GCD is used to divide objects into equal groups (event organization, fair distribution), to determine tile or module dimensions that fit perfectly on given surfaces, to simplify ratios and proportions, and to synchronize periodic events (schedules, production cycles).