The LCM & GCD Calculator finds the Least Common Multiple and Greatest Common Divisor of two or more integers โ€” enter them as a comma or space-separated list.

LCM & GCD Calculator

Find the Least Common Multiple and Greatest Common Divisor of two or more numbers.

GCD
โ€”
LCM
โ€”

How to Use This Calculator

  1. Enter two or more positive integers separated by commas or spaces (e.g., 12, 18, 24).
  2. Click Calculate.

What Are GCD and LCM?

The Greatest Common Divisor (GCD), also called Greatest Common Factor (GCF), is the largest number that divides all the given numbers evenly. For 12 and 18: GCD = 6 (both are divisible by 6, but not by 7, 8, etc.).

The Least Common Multiple (LCM) is the smallest number that all given numbers divide into evenly. For 4 and 6: LCM = 12 (the smallest number divisible by both 4 and 6).

Practical Uses

GCD is used in simplifying fractions (divide numerator and denominator by their GCD), cryptography (RSA encryption relies on GCD calculations), and scheduling problems.

LCM is used in adding fractions with different denominators (find the LCM of the denominators), scheduling repeating events (if event A repeats every 4 days and event B every 6 days, they coincide every LCM(4,6) = 12 days), and time synchronization problems.

Frequently Asked Questions

What is the Euclidean algorithm?

The most efficient GCD algorithm: GCD(a,b) = GCD(b, a mod b), repeating until the remainder is 0. GCD(48, 18): 48 mod 18 = 12 โ†’ GCD(18,12): 18 mod 12 = 6 โ†’ GCD(12,6): 12 mod 6 = 0 โ†’ GCD = 6.

Is GCD(a,b) ร— LCM(a,b) always equal to aร—b?

Yes, for two numbers: GCD(a,b) ร— LCM(a,b) = a ร— b. For example, GCD(4,6)=2, LCM(4,6)=12, and 2ร—12 = 4ร—6 = 24. This relationship only holds for pairs of numbers, not for three or more numbers.

Worked Example

Take 12 and 18. Their GCD (greatest common divisor) is the largest number dividing both: the factors of 12 are 1, 2, 3, 4, 6, 12 and of 18 are 1, 2, 3, 6, 9, 18, so the GCD is 6. Their LCM (least common multiple) is the smallest number both divide into: 36. A useful shortcut is that LCM ร— GCD always equals the product of the two numbers (36 ร— 6 = 216 = 12 ร— 18).

Where LCM and GCD Are Used

  • Adding fractions: The LCM of the denominators gives the least common denominator.
  • Simplifying fractions: Dividing by the GCD reduces a fraction to lowest terms.
  • Scheduling: The LCM tells you when two repeating events line up again (buses every 12 and 18 minutes coincide every 36 minutes).
  • Tiling and packing: The GCD finds the largest equal square that tiles a rectangle.

How They’re Calculated

The calculator uses the Euclidean algorithm to find the GCD efficiently: repeatedly replace the larger number with the remainder of dividing it by the smaller, until the remainder is zero. The LCM is then found instantly using the relationship LCM(a, b) = (a ร— b) รท GCD(a, b).

How it works

GCD is computed using the recursive Euclidean algorithm: gcd(a,b) = b===0 ? a : gcd(b, a%b). For more than two numbers, the GCD is found by reducing: gcd(a,b,c) = gcd(gcd(a,b),c). LCM of two numbers = (a/gcd(a,b)) ร— b, extended similarly for multiple numbers.

Formula

GCD(a,b): Euclidean โ€” gcd(a,b)=gcd(b,a mod b) until remainder=0. LCM(a,b)=(a/GCD(a,b))ร—b. For multiple numbers, apply pairwise.