GCD & LCM Calculator
Find greatest common divisor and least common multiple using the Euclidean algorithm.
About the GCD & LCM Calculator
The greatest common divisor (GCD) of two integers is the largest positive integer that divides both without remainder. The least common multiple (LCM) is the smallest positive integer that both divide without remainder. The two are linked by the identity gcd(a,b) * lcm(a,b) = |a*b|, so once you have one, the other is a single division away.
The GCD is computed using the Euclidean algorithm, first described in Euclid's Elements Book VII Proposition 2 (circa 300 BCE). The algorithm works by repeatedly replacing the larger number with the remainder of the division, until the remainder is zero. The last non-zero remainder is the GCD. Per Lame's theorem (1844), the algorithm always terminates within 5 times the number of decimal digits of the smaller input, so it is fast even for very large numbers.
GCD and LCM appear throughout mathematics and engineering. Adding fractions requires the LCM of the denominators to find a common denominator. Cryptographic key generation uses the GCD to verify that two large numbers are coprime. Mechanical engineers use the LCM to compute gear tooth counts that mesh without slipping. Music theorists use the GCD to find the greatest common measure of two rhythmic patterns.
The tool accepts any integers, including negative ones (the result is always non-negative, since divisibility does not depend on sign). It rejects the input pair (0, 0) because GCD(0,0) is mathematically undefined — every integer divides zero, so there is no greatest such integer.
How It Works
The Euclidean algorithm rests on the observation that if a and b are integers with b non-zero, then gcd(a, b) = gcd(b, a mod b). Repeatedly applying this identity reduces the pair until one of them becomes zero, at which point the other is the GCD:
function gcd(a, b) {
a = |a|; b = |b|;
while (b != 0) {
const t = b;
b = a mod b;
a = t;
}
return a;
}The LCM is then computed directly from the GCD using the identity lcm(a, b) = |a*b| / gcd(a, b). This is much faster than enumerating multiples of each input until they coincide, especially for large numbers.
For example, with a = 84 and b = 60, the Euclidean algorithm runs: gcd(84, 60) = gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12. Four iterations suffice, and Lame's bound (5 * 2 = 10 iterations, since 60 has two digits) is not approached.
The tool handles the edge case where one input is zero: gcd(a, 0) = |a| by convention, since every integer divides zero. The other edge case, gcd(0, 0), is undefined because every integer divides zero, so there is no greatest such integer — the tool reports this explicitly.
Worked Examples
Using the default values 84 and 60, the algorithm computes gcd(84, 60) = 12. The LCM is |84 * 60| / 12 = 5040 / 12 = 420. You can verify both: 84 = 2^2 * 3 * 7, 60 = 2^2 * 3 * 5, so GCD = 2^2 * 3 = 12 and LCM = 2^2 * 3 * 5 * 7 = 420.
For two coprime numbers, say 17 and 23 (both prime), the algorithm runs through all remainders and returns gcd = 1. The LCM is 17 * 23 = 391, the product of the inputs. This confirms the rule that for coprime numbers, gcd = 1 and lcm = a * b.
For numbers with a large common factor, like 1000 and 750, the algorithm returns gcd = 250 in just two iterations: gcd(1000, 750) = gcd(750, 250) = gcd(250, 0) = 250. The LCM is 1000 * 750 / 250 = 3000, much smaller than the product 750,000. The tool performs both the GCD and the LCM in constant time relative to the inputs.
When to Use This Tool
Use the GCD and LCM calculator when you need to:
- Find a common denominator when adding or subtracting fractions.
- Verify that two numbers are coprime (gcd = 1) for cryptographic key generation.
- Compute the least common multiple of cycle times in scheduling or signal processing.
- Determine the smallest shared grid size for two interlocking patterns in graphic design.
- Reduce a fraction to lowest terms by dividing top and bottom by the GCD.
- Find the lowest frequency at which two periodic events coincide (a property used in beat frequencies).
- Teach the Euclidean algorithm and Lame's theorem in a number-theory course.
Limitations & Disclaimer
This calculator works on two integers at a time and uses IEEE 754 double-precision arithmetic. Inputs above 2^53 may lose precision because JavaScript Number cannot represent every integer above that bound; use BigInt-based tools for cryptographic-size numbers. The tool rejects the input pair (0, 0) as mathematically undefined. For multi-argument GCD/LCM, compute pairwise. See our disclaimer for full details.
Frequently Asked Questions
What is the difference between GCD and LCM?
GCD is the largest integer that divides both inputs without remainder, while LCM is the smallest integer that both inputs divide without remainder. They are linked by the identity gcd(a, b) * lcm(a, b) = |a * b|. For 12 and 18, GCD = 6 and LCM = 36, and 6 * 36 = 216 = 12 * 18.
How does the Euclidean algorithm work?
It repeatedly replaces the larger number with the remainder when divided by the smaller, until the remainder is zero. The last non-zero remainder is the GCD. Euclid described it geometrically in Elements Book VII Proposition 2 around 300 BCE; today the same algorithm runs in software.
What happens if one of the inputs is zero?
By convention, gcd(a, 0) = |a|, since every integer divides zero. LCM(a, 0) is 0, since zero is the smallest common multiple. The exception is gcd(0, 0), which is undefined because every integer divides zero and there is no greatest such integer; the tool reports this as an error.
Does the calculator handle negative inputs?
Yes. The calculator takes the absolute value of each input at the start, because divisibility does not depend on sign. gcd(-84, 60) returns 12, the same as gcd(84, 60). The LCM is similarly returned as a positive value.
What is Lame's theorem?
Lame's theorem (1844) states that the Euclidean algorithm terminates in at most 5 times the number of decimal digits of the smaller input. For 100-digit numbers, that is at most 500 iterations. In practice, the average number of iterations is much smaller, around 12 times the natural log of the smaller input.
How is the LCM derived from the GCD?
Using the identity lcm(a, b) = |a * b| / gcd(a, b). This is far faster than the naive method of listing multiples of each input until they coincide. For very large numbers, multiplication may overflow IEEE 754 doubles; for inputs above 2^53, use a BigInt-based GCD instead.
Last updated: September 9, 2026 · Author: HT99 Tools Editorial Team