GCD & LCM Calculator
Find the Greatest Common Divisor and Least Common Multiple of two or more numbers with step-by-step working.
About the GCD & LCM Calculator
The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) are foundational number theory concepts with surprisingly broad practical applications: simplifying fractions (use GCD), synchronizing repeating events (use LCM), and optimizing packaging or cutting problems (use GCD). The Euclidean algorithm finds GCD efficiently for any two numbers.
GCD and LCM
GCD(a,b): Euclidean algorithm - repeatedly replace (a,b) with (b, a mod b) until b=0 ยท LCM(a,b) = (a ร b) / GCD(a,b)
GCD(48, 36): 48 mod 36 = 12, 36 mod 12 = 0 โ GCD = 12 ยท LCM(48, 36) = (48ร36)/12 = 144 ยท GCD = 1 means the numbers are coprime (no common factors)
Worked Example
Two buses leave a stop at the same time. Bus A every 15 min, Bus B every 20 min. When do they next leave together?
LCM(15, 20) = 60 minutes ยท Both buses next depart together after 60 minutes
Tips & Insights
- 1
GCD is used to reduce fractions to lowest terms - divide both numerator and denominator by GCD(numerator, denominator). GCD(36, 48) = 12, so 36/48 simplifies to 3/4.
- 2
LCM is used to find the common denominator when adding or subtracting fractions. For 1/6 + 1/4, LCM(6,4) = 12, so the sum is 2/12 + 3/12 = 5/12.
- 3
In manufacturing, LCM determines when two production cycles next coincide - useful for maintenance scheduling. If machine A needs servicing every 8 hours and machine B every 12 hours, LCM(8,12) = 24 hours tells you when both need service at the same time.
- 4
RSA encryption relies on the difficulty of factoring large numbers. Key generation requires GCD(e, ฯ(n)) = 1 (coprime check). Euclid's GCD algorithm, used here, is one of the oldest known algorithms - predating modern computing by over 2,000 years yet still used in every cryptographic library today.
- 5
For packaging problems, GCD gives the largest equal group. If you have 36 red and 48 blue marbles to pack into identical bags with no leftovers, each bag gets GCD(36,48) = 12 marbles - 3 red and 4 blue. This is the optimal pack size.
- 6
GCD of two consecutive integers is always 1 (they are always coprime). GCD(n, n+1) = 1 for any n. This is why consecutive years never share the same 'special calendar pattern' in the way non-consecutive years might.
- 7
LCM is directly related to GCD via LCM(a,b) = (a ร b) / GCD(a,b). This relationship means you only need to compute GCD to get LCM - and the Euclidean algorithm for GCD is extremely fast even for very large numbers.
Why this matters for you
GCD and LCM solve real scheduling, packing, and synchronization problems. Beyond textbook exercises, they appear in computer science (memory alignment, hash table sizing), music theory (rhythmic patterns and time signatures), and event planning (when multiple recurring events next coincide). The Euclidean algorithm for GCD is one of the oldest algorithms in mathematics and remains efficient on modern hardware.
In Indian school exams (CBSE, ICSE, and state boards), HCF and LCM are among the most consistently tested topics from Class 5 through Class 10. Many students memorise the prime factorisation method without understanding the faster Euclidean algorithm or the relationship LCM = (aรb)/GCD. Understanding the relationship means you only need one algorithm, not two separate procedures.
Software engineers use GCD and LCM routinely: computing aspect ratios (GCD of width and height gives the simplest ratio), memory alignment (DRAM burst lengths must be multiples of power-of-2 sizes), and scheduling (cron jobs with different intervals next fire simultaneously at their LCM interval). Having a fast calculator for these avoids the small arithmetic errors that accumulate when done mentally for larger numbers.
Related Calculators
Fractions
Add, subtract, multiply, and divide fractions. Get simplified results, mixed numbers, and step-by-step working.
Prime Checker
Check if a number is prime and get its prime factorization, all divisors, and the nearest prime numbers.
Base Converter
Convert numbers between binary, octal, decimal, and hexadecimal. See the value in all 4 bases at once.