GCD & LCM Calculator
Find the greatest common divisor and least common multiple of any numbers.
Reviewed by the ToolNestr Editorial Team — July 2026
Euclidean algorithm for GCD
The Euclidean algorithm is one of the oldest algorithms still in common use, dating back to ancient Greece (circa 300 BC). It computes the greatest common divisor of two numbers efficiently using repeated division. The algorithm is based on the observation that the GCD of two numbers does not change if the larger number is replaced by its remainder when divided by the smaller number.
Formally, for integers a and b where a > b:
The algorithm repeats the modulo operation until the remainder is zero. The last non-zero remainder is the GCD. For n numbers, compute pairwise using reduce.
Worked example: GCD(12, 18)
Step 1: 18 ÷ 12 = 1 remainder 6 gcd(12, 18) → gcd(12, 6)
Step 2: 12 ÷ 6 = 2 remainder 0 gcd(12, 6) → gcd(6, 0)
Last non-zero remainder = 6 → GCD = 6
LCM = (12 × 18) / GCD = 216 / 6 = 36
Simplifying Fractions
To reduce a fraction to its simplest form, divide numerator and denominator by their GCD. For example, 12/18 simplified by GCD 6 gives 2/3.
Scheduling & Cycles
LCM helps determine when repeating events align. If one machine runs every 12 minutes and another every 18 minutes, they both run together every LCM(12, 18) = 36 minutes.
Number Theory
GCD and LCM are foundational in number theory. The relationship GCD × LCM = product of numbers is a key identity used in proofs and problem-solving.
Gear Ratios
In mechanical engineering, LCM of gear teeth counts determines when gears return to their starting alignment. GCD helps find the simplest ratio between two gears.
GCD and LCM relationship
For any two positive integers a and b, the product of their GCD and LCM equals the product of the numbers themselves:
This identity allows you to compute LCM directly from GCD: LCM = (a × b) / GCD(a, b). For three or more numbers, the relationship generalises but becomes more complex — the simple product identity only holds pairwise.
The proof follows from prime factorisation. Each prime factor appears in both GCD and LCM: the GCD takes the minimum exponent across all numbers, while the LCM takes the maximum exponent. When you multiply GCD and LCM, you get the full product because min(e) + max(e) = e1 + e2 for each prime across two numbers.
How to use the GCD & LCM Calculator
Enter numbers
Type two or more positive integers separated by commas, e.g. "12, 18, 24".
Choose calculation
Click "Calculate GCD" to find the greatest common divisor, "Calculate LCM" for the least common multiple, or "Calculate Both".
Review steps
For two numbers, the step-by-step breakdown of the Euclidean algorithm is shown. Prime factorisation is displayed when numbers are 100 or less.
Tips for working with GCD and LCM
The distributive property
GCD and LCM distribute over each other: GCD(a, LCM(b, c)) = LCM(GCD(a, b), GCD(a, c)). Similarly, LCM(a, GCD(b, c)) = GCD(LCM(a, b), LCM(a, c)). These are known as the distributive laws of GCD and LCM and mirror the distributive property in Boolean algebra.
GCD of more than two numbers
To find the GCD of three or more numbers, compute the GCD pairwise using reduce: GCD(a, b, c) = GCD(GCD(a, b), c). The order does not matter — GCD is associative and commutative. The same approach works for LCM. This calculator extends to n numbers automatically.
Coprime numbers
Two numbers are called coprime (or relatively prime) if their GCD is 1. For example, 8 and 15 are coprime because their only common factor is 1. When two numbers are coprime, their LCM is simply their product. Coprime pairs are essential in cryptography and modular arithmetic.
Efficiency of the Euclidean algorithm
The Euclidean algorithm is remarkably efficient. The number of division steps grows logarithmically with the size of the input numbers. In the worst case (consecutive Fibonacci numbers), the number of steps is still proportional to the number of digits. This makes it practical even for extremely large numbers used in cryptography.
Understanding the Euclidean algorithm in depth
The Euclidean algorithm works because of a simple observation: any common divisor of a and b also divides their difference a − b. By repeatedly applying this with the modulo operation (which is essentially repeated subtraction), we reduce the problem to smaller and smaller numbers until one reaches zero.
The extended Euclidean algorithm is an important variant that, in addition to finding the GCD, also finds integers x and y such that ax + by = GCD(a, b). This is known as Bézout's identity and is used in solving linear Diophantine equations and computing modular inverses in RSA encryption.
Historically, the Euclidean algorithm is one of the earliest algorithms ever formally described. Euclid included it in his Elements (Book VII, Propositions 1-3) around 300 BC. The algorithm predates the concept of modular arithmetic by over two millennia, yet it remains the most efficient way to compute GCD even on modern computers.
Related tools
Frequently asked questions
What is GCD?
The greatest common divisor is the largest number that divides all given numbers without a remainder.
What is LCM?
The least common multiple is the smallest positive number that is a multiple of all given numbers.
How do you compute GCD?
Euclidean algorithm: repeatedly replace the larger number with its remainder modulo the smaller.
How are GCD and LCM related?
For two numbers a and b: GCD(a,b) × LCM(a,b) = a × b.