CALTRX

GCD/LCM Calculator

Find the Greatest Common Divisor and Least Common Multiple of two or more numbers. Used in fraction simplification and number theory.

units

Enter your values above to see the results.

Tips & Notes

  • ✓GCD×LCM = a×b always. Use to find LCM once you have GCD: LCM = (a×b)/GCD.
  • ✓GCD(a,1)=1 always. GCD(a,a)=a always. Quick sanity checks.
  • ✓For fractions: simplify with GCD. Add fractions with LCM as common denominator.
  • ✓Three numbers: GCD(a,b,c) = GCD(GCD(a,b), c). Apply pairwise.
  • ✓If smaller divides larger evenly, GCD = smaller: GCD(6,18)=6 since 18÷6=3 exactly.

Common Mistakes

  • ✗Confusing GCD with LCM. GCD ≤ min(a,b). LCM ≥ max(a,b). They go in opposite directions.
  • ✗Stopping Euclidean algorithm early. GCD(48,18): first remainder is 12, not the final answer.
  • ✗Taking minimum exponents of ALL primes in factorization. GCD uses only SHARED primes.
  • ✗LCM formula: (a×b)/GCD. Not (a+b)/GCD or a×b×GCD.
  • ✗GCD of three numbers: must apply GCD pairwise — not just to any two.

GCD/LCM Calculator Overview

The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) are two fundamental number theory operations that reveal how integers relate through divisibility. The GCD finds the largest number that divides both inputs evenly — the deepest common factor. The LCM finds the smallest number divisible by both inputs — the earliest common multiple. Together they govern fraction arithmetic, ratio reduction, scheduling synchronization, and the structure of modular arithmetic. Their elegant relationship — GCD × LCM = a × b — means knowing one instantly gives you the other.

GCD using the Euclidean Algorithm — the most efficient method:

GCD(a, b) = GCD(b, a mod b) — repeat until remainder = 0
EX: GCD(48, 18) → 48 mod 18=12 → GCD(18,12) → 18 mod 12=6 → GCD(12,6) → 0 → GCD=6
EX: GCD(270, 192) → 270 mod 192=78 → GCD(192,78) → 192 mod 78=36 → GCD(78,36) → 78 mod 36=6 → GCD(36,6) → 0 → GCD=6
LCM from GCD — the fastest route once GCD is known:
LCM(a, b) = (a × b) / GCD(a, b)
EX: LCM(48, 18) = (48×18)/6 = 864/6 = 144 | verify: 144÷48=3✓, 144÷18=8✓
Verification identity: GCD(a,b) × LCM(a,b) = a × b always — use this to check your work:
EX: GCD(48,18)=6, LCM=144 → 6×144=864=48×18 ✓
Prime factorization method: - GCD: take minimum exponent of each shared prime - LCM: take maximum exponent of every prime
EX: 48=2⁴×3, 18=2×3² → GCD=2¹×3¹=6 | LCM=2⁴×3²=144
The GCD and LCM are complementary — they always satisfy the identity GCD(a,b) × LCM(a,b) = a × b. This relationship lets you compute one from the other: if you know the GCD, the LCM is a×b÷GCD, which is faster than computing the LCM directly. For three or more numbers, apply the algorithm iteratively: GCD(a,b,c) = GCD(GCD(a,b), c). The Euclidean algorithm is one of the oldest and most efficient algorithms in mathematics — it reduces any GCD problem to a sequence of simple remainders that converges in at most 5× the number of digits of the smaller input. The GCD has a geometric interpretation that makes fraction problems intuitive: the largest square tile that fits exactly into a p × q rectangle without any cuts has a side length of GCD(p, q).

Frequently Asked Questions

GCD is the largest number that divides all given numbers without remainder. LCM is the smallest number that all given numbers divide into without remainder. GCD(12,18)=6 because 6 is the biggest divisor of both. LCM(12,18)=36 because 36 is the smallest number both 12 and 18 divide into evenly. Key relationship: GCD(a,b) × LCM(a,b) = a × b. GCD(12,18) × LCM(12,18) = 6 × 36 = 216 = 12 × 18 ✓.

Euclidean algorithm for GCD: GCD(a,b) = GCD(b, a mod b), stopping when remainder = 0. Example: GCD(252,105). 252 = 2×105 + 42 → GCD(105,42). 105 = 2×42 + 21 → GCD(42,21). 42 = 2×21 + 0 → GCD = 21. Then LCM(252,105) = 252×105/21 = 26460/21 = 1260. Verify: 1260/252=5 ✓, 1260/105=12 ✓. The Euclidean algorithm runs in at most 2×log₁₀(min(a,b)) steps.

Prime factorization method: factor both numbers, then GCD uses minimum exponents and LCM uses maximum exponents. GCD(360,252): 360=2³×3²×5, 252=2²×3²×7. GCD: 2^min(3,2)×3^min(2,2) = 2²×3² = 36. LCM: 2^max(3,2)×3^max(2,2)×5¹×7¹ = 2³×3²×5×7 = 2520. Verify: GCD×LCM = 36×2520 = 90720 = 360×252 ✓. This method extends naturally to three or more numbers.

GCD simplifies fractions: divide numerator and denominator by their GCD. 24/36: GCD(24,36)=12 → 2/3. LCM finds the common denominator for fraction addition. 1/12 + 1/18: LCM(12,18)=36 → 3/36 + 2/36 = 5/36. GCD solves equal-grouping problems: distribute 24 apples and 36 oranges into maximum equal groups → GCD(24,36)=12 groups with 2 apples and 3 oranges each. LCM solves scheduling: events every 12 and 18 days coincide every LCM(12,18)=36 days.

GCD of three numbers: GCD(a,b,c) = GCD(GCD(a,b),c). GCD(24,36,48): GCD(24,36)=12, GCD(12,48)=12. LCM(a,b,c) = LCM(LCM(a,b),c). LCM(4,6,10): LCM(4,6)=12, LCM(12,10)=60. Cannot use the product formula a×b×c/GCD for three numbers — it only works for exactly two numbers. The relationship GCF×LCM=a×b extends as: LCM(a,b,c) = a×b×c×GCD(a,b,c) / (GCD(a,b)×GCD(b,c)×GCD(a,c)).

In modular arithmetic and number theory, GCD determines coprimality (GCD=1 means coprime), which governs the structure of solutions to linear Diophantine equations. The equation ax+by=c has integer solutions if and only if GCD(a,b) divides c. Example: 6x+10y=14. GCD(6,10)=2, and 2 divides 14 → solutions exist. One solution: x=3, y=−1 (verify: 18−10=8... correction: x=−1, y=2 gives −6+20=14 ✓). The general solution adds multiples of the other coefficient.