GCD and LCM Explained: Methods, Formulas, and Applications

The greatest common divisor (GCD) and least common multiple (LCM) are two of the most important concepts in number theory. They appear in fraction simplification, scheduling problems, cryptography, and countless other areas of mathematics.

This guide explains what GCD and LCM are, how to compute them using multiple methods, the relationship between them, and where they show up in real-world applications.

What Is the GCD?

The greatest common divisor (also called the greatest common factor or highest common factor) of two integers is the largest positive integer that divides both numbers evenly. For two integers and :

Example 1: GCD by Listing Factors

Find :

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

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

Common factors: 1, 2, 3, 4, 6, 12

Methods for Finding the GCD

Method 1: Prime Factorisation

Express each number as a product of prime factors, then take the product of the common prime factors raised to their lowest powers.

Example 2: GCD by Prime Factorisation

Find :

Take the minimum power of each common prime factor:

Method 2: The Euclidean Algorithm

The Euclidean algorithm is the most efficient method for computing the GCD. It is based on the principle that , and repeats until the remainder is zero:

Example 3: Euclidean Algorithm

Find :

The last non-zero remainder is 21, so .

Method 3: Extended Euclidean Algorithm

The extended Euclidean algorithm not only finds the GCD but also finds integers and such that:

This is known as Bezout's identity and is fundamental in modular arithmetic and cryptography (e.g., finding modular inverses in RSA encryption).

Example 4: Extended Euclidean Algorithm

Find and such that :

Working backwards from the Euclidean algorithm:

So and , and indeed .

What Is the LCM?

The least common multiple of two integers is the smallest positive integer that is divisible by both numbers:

Example 5: LCM by Listing Multiples

Find :

Multiples of 4: 4, 8, 12, 16, 20, 24, ...

Multiples of 6: 6, 12, 18, 24, 30, ...

LCM by Prime Factorisation

Express each number as a product of primes, then take the product of all prime factors raised to their highest powers.

Example 6: LCM by Prime Factorisation

Find :

The GCD-LCM Relationship

One of the most important properties connecting GCD and LCM is:

This means you can compute the LCM from the GCD (and vice versa):

Example 7: Using the Relationship

Find using the GCD we already computed:

GCD and LCM of More Than Two Numbers

To find the GCD or LCM of more than two numbers, apply the operation iteratively:

Example 8: GCD of Three Numbers

Find :

So .

Properties of GCD and LCM

Here are key properties you should know:

• Commutative: and .
• Associative: .
• Identity: and .
• Coprime numbers: If , then and are coprime, and .
• Divisibility: always divides both and , and both divide .

Applications of GCD

• Simplifying fractions: Divide numerator and denominator by their GCD. For example, .
• Cryptography: RSA encryption relies on the extended Euclidean algorithm to compute modular inverses.
• Tiling problems: The largest square tile that perfectly covers a rectangular floor of metres has side length .
• Music theory: GCD determines the simplest ratio of frequencies in musical intervals.

Applications of LCM

• Adding fractions: The least common denominator is the LCM of the denominators. For , the LCD is .
• Scheduling: If event A occurs every 4 days and event B every 6 days, they coincide every days.
• Gear ratios: The LCM determines when gear teeth realign.
• Signal processing: Finding the period of combined periodic signals.

Worked Example: Scheduling Problem

Example 9: Bus Schedules

Bus A departs every 15 minutes and Bus B departs every 20 minutes. If both depart at 9:00 AM, when do they next depart at the same time?

Using prime factorisation:

They next depart together after 60 minutes, at 10:00 AM.

Worked Example: Fraction Addition

Example 10: Adding Fractions with LCM

Add :

Find :

Convert and add:

Common Mistakes

1. Confusing GCD with LCM. GCD is the largest common divisor (always smaller or equal to both numbers). LCM is the smallest common multiple (always larger or equal to both numbers).
2. Using wrong powers in prime factorisation. For GCD, take the minimum power. For LCM, take the maximum power.
3. Forgetting . Zero is divisible by every integer, so every integer divides zero.
4. Not simplifying the final answer. After using GCD to simplify a fraction, verify no common factors remain.

Try It Yourself

Compute GCD and LCM instantly with our free GCD & LCM Calculator. It supports multiple numbers, shows prime factorisations, and provides step-by-step solutions using both the Euclidean algorithm and prime factorisation methods. For finding all factors of a number, our Factor Calculator provides complete factor lists and prime factorisations.