GCD/LCM Calculator
Calculate the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of two or more numbers.
What is GCD (Greatest Common Divisor)?
GCD is the largest positive integer that divides all given numbers without leaving a remainder. It's also known as HCF (Highest Common Factor). For example, GCD(12, 18) = 6 because 6 is the largest number that divides both 12 and 18 evenly.
What is LCM (Least Common Multiple)?
LCM is the smallest positive integer that is divisible by all given numbers. For example, LCM(4, 6) = 12 because 12 is the smallest number that both 4 and 6 can divide into without remainder.
How does the Euclidean algorithm work for finding GCD?
The Euclidean algorithm finds GCD by repeatedly applying the division algorithm: divide the larger number by the smaller, replace the larger with the smaller and the smaller with the remainder, and repeat until the remainder is zero. The last non-zero remainder is the GCD. For example, to find GCD(48, 18): 48÷18=2 remainder 12, then 18÷12=1 remainder 6, then 12÷6=2 remainder 0, so GCD=6.
What is the relationship between GCD and LCM?
GCD and LCM are related by the formula: LCM(a,b) = |a×b| / GCD(a,b). This means if you know the GCD of two numbers, you can easily calculate their LCM, and vice versa. This relationship holds for any two positive integers.
Can I calculate GCD and LCM for more than two numbers?
Yes, you can calculate GCD and LCM for three or more numbers. For GCD, use the property: GCD(a,b,c) = GCD(GCD(a,b),c). For LCM, use: LCM(a,b,c) = LCM(LCM(a,b),c). Simply enter multiple numbers separated by commas.
What are the applications of GCD in mathematics?
GCD has many applications: simplifying fractions (dividing numerator and denominator by their GCD), solving Diophantine equations, finding modular inverses in cryptography, determining if two numbers are coprime (GCD=1), and in the Euclidean algorithm which is fundamental in number theory.
What are the applications of LCM in real life?
LCM is used in many real-life situations: finding when events will coincide (like bus schedules), adding or subtracting fractions with different denominators, scheduling recurring tasks, solving problems involving periodic phenomena, and in music for finding rhythmic patterns.
What does it mean if GCD equals 1?
If GCD(a,b) = 1, the numbers are called coprime or relatively prime. This means they share no common factors other than 1. For example, 8 and 15 are coprime because their only common divisor is 1. Coprime numbers are important in cryptography and number theory.
How do I find GCD using prime factorization?
To find GCD using prime factorization: (1) Find the prime factors of each number, (2) Identify the common prime factors, (3) For each common prime factor, take the lowest power, (4) Multiply these together. For example, 36=2²×3² and 48=2⁴×3¹, so GCD=2²×3¹=12.
How do I find LCM using prime factorization?
To find LCM using prime factorization: (1) Find the prime factors of each number, (2) For each prime factor that appears in any number, take the highest power, (3) Multiply these together. For example, 12=2²×3¹ and 18=2¹×3², so LCM=2²×3²=36.
Can GCD and LCM be calculated for negative numbers?
Yes, GCD and LCM are always positive integers regardless of the sign of the input numbers. The calculator uses the absolute values of the numbers. For example, GCD(-12, 18) = 6 and LCM(-4, 6) = 12.
What is the time complexity of the Euclidean algorithm?
The Euclidean algorithm has a time complexity of O(log(min(a,b))), making it very efficient even for very large numbers. It's one of the oldest and most efficient algorithms in mathematics, dating back to ancient Greece around 300 BC.
How is GCD used in fraction simplification?
To simplify a fraction, divide both the numerator and denominator by their GCD. For example, to simplify 24/36: GCD(24,36)=12, so 24÷12=2 and 36÷12=3, giving the simplified fraction 2/3. This ensures the fraction is in its lowest terms.
Can this calculator handle very large numbers?
Yes, this calculator can handle large integers efficiently using the Euclidean algorithm. However, extremely large numbers (hundreds of digits) may be limited by JavaScript's number precision. For most practical purposes, it works perfectly for numbers up to 15-16 digits.
How to Use GCD/LCM Calculator
Compute the greatest common divisor (GCD) and least common multiple (LCM) of two or more numbers right in your browser. All calculations run locally, so nothing is uploaded.
- Type your numbers into the 'Numbers (Separated by line, comma or space)' field, for example 12, 18, 24.
- Pick a 'Separator Type:' option — Auto Detect, New Line, Comma or Space — or leave it on Auto Detect to let the tool decide.
- Read the GCD and LCM results, which update automatically as you edit the input.
- Enable 'Use Absolute Values' if your list contains negative numbers, so factors are computed from their magnitudes.
- Add more numbers on new lines to compare GCD and LCM across a larger set.
The GCD is useful for simplifying fractions, while the LCM helps you find a common denominator or align repeating cycles.
Related Tools
- Prime Number Checker Check if a number is prime instantly. Find prime factors, nearest primes, and the nth prime number online.
- Factorial Calculator Calculate n! instantly for any non-negative integer. Free online factorial calculator with BigInt support for arbitrarily large results.
- Calorie Calculator Free calorie calculator. Find your BMR and daily calorie needs (TDEE), plus target calories for weight loss or gain with a protein, carb and fat breakdown - works offline in your browser.
- Math Expression Calculator Evaluate complex math expressions online with variables, 20+ functions, and real-time calculations. Perfect for algebra, trigonometry, and scientific computing.
- Arithmetic Sequence Calculator Calculate nth term, sum, and generate complete arithmetic sequences instantly. Free online tool with 100% privacy - all calculations happen locally in your browser.
- Fibonacci Generator Generate Fibonacci numbers and sequences instantly. Calculate the nth Fibonacci number or generate a full sequence with BigInt support for arbitrarily large numbers.
- Loan Calculator Calculate monthly loan payments, total interest, and view amortization schedule. Supports equal payment and equal principal methods for mortgages, auto loans, and personal loans.
- Discount Calculator Calculate discounted prices, savings, and final cost. Supports percentage and fixed amount discounts with tax.