$' '

GCD and LCM Calculator: How to Find Greatest Common Divisor & Least Common Multiple

A comprehensive guide to finding the GCD and LCM of any set of numbers using multiple methods.

The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) are two of the most frequently used concepts in number theory and practical mathematics. Whether you are simplifying fractions, finding common denominators, scheduling events, or solving Diophantine equations, understanding how to compute the GCD and LCM efficiently is essential. This guide explains both concepts from scratch, walks through multiple calculation methods with worked examples, and connects them with the fundamental relationship that ties them together. For instant results, use our free GCD and LCM calculator.

What Is the GCD (Greatest Common Divisor)?

The Greatest Common Divisor (also called Greatest Common Factor or GCF) of two or more numbers is the largest positive integer that divides each of the numbers without leaving a remainder.

For example, the divisors of 12 are {1, 2, 3, 4, 6, 12} and the divisors of 18 are {1, 2, 3, 6, 9, 18}. The common divisors are {1, 2, 3, 6}, and the greatest of these is 6. So GCD(12, 18) = 6.

The GCD is useful whenever you need to reduce a fraction to its simplest form. For instance, to simplify 12/18, divide both numerator and denominator by GCD(12, 18) = 6, giving 2/3.

What Is the LCM (Least Common Multiple)?

The Least Common Multiple of two or more numbers is the smallest positive integer that is a multiple of each of the numbers.

For example, the multiples of 4 are {4, 8, 12, 16, 20, 24, ...} and the multiples of 6 are {6, 12, 18, 24, 30, ...}. The common multiples are {12, 24, 36, ...}, and the least of these is 12. So LCM(4, 6) = 12.

The LCM is essential when you need to find a common denominator for adding or subtracting fractions, or when scheduling events that repeat at different intervals.

Method 1: Listing Method (For Small Numbers)

Find GCD(24, 36) by listing

Step 1: List all divisors of 24: {1, 2, 3, 4, 6, 8, 12, 24}

Step 2: List all divisors of 36: {1, 2, 3, 4, 6, 9, 12, 18, 36}

Step 3: Common divisors: {1, 2, 3, 4, 6, 12}

Step 4: Greatest: GCD = 12

This method works fine for small numbers but becomes impractical for large ones. That is where the Euclidean algorithm shines.

Method 2: Euclidean Algorithm (For Any Size Numbers)

The Euclidean algorithm is one of the oldest and most efficient algorithms in mathematics. It is based on the principle that GCD(a, b) = GCD(b, a mod b), and it terminates when the remainder reaches zero.

Find GCD(252, 105) using the Euclidean algorithm

Step 1: 252 ÷ 105 = 2 remainder 42 → GCD(252, 105) = GCD(105, 42)

Step 2: 105 ÷ 42 = 2 remainder 21 → GCD(105, 42) = GCD(42, 21)

Step 3: 42 ÷ 21 = 2 remainder 0 → GCD(42, 21) = 21

✅ GCD(252, 105) = 21

The Euclidean algorithm is extremely fast — it runs in O(log min(a,b)) time, making it practical even for numbers with hundreds of digits. This is the method used by most online GCD calculators.

Method 3: Prime Factorization

Another approach is to break each number down into its prime factors and then combine them appropriately.

Find GCD and LCM of 60 and 84 by prime factorization

Step 1: 60 = 2² × 3¹ × 5¹

Step 2: 84 = 2² × 3¹ × 7¹

GCD: Take the minimum power of each common prime: 2² × 3¹ = 12

LCM: Take the maximum power of each prime present: 2² × 3¹ × 5¹ × 7¹ = 420

The Golden Relationship: GCD × LCM = a × b

For any two positive integers a and b:

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

This is a powerful shortcut. If you already know the GCD, you can find the LCM without prime factorization:

Example: Find LCM(252, 105) using the GCD

Step 1: We already found GCD(252, 105) = 21.

Step 2: LCM = (252 × 105) / 21 = 26,460 / 21 = 1,260

Step-by-Step Examples

Example 1: Simplifying a Fraction

Simplify the fraction 48/64.

Step 1: Find GCD(48, 64). Using Euclidean: 64 mod 48 = 16, 48 mod 16 = 0 → GCD = 16.

Step 2: Divide numerator and denominator by 16: 48/16 = 3, 64/16 = 4.

Result: 48/64 = 3/4

Example 2: Finding a Common Denominator

Add the fractions 5/6 and 7/9.

Step 1: Find LCM(6, 9). Prime factors: 6 = 2 × 3, 9 = 3². LCM = 2 × 3² = 18.

Step 2: Convert: 5/6 = 15/18 and 7/9 = 14/18.

Step 3: Add: 15/18 + 14/18 = 29/18

Example 3: Event Scheduling

A bus arrives every 15 minutes and a train arrives every 20 minutes. They both arrive together at 8:00 AM. When will they next arrive together?

Step 1: Find LCM(15, 20). 15 = 3 × 5, 20 = 2² × 5. LCM = 2² × 3 × 5 = 60.

Step 2: They will next arrive together 60 minutes later, at 9:00 AM.

GCD and LCM for More Than Two Numbers

Both concepts extend naturally to three or more numbers. For the GCD, you can apply the Euclidean algorithm pairwise: GCD(a, b, c) = GCD(GCD(a, b), c). For the LCM, similarly: LCM(a, b, c) = LCM(LCM(a, b), c).

Find GCD(24, 36, 48)

Step 1: GCD(24, 36) = 12 (using Euclidean algorithm)

Step 2: GCD(12, 48) = 12

Result: GCD(24, 36, 48) = 12

Common Use Cases

Fraction arithmetic: Simplifying fractions (GCD) and finding common denominators (LCM).
Scheduling: Finding when repeating events align (e.g., meetings, bus schedules).
Cryptography: The RSA encryption algorithm relies on the GCD for key generation.
Music theory: Finding rhythmic patterns and time signatures that align.
Computer science: Hash table sizing, memory allocation, and algorithm optimization.
Tile and flooring: Determining the largest tile size that evenly covers a space.

Calculate GCD and LCM Instantly

Our free calculator supports 2 to 10 numbers with step-by-step solutions using the Euclidean algorithm.

Try the GCD & LCM Calculator →

Frequently Asked Questions

Can the GCD be larger than either number?

No. The GCD of two numbers cannot exceed the smaller of the two numbers. By definition, the GCD must divide both numbers evenly, so it must be less than or equal to each of them.

What is the GCD of two prime numbers?

If two numbers are both prime and different from each other, their GCD is always 1. Two numbers with a GCD of 1 are called coprime or relatively prime.

Does the formula GCD × LCM = a × b work for more than two numbers?

No, this formula only applies to two numbers. For three or more numbers, you must compute the GCD and LCM separately using the pairwise approach.

What is the difference between GCD and GCF?

They are the same thing. GCD stands for "Greatest Common Divisor" and GCF stands for "Greatest Common Factor." Different textbooks and regions use different terms, but the concept is identical.

How does the Euclidean algorithm handle negative numbers?

The GCD is always positive. When working with negative numbers, simply ignore the signs and apply the algorithm to the absolute values. GCD(−12, 18) = GCD(12, 18) = 6.