What is GCD & LCM Calculator?
The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) are two of the most important concepts in elementary number theory, with applications from simplifying fractions in middle school to cryptographic algorithms that secure the internet.
The Euclidean algorithm, described by Euclid around 300 BC, is one of the oldest and most efficient algorithms in mathematics. It computes the GCD in O(log(min(a,b))) steps, terminating rapidly even for very large numbers. The algorithm applies the identity: GCD(a, b) = GCD(b, a mod b) repeatedly until the remainder is zero.
This calculator shows the complete Euclidean algorithm step by step for two numbers, and also computes GCD and LCM for lists of multiple numbers using the generalization: GCD(a, b, c) = GCD(GCD(a, b), c).
When to Use This Calculator
- Simplifying fractions to lowest terms: divide numerator and denominator by GCD
- Adding or subtracting fractions with different denominators: find LCM of denominators
- Scheduling problems: determining when two periodic events will next coincide
- RSA cryptography: verifying that the encryption exponent is co-prime with φ(n)
- Gear ratio calculations: finding the smallest gear tooth count for a given ratio
- Tile pattern design: determining the smallest repeating unit for rectangular tiles
Steps:
- Enter two positive integers a and b.
- Apply integer division: a = q×b + r.
- Replace a with b and b with r. Repeat until r = 0.
- The last non-zero remainder is the GCD.
- Compute LCM = |a × b| / GCD using the fundamental identity.
- Use Multiple Numbers mode for three or more numbers.
Formula
Euclidean Algorithm:
GCD(a, b) = GCD(b, a mod b) until b = 0
LCM from GCD:
LCM(a, b) = |a × b| / GCD(a, b)
For multiple numbers:
GCD(a, b, c) = GCD(GCD(a, b), c)
LCM(a, b, c) = LCM(LCM(a, b), c)
Use Cases
- Simplifying fractions: reduce a/b by dividing both by GCD(a, b)
- Adding fractions with different denominators: find LCM of denominators
- Scheduling: finding when two recurring events will next coincide
- RSA key generation: checking that exponent e is co-prime with φ(n)
- Gear ratio problems in mechanical engineering
- Tile pattern design: finding the smallest repeating unit
Key Benefits
- Compute GCD and LCM instantly for two or more numbers using the Euclidean algorithm
- See the complete step-by-step division process so you can learn and verify the algorithm
- Automatically determine whether two numbers are co-prime (GCD = 1)
- Simplify fractions by dividing numerator and denominator by their GCD
- Handle large numbers efficiently — the algorithm works even for numbers with dozens of digits
- Support for multiple numbers mode: compute GCD/LCM for lists of 3 or more values
Pro Tips
- Use the GCD-LCM relationship: LCM(a,b) = |a×b| / GCD(a,b) — this is faster than listing multiples
- Two numbers are co-prime if and only if GCD = 1 — check this before modular arithmetic calculations
- For simplifying fractions, always divide both numerator and denominator by GCD(num, den)
- When scheduling, convert all time periods to the same unit before computing LCM
- Remember that GCD(0, n) = n and LCM(0, n) = 0 — zero is divisible by everything
- For very large numbers, the Euclidean algorithm is still efficient — no need for prime factorization
Common Mistakes to Avoid
- Confusing GCD with LCM: GCD is the largest common DIVISOR, LCM is the smallest common MULTIPLE
- Thinking LCM is just a×b: this is only true when GCD(a,b) = 1 (co-prime numbers)
- Forgetting that GCD and LCM extend to more than two numbers: GCD(a,b,c) = GCD(GCD(a,b), c)
- Assuming the Euclidean algorithm requires prime factorization — it does not, which is why it is so efficient
- Using LCM for simplifying fractions when you should use GCD
- Not checking for co-prime status before RSA key generation — e must be co-prime with φ(n)
Key Terms Explained
- GCD: Largest integer dividing both numbers without remainder
- LCM: Smallest positive integer divisible by both numbers
- Co-prime: Two numbers with GCD = 1, sharing no common prime factors
- Euclidean algorithm: Ancient algorithm computing GCD by repeated division
- Modulo operation: a mod b is the remainder when a is divided by b
- Divisibility: a divides b if b/a has no remainder
Related Concepts
- Prime Factorization: Break numbers into prime factors — the foundation for understanding GCD and LCM.
- Fraction Calculator: Simplify, add, and subtract fractions using GCD for reduction.
- Logarithm Calculator: Explore the logarithmic complexity of the Euclidean algorithm.
- Percentage Calculator: Convert GCD/LCM results to percentages for ratio analysis.
- Modular Arithmetic: Work with co-prime moduli in RSA cryptography and modular equations.
Example
Find GCD(48, 18): 48 = 2×18 + 12 → 18 = 1×12 + 6 → 12 = 2×6 + 0. GCD = 6. LCM = |48×18|/6 = 864/6 = 144. Check: 144/48 = 3 ✓, 144/18 = 8 ✓.
Interpreting Your Results
The GCD result tells you the largest number that divides both inputs evenly. If GCD = 1, the numbers are co-prime — they share no common factors beyond 1. The LCM result is the smallest number both inputs divide into evenly. A large GCD relative to the inputs means the numbers share many factors (e.g., GCD(12, 18) = 6). A GCD of 1 means the numbers are co-prime and LCM = a×b. The product identity GCD × LCM = |a×b| lets you verify: multiply your GCD and LCM results and confirm they equal the product of the original numbers.