GCD & LCM Calculator
Enter two integers to get Greatest Common Divisor and Least Common Multiple.
Back to all tools on ToolForge
Number A
Number B
Result
GCD:
LCM:
About GCD & LCM Calculator
This GCD and LCM calculator finds the greatest common divisor and least common multiple for two integers.
It is useful for simplifying fractions, comparing repeating cycles and solving number problems where shared factors or common multiples matter.
Euclidean Algorithm Implementation
// Euclidean algorithm for GCD
function gcd(a, b) {
return b ? gcd(b, a % b) : Math.abs(a);
}
// Example trace: gcd(48, 18)
// gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) → 6
// LCM using GCD relationship
function lcm(a, b) {
return Math.abs(a * b) / gcd(a, b);
}
// Time complexity: O(log min(a,b))
GCD and LCM Examples
| Numbers | GCD | LCM | Product Check |
|---|---|---|---|
| 12, 18 | 6 | 36 | 12×18 = 6×36 = 216 |
| 24, 36 | 12 | 72 | 24×36 = 12×72 = 864 |
| 15, 25 | 5 | 75 | 15×25 = 5×75 = 375 |
| 7, 13 | 1 | 91 | 7×13 = 1×91 = 91 (coprime) |
| 48, 60 | 12 | 240 | 48×60 = 12×240 = 11520 |
Prime Factorization Method
// For a = 60 = 2² × 3 × 5 // For b = 48 = 2⁴ × 3 // GCD: Take lowest power of common primes // gcd = 2² × 3 = 12 // LCM: Take highest power of all primes // lcm = 2⁴ × 3 × 5 = 240
Frequently Asked Questions
- What is the Euclidean algorithm for finding GCD?
- The Euclidean algorithm finds GCD by repeated division: gcd(a,b) = gcd(b, a mod b), continuing until remainder is 0. Example: gcd(48,18) = gcd(18,48 mod 18) = gcd(18,12) = gcd(12,6) = gcd(6,0) = 6. This method is efficient with O(log min(a,b)) time complexity.
- How is LCM calculated using GCD?
- LCM is calculated using the formula: lcm(a,b) = |a×b| / gcd(a,b). This relationship exists because the product of two numbers equals the product of their GCD and LCM. Example: lcm(12,18) = (12×18)/6 = 36. This avoids listing multiples and is computationally efficient.
- What is prime factorization method for GCD and LCM?
- Prime factorization breaks numbers into prime factors. For GCD, take the lowest power of each common prime. For LCM, take the highest power of each prime. Example: 60 = 2²×3×5, 48 = 2⁴×3. GCD = 2²×3 = 12, LCM = 2⁴×3×5 = 240.
- What are coprime (relatively prime) numbers?
- Two numbers are coprime if their GCD is 1, meaning they share no common factors other than 1. Example: 8 and 15 are coprime (gcd=1) even though neither is prime. Consecutive integers are always coprime. For coprime a,b: lcm(a,b) = a×b.
- What are common use cases for GCD and LCM?
- GCD is used for: simplifying fractions, dividing items into equal groups, finding largest tile size for flooring. LCM is used for: finding common denominators, scheduling repeating events, gear rotation synchronization, adding periodic tasks with different cycles.
- How do you handle negative numbers in GCD/LCM calculations?
- GCD is always positive by convention. gcd(-a,b) = gcd(a,b) = gcd(a,-b). The algorithm uses absolute values. LCM is also typically expressed as positive. Most calculators return gcd(-48,18) = 6 and lcm(-12,18) = 36, treating inputs as their absolute values.