GCD/LCM Calculator: Find the Greatest Common Divisor and Least Common Multiple

Finding the greatest common divisor (GCD) and least common multiple (LCM) shows up more often than you might expect — from simplifying fractions in homework to scheduling recurring events in software. Our calculator gives you both results instantly using the Euclidean algorithm, the same method mathematicians have trusted for over two thousand years.

What Are GCD and LCM?

Greatest Common Divisor (GCD)

The GCD of two or more integers is the largest positive integer that divides each of them without a remainder. It is also called the greatest common factor (GCF) or highest common factor (HCF).

GCD(12, 18) = 6

Divisors of 12: 1, 2, 3, 4, 6, 12
Divisors of 18: 1, 2, 3, 6, 9, 18
Common divisors: 1, 2, 3, 6
Greatest: 6

Least Common Multiple (LCM)

The LCM of two or more integers is the smallest positive integer that is divisible by each of them. Think of it as the first point where their multiples overlap.

LCM(4, 6) = 12

Multiples of 4: 4, 8, 12, 16, 20, ...
Multiples of 6: 6, 12, 18, 24, ...
First common multiple: 12

The Relationship Between GCD and LCM

GCD and LCM are directly connected by a simple formula:

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

Example:
GCD(12, 18) = 6
LCM(12, 18) = 36
6 * 36 = 216 = 12 * 18

This means once you know the GCD, you can derive the LCM without listing all multiples.

The Euclidean Algorithm

The Euclidean algorithm is an efficient method for computing the GCD. Described by Euclid around 300 BC, it remains one of the oldest algorithms still in widespread use.

How It Works

The algorithm repeatedly replaces the larger number with the remainder of dividing the two numbers, until the remainder is zero. The last non-zero remainder is the GCD.

GCD(48, 18):
  48 = 2 * 18 + 12
  18 = 1 * 12 + 6
  12 = 2 * 6  + 0
  GCD = 6

Why It’s Fast

Listing all divisors to find the GCD would take time proportional to the smaller number. The Euclidean algorithm runs in time proportional to the number of digits, making it dramatically faster for large numbers. It can compute the GCD of numbers with thousands of digits in milliseconds.

Common Use Cases

Simplifying Fractions

To reduce a fraction to its simplest form, divide both the numerator and denominator by their GCD:

Fraction: 48/60
GCD(48, 60) = 12
Simplified: 48/12 / 60/12 = 4/5

Scheduling and Timing

LCM helps determine when periodic events will coincide:

Traffic lights: If one light cycles every 40 seconds and another every 60 seconds, they align every LCM(40, 60) = 120 seconds.
Shift schedules: Two employees with different rotation lengths meet on the same shift every LCM of their rotation periods.
Maintenance windows: Systems with different service intervals need joint downtime at LCM intervals.

Working with Ratios

When scaling recipes, materials, or any proportional quantities, the GCD tells you the base ratio:

Ingredients: 750g flour, 500g sugar
GCD(750, 500) = 250
Base ratio: 3:2

Programming and Computer Science

GCD appears in cryptographic algorithms (RSA key generation), computing modular inverses, reducing aspect ratios for displays, and generating hash table sizes. The gcd function is built into many standard libraries precisely because it comes up so often.

How to Use Our GCD/LCM Calculator

Enter two or more numbers into the input fields
View the GCD and LCM computed in real time
See the steps of the Euclidean algorithm broken down for each computation
Copy the results with one click

Tips

Enter whole positive integers for meaningful results
The tool handles large numbers without difficulty because the Euclidean algorithm scales well
Use the step-by-step breakdown to understand or verify the computation
All calculations run locally in your browser — nothing is sent to a server

Quick Reference Table

a	b	GCD	LCM
12	8	4	24
15	25	5	75
7	13	1	91
100	75	25	300
36	48	12	144

When the GCD is 1, the two numbers are called coprime (or relatively prime). Their LCM is simply their product.

Frequently Asked Questions

What if one of the numbers is zero? The GCD of any number and zero is the number itself: GCD(n, 0) = n. The LCM of any number and zero is zero: LCM(n, 0) = 0. This follows directly from the definitions.

Can I find the GCD of more than two numbers? Yes. Compute the GCD of the first two numbers, then find the GCD of that result with the third number, and continue. The same approach works for LCM: GCD(a, b, c) = GCD(GCD(a, b), c).

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. HCF (Highest Common Factor) is another name used in some countries.

Is the Euclidean algorithm the fastest method? For typical inputs, yes. A binary GCD algorithm avoids division operations and can be faster on hardware that handles bit shifts efficiently, but the classical Euclidean algorithm is optimal for general-purpose computation and is what most standard libraries implement.

Try our free GCD/LCM Calculator to find the greatest common divisor and least common multiple instantly.