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.
Frequently Asked Questions
What is GCD (HCF)?+
GCD (Greatest Common Divisor), also called HCF (Highest Common Factor) in Indian school curricula, is the largest positive integer that divides all given numbers exactly with no remainder. Example: GCD(24, 36). Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24. Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36. Common factors: 1, 2, 3, 4, 6, 12. Greatest = 12. So GCD(24, 36) = 12. This tells you that 24 and 36 can both be evenly divided into groups of 12. For large numbers, listing all factors is slow - the Euclidean algorithm finds GCD much faster.
What is LCM?+
LCM (Least Common Multiple) is the smallest positive integer divisible by all given numbers. Example: LCM(4, 6). Multiples of 4: 4, 8, 12... Multiples of 6: 6, 12... First common multiple = 12. The efficient formula: LCM(a, b) = (a x b) / GCD(a, b). Using the formula: LCM(4, 6) = (4 x 6) / GCD(4, 6) = 24 / 2 = 12. For three numbers: LCM(a, b, c) = LCM(LCM(a, b), c). LCM tells you when two periodic events next coincide: if event A repeats every 4 minutes and event B every 6 minutes, they next coincide in 12 minutes (the LCM). Adding fractions with unlike denominators requires the LCM of those denominators.
What is the Euclidean algorithm?+
The Euclidean algorithm finds GCD efficiently without listing all factors. It uses the fact that GCD(a, b) = GCD(b, a mod b), where a mod b is the remainder when a is divided by b. Repeat until the remainder is 0; the last non-zero remainder is the GCD. Example: GCD(252, 105). Step 1: 252 mod 105 = 42. Now GCD(105, 42). Step 2: 105 mod 42 = 21. Now GCD(42, 21). Step 3: 42 mod 21 = 0. GCD = 21. This algorithm runs in O(log n) steps - fast even for numbers with hundreds of digits, which is why it is fundamental to cryptography and used in every programming language's standard library.
Where are GCD and LCM used in everyday life?+
GCD - packing: you have 60 red and 48 blue candies to pack into identical bags with no leftovers. GCD(60, 48) = 12 means 12 equal bags, each with 5 red and 4 blue. GCD - simplifying fractions: 36/48 simplifies to 3/4 by dividing both by GCD(36, 48) = 12. LCM - scheduling: bus A every 15 minutes, bus B every 20 minutes. LCM(15, 20) = 60 - they arrive together after 60 minutes. LCM - adding fractions: 1/6 + 1/4. LCD = LCM(6, 4) = 12. Convert to 2/12 + 3/12 = 5/12. LCM - gear cycles: gears of 24 and 36 teeth return to starting position every LCM(24, 36) = 72 rotations.
Where are GCD and LCM used in everyday life and school problems?+
GCD (Greatest Common Divisor) is used when you need to divide things into equal groups without leftovers. Example: you have 24 apples and 36 oranges; GCD(24,36) = 12 means you can make 12 equal bags with 2 apples and 3 oranges each. Also used to simplify fractions - divide numerator and denominator by their GCD. LCM (Least Common Multiple) is used when things need to happen together. Example: Bus A comes every 12 minutes, Bus B every 8 minutes; LCM(12,8) = 24 means they arrive together every 24 minutes. Adding fractions with different denominators requires finding the LCM of those denominators.
How do I find GCD of three or more numbers?+
Apply the GCD algorithm iteratively: GCD(a, b, c) = GCD(GCD(a, b), c). Example: GCD(36, 48, 60). First: GCD(36, 48). 48 mod 36 = 12, 36 mod 12 = 0, so GCD(36, 48) = 12. Then: GCD(12, 60). 60 mod 12 = 0, so GCD(12, 60) = 12. Final answer: GCD(36, 48, 60) = 12. This means 12 is the largest number dividing all three exactly. Practical use: you have containers of 36 L, 48 L, and 60 L of three different liquids. The largest equal portion you can fill from all three with no remainder is 12 L. The iterative method extends to any number of inputs.
What does it mean when GCD equals 1?+
When GCD(a, b) = 1, the two numbers are called coprime or relatively prime - they share no common factors other than 1. Examples: GCD(8, 15) = 1, so 8 and 15 are coprime, even though neither is itself a prime number. GCD(14, 21) = 7, so 14 and 21 are not coprime. Why coprime matters: a fraction a/b is in lowest terms when a and b are coprime. RSA encryption requires the public exponent e to be coprime with phi(n) - this GCD check is done with the Euclidean algorithm. Consecutive integers are always coprime: GCD(n, n+1) = 1 for any integer n, which is why consecutive years never share the same number of calendar weeks.