GCD & LCM Calculator
Calculate the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of two numbers using the Euclidean algorithm.
GCD (Greatest Common Divisor)
—
LCM (Least Common Multiple) —
GCD Steps —
Extended More scenarios, charts & detailed breakdown ▾
GCD
—
LCM —
Euclidean Steps —
Coprime? —
Professional Full parameters & maximum detail ▾
GCD & LCM
GCD of all —
LCM of all —
Number Properties
All Coprime? —
Sum of Numbers —
Product of Numbers —
Prime Factorizations
Prime Factors of each —
How to Use This Calculator
Enter two positive integers. The calculator finds their GCD using the Euclidean algorithm and their LCM from the formula LCM = |a×b| / GCD.
Formula
Euclidean GCD: repeatedly apply (a,b) → (b, a mod b) until b=0 • LCM = |a×b| / GCD
Example
GCD(48,18): 48=2×18+12 → 18=1×12+6 → 12=2×6+0 → GCD=6, LCM=144
Frequently Asked Questions
- The Greatest Common Divisor (GCD), also called the Greatest Common Factor (GCF), is the largest positive integer that divides both numbers without leaving a remainder. For example, GCD(48, 18) = 6, because 6 divides both 48 (48÷6=8) and 18 (18÷6=3), and no larger integer does so. GCD is used to simplify fractions: divide both numerator and denominator by their GCD. For 18/48, GCD=6, so 18/48 = 3/8. GCD(a, 0) = a for any a, and GCD(0, 0) is conventionally undefined.
- The Least Common Multiple (LCM) is the smallest positive integer that is divisible by both numbers. For example, LCM(4, 6) = 12, because 12 is the smallest number in both the multiples of 4 (4, 8, 12, 16, …) and multiples of 6 (6, 12, 18, …). LCM is used when adding fractions with different denominators — the LCD (Least Common Denominator) is the LCM of the denominators. For 1/4 + 1/6, LCD = LCM(4,6) = 12, so 3/12 + 2/12 = 5/12.
- The Euclidean algorithm efficiently finds GCD by repeatedly applying: GCD(a, b) = GCD(b, a mod b), until b = 0, at which point a is the GCD. Example: GCD(48, 18): 48 = 2×18 + 12 → GCD(18, 12). Then 18 = 1×12 + 6 → GCD(12, 6). Then 12 = 2×6 + 0 → GCD(6, 0) = 6. This is much faster than listing all factors, especially for large numbers. The Extended Euclidean Algorithm also finds integers x, y such that a×x + b×y = GCD(a,b), useful in modular inverse calculations.
- GCD and LCM are related by: LCM(a, b) = |a × b| / GCD(a, b). This means you only need to compute one to find the other. Example: GCD(12, 18) = 6, so LCM(12, 18) = (12 × 18) / 6 = 216 / 6 = 36. Verify: 36 / 12 = 3 ✓ and 36 / 18 = 2 ✓. This relationship holds for any two positive integers. For more than two numbers, apply pairwise: LCM(a,b,c) = LCM(LCM(a,b), c).
- GCD has many practical uses: simplifying fractions (divide numerator and denominator by GCD to get the simplest form), finding common denominators for adding fractions, distributing items equally (e.g., 48 apples and 18 oranges into the maximum equal groups — GCD(48,18) = 6 groups), and number theory (coprimality: two numbers are coprime if GCD = 1, which is required for modular inverses and RSA encryption). Many calendar and scheduling problems also use GCD and LCM to find repeating cycles.