GCD and LCM Calculator

Find the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of two or more integers instantly.

Instant result Runs in browser

Tip: Enter at least 2 integers. You can enter more than 2 numbers.

Formulas

EBOB(a,b) = EBOB(b, a mod b)
EKOK(a,b) = a × b / EBOB(a,b)
EBOB(12,18): 12 = 0×18+12 → 18=1×12+6 → 12=2×6+0 → EBOB=6
EKOK(12,18): 12×18/6 = 36

How to use?

  1. 1
    Enter numbersType two or more integers separated by commas or spaces (e.g. 12, 18, 24).
  2. 2
    Click CalculateGCD and LCM appear instantly. The step-by-step Euclidean algorithm is also shown.
  3. 3
    Copy or shareCopy the result or share the page with others.

FAQ

What is the difference between GCD and LCM?
GCD (Greatest Common Divisor) is the largest number that divides all given numbers exactly. LCM (Least Common Multiple) is the smallest number divisible by all given numbers. They are related by: GCD × LCM = a × b (for two numbers a and b).
How is GCD calculated?
The most efficient method is the Euclidean algorithm: repeatedly replace the larger number with the remainder of dividing by the smaller. For example, GCD(48, 18): 48 = 2×18 + 12; 18 = 1×12 + 6; 12 = 2×6 + 0 → GCD = 6.
Where are GCD and LCM used?
GCD is used to simplify fractions (divide numerator and denominator by GCD). LCM is used to find a common denominator when adding fractions. Both are fundamental in number theory and competitive programming.

What Are GCD and LCM?

The Greatest Common Divisor (GCD) — also called Greatest Common Factor (GCF) or Highest Common Factor (HCF) — is the largest positive integer that divides each of the given numbers without a remainder. The Least Common Multiple (LCM) is the smallest positive integer divisible by all given numbers.

The Euclidean Algorithm

The Euclidean algorithm is the most efficient way to compute GCD: GCD(a, b) = GCD(b, a mod b), repeating until the remainder is 0. It runs in O(log n) time. For example: GCD(252, 105) → GCD(105, 42) → GCD(42, 21) → GCD(21, 0) = 21.

Relationship Between GCD and LCM

For two positive integers a and b: GCD(a, b) × LCM(a, b) = a × b. This identity allows LCM to be computed quickly once GCD is known.

Practical Uses

  • Simplifying fractions: 18/24 → divide both by GCD(18,24)=6 → 3/4.
  • Adding fractions: 1/4 + 1/6 → common denominator = LCM(4,6) = 12 → 3/12 + 2/12 = 5/12.
  • Scheduling: Two events with periods of 4 and 6 days coincide every LCM(4,6) = 12 days.

Comments