Home / Tools / GCD & LCM Calculator
Math & Algebra Calculator

Least Common Multiple & GCD Calculator

Find the Greatest Common Divisor (GCD / GCF) and Least Common Multiple (LCM) for two or more numbers. Features complete step-by-step Euclidean division, prime factorization trees, and fraction simplification.

Comma, space, or semicolon separated
Presets:
Greatest Common Divisor (GCD / GCF)
6
The largest factor dividing all numbers evenly
Least Common Multiple (LCM)
36
The smallest positive multiple shared by all numbers
Fraction Simplification (via GCD): 12 / 18 = 2 / 3
Least Common Denominator (LCD = LCM): 1/12 + 1/18 = (3 + 2) / 36 = 5/36

Euclidean Algorithm Step-by-Step

The Euclidean Algorithm repeatedly computes remainder a mod b until the remainder is zero:

Therefore, GCD = 6. Using the formula LCM(a, b) = (a × b) / GCD(a, b): LCM = (12 × 18) / 6 = 216 / 6 = 36.

What is the Least Common Multiple (LCM)?

The Least Common Multiple (LCM)—sometimes called the lowest common multiple or smallest common multiple—of two or more non-zero integers is the smallest positive integer that is an exact multiple of all given numbers. In other words, it is the lowest number that can be divided by each of the inputs without leaving any remainder.

The most important real-world mathematical application of the LCM is finding the Least Common Denominator (LCD) when adding or subtracting fractions with unlike denominators. For example, to evaluate 1/12 + 1/18, you find the LCM of 12 and 18 (which is 36) to rewrite the fractions with equal denominators: 3/36 + 2/36 = 5/36.

What is the Greatest Common Divisor (GCD / GCF)?

The Greatest Common Divisor (GCD)—also universally known as the Greatest Common Factor (GCF), highest common factor (HCF), or greatest common denominator—is the largest positive integer that divides each of the numbers with a remainder of zero.

The GCD is essential for simplifying algebraic expressions, reducing fractions to their irreducible lowest terms, and cryptography algorithms (including the RSA public-key cryptosystem and Diffie-Hellman key exchange).

How to Calculate GCD and LCM: Comparison of Methods

Calculation Method Best Used For Computational Complexity How It Works
Euclidean Algorithm Large numbers & programming O(log(min(a, b))) — Extremely Fast Divides larger number by smaller and takes remainder until zero is reached.
Prime Factorization School algebra & teaching Requires finding prime factors Expresses numbers as prime powers: GCD takes min exponents, LCM takes max exponents.
Listing Method Small numbers (under 50) Manual inspection Lists factors to find the largest common one; lists multiples to find the smallest common one.

The Fundamental Mathematical Formula Linking GCD and LCM

For any two positive integers a and b, their greatest common divisor and least common multiple are directly linked by an elegant theorem:

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

Because of this identity, once you compute the GCD using Euclid's algorithm, calculating the LCM requires only a single multiplication and division:

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

LCM and GCD Quick Reference Chart

Number Pair Greatest Common Divisor (GCD) Least Common Multiple (LCM) Prime Factorization Breakdown
12 and 18 6 36 12 = 2² × 3  |  18 = 2 × 3²
8 and 12 4 24 8 = 2³  |  12 = 2² × 3
15 and 25 5 75 15 = 3 × 5  |  25 = 5²
24 and 36 12 72 24 = 2³ × 3  |  36 = 2² × 3²
14 and 21 7 42 14 = 2 × 7  |  21 = 3 × 7
48 and 180 12 720 48 = 2⁴ × 3  |  180 = 2² × 3² × 5

Frequently Asked Questions

What is the difference between GCD and LCM? ▾
The Greatest Common Divisor (GCD) is the highest integer that divides into all given numbers without a remainder. The Least Common Multiple (LCM) is the smallest number that is a multiple of all given numbers. For example, for 12 and 18, the GCD is 6 and the LCM is 36.
How do you calculate LCM and GCD step-by-step? ▾
Using prime factorization: 1) Find the prime factors of each number. 2) For the GCD, multiply the common prime factors using their lowest exponents. 3) For the LCM, multiply all prime factors from both numbers using their highest exponents.
Is greatest common denominator the same as greatest common divisor? ▾
Yes, "greatest common denominator" is simply another common name for the Greatest Common Divisor (GCD) or Greatest Common Factor (GCF), specifically used when simplifying fractions to reduce numerators and denominators to lowest terms.
Can you find the GCD and LCM of three or more numbers? ▾
Yes. For three numbers (a, b, c), first calculate the GCD of the first two: g = GCD(a, b). Then compute the GCD of that result and the third: GCD(g, c). The same associative rule applies for LCM: LCM(a, b, c) = LCM(LCM(a, b), c).
How do you find the Least Common Denominator (LCD)? ▾
The Least Common Denominator (LCD) of two or more fractions is exactly equal to the Least Common Multiple (LCM) of their denominators. By converting each fraction to this common denominator, you can easily add or subtract them.
What happens if the GCD of two numbers is 1? ▾
When two numbers have a GCD of 1, they are called coprime or relatively prime (e.g., 8 and 9). When two numbers are coprime, their LCM is simply their direct product: LCM(a, b) = a * b.

More Free Math & Developer Tools

Frequency Converter

Convert Hz, kHz, MHz, and GHz, and calculate wavelength to frequency in meters.

Morse Code Translator

Convert text, binary, and hex to Morse code with live audio oscillator sound playback.

Time Card Calculator

Calculate total employee work hours, overtime, and gross paycheck payroll.

Glitch Text Generator

Create cursed Zalgo text, creepy void characters, and cyber matrix glitch effects.
Copied to clipboard!