mode

GCD and LCM Calculator

Find the GCD and LCM of two integers using prime factorization with a Venn diagram.

Back to Prime Factorization Calculator

Prime Factorization Tips

Click to show tips

Try an Example

Pick a scenario to see how the calculator works, then adjust the values

Highly Composite Number

Factor 360, a highly composite number with many divisors.

Key values: 360 = 2^3 x 3^2 x 5 · 24 divisors · phi(360) = 96

Large Prime

Check if 7919 is prime (it is -- the 1000th prime number).

Key values: 7919 is prime · 2 divisors · phi(7919) = 7918

GCD and LCM

Compute the GCD and LCM of 84 and 120.

Key values: 84 = 2^2 x 3 x 7 · 120 = 2^3 x 3 x 5 · GCD = 12, LCM = 840

Documentation

GCD and LCM via Prime Factorization

Once you have the prime factorizations of two numbers, GCD and LCM follow directly:

\gcd(a, b) = \prod p^{\min(e, f)}

Take each shared prime at the minimum exponent.

\text{lcm}(a, b) = \prod p^{\max(e, f)}

Take every prime (from either number) at the maximum exponent.

The Fundamental Identity

\gcd(a, b) \times \text{lcm}(a, b) = |a \times b|

This identity means you only need to compute one (GCD or LCM) and derive the other. Euclid's algorithm computes GCD in $O(\log \min(a,b))$ time without needing factorization.

Practical Examples

Simplifying Fractions

To simplify 48/180: factor $48 = 2^4 \times 3$ and $180 = 2^2 \times 3^2 \times 5$ . $\gcd = 2^2 \times 3 = 12$ . Divide both by 12: $48/180 = 4/15$ .

Scheduling Problems

Two buses arrive every 12 and 18 minutes. When do they coincide? $\text{lcm}(12, 18) = 36$ minutes.

Gear Ratio Simplification

Gears with 24 and 36 teeth: $\gcd(24, 36) = 12$ . Simplest ratio: 2:3.

Frequently Asked Questions

What is the difference between GCD and LCM?

The GCD (Greatest Common Divisor) is the largest number that divides both integers evenly. The LCM (Least Common Multiple) is the smallest positive number that both integers divide into evenly. For 12 and 18: GCD = 6, LCM = 36.

How do you find GCD using prime factorization?

Factor both numbers into primes, then take each shared prime at its minimum exponent. For example, $48 = 2^4 \times 3$ and $180 = 2^2 \times 3^2 \times 5$ . The shared primes are 2 and 3, so $\gcd = 2^2 \times 3 = 12$ .

How do you find LCM using prime factorization?

Factor both numbers into primes, then take every prime (from either number) at its maximum exponent. For $12 = 2^2 \times 3$ and $18 = 2 \times 3^2$ : $\text{lcm} = 2^2 \times 3^2 = 36$ .

What is the relationship between GCD and LCM?

For any two positive integers $a$ and $b$ , $\gcd(a, b) \times \text{lcm}(a, b) = a \times b$ . This identity lets you compute one from the other. For example, $\gcd(12, 18) = 6$ and $\text{lcm}(12, 18) = 36$ , and $6 \times 36 = 216 = 12 \times 18$ .

When are two numbers coprime?

Two numbers are coprime (or relatively prime) when their GCD is 1, meaning they share no common prime factors. For example, 8 and 15 are coprime because $8 = 2^3$ and $15 = 3 \times 5$ share no primes. A fraction $a/b$ is already in lowest terms when $a$ and $b$ are coprime.

More Math Calculators

Explore the category

Absolute Value Calculator

Area Calculator

Circle Calculator

Percentage Calculator

Pythagorean Theorem Calculator

Unit Circle Explorer