What is GCD (Greatest Common Divisor)?

GCD is the largest number that divides both input numbers without leaving a remainder. For example, GCD(12, 18) = 6, because 6 divides both 12 and 18.

What is LCM (Least Common Multiple)?

LCM is the smallest number that is a multiple of both input numbers. For example, LCM(12, 18) = 36, because 36 is the smallest number divisible by both 12 and 18.

What is the Euclidean algorithm?

The Euclidean algorithm is an efficient method to compute GCD by repeatedly dividing and taking remainders: GCD(a, b) = GCD(b, a mod b) until b = 0. It is much faster than prime factorization for large numbers.

How are GCD and LCM related?

They are related by the formula: GCD(a, b) × LCM(a, b) = a × b. This identity is useful for computing LCM once GCD is known.

What is GCD of two coprime numbers?

Coprime numbers (also called relatively prime) have a GCD of 1, meaning they share no common factors other than 1. For example, GCD(7, 11) = 1.

GCD and LCM Calculator

Free GCD and LCM calculator using the Euclidean algorithm. Find both the greatest common divisor and least common multiple with step-by-step breakdown.

Calculate the greatest common divisor and least common multiple of two numbers.

GCD (a, b) = Euclidean algorithm; LCM (a, b) = \frac{a \times b}{GCD ( a , b )}

Related calculators

Prime Factorization Calculator

Decompose any number into its prime factors and view the exponent notation.

Factorial Calculator — n! for Any Integer

Compute the factorial of any integer from 0 to 170, including large numbers using arbitrary precision.

Combinations & Permutations Calculator

Calculate nCr (combinations) and nPr (permutations) for any n and r instantly.

Percentage Calculator

Calculate percentages instantly: X% of Y, X is what % of Y, or percentage change.