GCD & LCM Calculator
Find the greatest common divisor and least common multiple of two numbers. Calculate GCD and LCM instantly using the Euclidean algorithm.
Result
- Greatest Common Divisor (GCD)
- 0
- Least Common Multiple (LCM)
- 0
Formula & Guide
GCD
GCD (Euclidean Algorithm)
GCD(a, b) = GCD(b, a mod b)
Recursive formula until remainder is 0
LCM
LCM Formula
LCM(a, b) = (a × b) / GCD(a, b)
Product divided by GCD
=
Relationship
GCD × LCM = a × b
Product of GCD and LCM equals product of numbers
Formula Variables
a, b
Numbers
The two positive integers to find GCD and LCM for
GCD
Greatest Common Divisor
The largest positive integer that divides both a and b evenly
LCM
Least Common Multiple
The smallest positive integer that is divisible by both a and b
mod
Modulo
The remainder after division (a mod b = remainder of a ÷ b)
Step-by-Step Scenario
Example Scenario
Number 1
48
Number 2
18
1
Apply Euclidean Algorithm
- GCD(48, 18) = GCD(18, 48 mod 18)
- 48 mod 18 = 12 (remainder)
Divide 48 by 18, use the remainder
2
Continue the Algorithm
- GCD(18, 12) = GCD(12, 18 mod 12)
- 18 mod 12 = 6
3
Final Step
- GCD(12, 6) = GCD(6, 12 mod 6)
- 12 mod 6 = 0
4
Calculate LCM
- LCM(48, 18) = (48 × 18) / GCD(48, 18)
- LCM(48, 18) = 864 / 6
Additional Examples
Small Numbers
Numbers: 12 and 8
GCD
GCD(12, 8) = 4
LCM
LCM(12, 8) = 24
Prime Numbers
Numbers: 7 and 11
GCD
GCD(7, 11) = 1 (coprime)
LCM
LCM(7, 11) = 77
Characteristics of GCD & LCM
Efficient Algorithm
The Euclidean algorithm for GCD is very efficient, with time complexity O(log min(a,b)), making it fast even for large numbers.
Fraction Simplification
GCD is used to simplify fractions by dividing numerator and denominator by their GCD. For example, 12/18 simplifies to 2/3 using GCD(12,18)=6.
Common Denominators
LCM is essential for finding common denominators when adding or subtracting fractions. For example, to add 1/4 + 1/6, use LCM(4,6)=12.
Mathematical Relationship
GCD and LCM are inversely related: GCD × LCM = a × b. This relationship allows calculating one from the other.
Important Notes
- GCD is always positive and cannot be zero. The GCD of any number and 0 is the absolute value of that number.
- LCM is always positive (for positive inputs) and is at least as large as the larger of the two numbers.
- If two numbers are coprime (GCD = 1), their LCM is simply their product: LCM(a, b) = a × b when GCD(a, b) = 1.
- The Euclidean algorithm is much more efficient than listing all divisors, especially for large numbers.
- GCD and LCM are fundamental in number theory and are used extensively in algebra, cryptography, and computer science.
Frequently Asked Questions
Find answers to common questions about GCD and LCM calculations.
GCD is the largest positive integer that divides both numbers evenly without a remainder. For example, GCD of 12 and 18 is 6, because 6 is the largest number that divides both 12 and 18 evenly.
LCM is the smallest positive integer that is a multiple of both numbers. For example, LCM of 4 and 6 is 12, because 12 is the smallest number that is divisible by both 4 and 6.
GCD and LCM are related by the formula: GCD(a, b) × LCM(a, b) = a × b. This means if you know one, you can calculate the other. For example, if GCD(12, 18) = 6, then LCM(12, 18) = (12 × 18) / 6 = 36.
The Euclidean algorithm is an efficient method to find GCD. It repeatedly applies: GCD(a, b) = GCD(b, a mod b) until b becomes 0, then a is the GCD. This is much faster than listing all divisors.
GCD is used to simplify fractions (dividing numerator and denominator by GCD), while LCM is used to find common denominators for adding/subtracting fractions. Both are fundamental in number theory and algebra.
GCD cannot be zero (by definition, it's the greatest positive divisor). LCM can be zero only if both numbers are zero, but typically we work with positive integers where LCM is always positive.