GCD/LCM Calculator
Calculate greatest common divisor (GCD) and least common multiple (LCM) of two or more integers with prime factorization
Enter at least two integers and click 'Calculate GCD/LCM' to start
Euclidean Algorithm
Classical algorithm for calculating GCD of two numbers, based on the principle: gcd(a, b) = gcd(b, a mod b). High efficiency with time complexity O(log min(a, b)).
Extend to Multiple Numbers
GCD of multiple numbers can be calculated by successive pairwise GCD: gcd(a, b, c) = gcd(gcd(a, b), c). Same for LCM: lcm(a, b, c) = lcm(lcm(a, b), c).
GCD and LCM Relationship
For two positive integers a and b: gcd(a, b) × lcm(a, b) = a × b. This relationship can be used to verify calculation correctness.
Your Privacy is Protected
All calculations run locally in your browser. We do not store or transmit your data.
What are GCD and LCM?
GCD (Greatest Common Divisor) is the largest number that divides two or more numbers evenly. For 12 and 18, the divisors of 12 are {1,2,3,4,6,12}and of 18 are {1,2,3,6,9,18} — the largest shared one is 6, so GCD(12, 18) = 6.
LCM (Least Common Multiple) is the smallest number that is a multiple of two or more numbers. The multiples of 4 are {4,8,12,16,20,...} and of 6 are {6,12,18,24,...} — the smallest shared one is 12, so LCM(4, 6) = 12.
These two concepts are two sides of the same coin, and they are the backbone of working with fractions: GCD lets you simplify fractions, and LCM lets you add and subtract fractions with different denominators.
How to Calculate GCD and LCM
The fastest way to find the GCD is the Euclidean algorithm:
Repeatedly: larger = remainder of larger ÷ smaller, until remainder = 0
Example — GCD(48, 18):
48 ÷ 18 → r 12 → 18 ÷ 12 → r 6 → 12 ÷ 6 → r 0 → GCD = 6
Example — LCM(4, 6) using the relationship:
LCM = (4 × 6) ÷ GCD(4,6) = 24 ÷ 2 = 12
Key tip: Use the identity GCD × LCM = a × b — once you have the GCD (via the Euclidean algorithm), the LCM is one division away. No need to list multiples.
Common Use Cases
Simplifying fractions — To reduce 12/18, divide both by their GCD (6) to get ⅔. GCD is the tool that makes fraction simplification automatic.
Adding fractions — To add ⅓ + ¼, the common denominator is the LCM of 3 and 4, which is 12. LCM turns messy fraction addition into a clean process.
Scheduling and cycles — Two events that repeat every 12 and 18 minutes will coincide every LCM(12, 18) = 36 minutes. Used in traffic lights, manufacturing, and planetary alignments.
Cryptography — The RSA algorithm uses modular arithmetic built on GCD, and the Euclidean algorithm is used to find the modular inverse needed for decryption.
Frequently Asked Questions
What is the GCD (Greatest Common Divisor)?
The GCD of two or more numbers is the largest number that divides all of them evenly (with no remainder). For example, the GCD of 12 and 18 is 6, because 6 is the largest number that divides both 12 and 18 without a remainder. GCD is also called GCF (Greatest Common Factor) or HCF (Highest Common Factor).
What is the LCM (Least Common Multiple)?
The LCM of two or more numbers is the smallest number that is a multiple of all of them. For example, the LCM of 4 and 6 is 12, because 12 is the smallest number divisible by both 4 and 6. LCM is essential for adding fractions with different denominators — the common denominator is the LCM of the original denominators.
How do I find the GCD using the Euclidean algorithm?
The Euclidean algorithm finds the GCD by repeatedly replacing the larger number with the remainder of dividing the two numbers, until the remainder is 0. For GCD(48, 18): 48 ÷ 18 = 2 remainder 12, then 18 ÷ 12 = 1 remainder 6, then 12 ÷ 6 = 2 remainder 0. The last non-zero remainder (6) is the GCD. This method is fast and works for any pair of numbers.
How are GCD and LCM related?
For any two numbers a and b, GCD(a, b) × LCM(a, b) = a × b. So once you know the GCD, you can find the LCM instantly: LCM = (a × b) ÷ GCD. For example, for 12 and 18: GCD = 6, so LCM = (12 × 18) ÷ 6 = 216 ÷ 6 = 36. This relationship means you never need to calculate both separately.
When would I use GCD and LCM in real life?
LCM is used whenever you need to sync repeating cycles — for example, two traffic lights that cycle every 60 and 90 seconds will align every LCM(60, 90) = 180 seconds. GCD is used to simplify fractions (divide numerator and denominator by their GCD) and to divide items into equal groups without leftovers. Both appear in scheduling, music theory, and engineering.