CalculateY CalculateY

GCD & LCM Calculator

The greatest common divisor (GCD) of two or more integers is the largest positive integer that divides each of them without a remainder. The least common multiple (LCM) is the smallest positive integer that is divisible by each of the given numbers. Enter a set of integers to compute both values at once. The GCD is calculated using the Euclidean algorithm, and the LCM is derived from the relationship LCM(a, b) = |a x b| / GCD(a, b).

Quick Answer

The GCD of 12 and 18 is 6, and the LCM of 12 and 18 is 36.

Separate values with commas, spaces, or newlines. Non-integer and zero values are ignored.

Common Examples

Input Result
12, 18 GCD: 6, LCM: 36
24, 36, 48 GCD: 12, LCM: 144
7, 13 GCD: 1, LCM: 91
100, 75, 50 GCD: 25, LCM: 300
8, 12, 20 GCD: 4, LCM: 120

How It Works

The Euclidean Algorithm (GCD)

The Euclidean algorithm is one of the oldest known algorithms, dating back to Euclid’s Elements (circa 300 BC). It finds the GCD of two numbers by repeatedly applying the division algorithm:

GCD(a, b): While b is not 0, replace (a, b) with (b, a mod b). When b = 0, a is the GCD.

For more than two numbers, apply the algorithm iteratively: GCD(a, b, c) = GCD(GCD(a, b), c).

Least Common Multiple (LCM)

The LCM is calculated using its relationship with the GCD:

**LCM(a, b) = a x b / GCD(a, b)**

For more than two numbers, apply the formula iteratively: LCM(a, b, c) = LCM(LCM(a, b), c).

Key Properties

For any two positive integers a and b:

  • GCD(a, b) x LCM(a, b) = a x b
  • GCD(a, b) always divides both a and b
  • LCM(a, b) is always divisible by both a and b
  • If GCD(a, b) = 1, the numbers are called coprime (or relatively prime)

Worked Example

To find GCD(24, 36):

  • 36 = 1 x 24 + 12 (remainder 12)
  • 24 = 2 x 12 + 0 (remainder 0)
  • GCD = 12
LCM(24, 36) = 24 x 36 / 12 = 864 / 12 = 72.
For three numbers, GCD(24, 36, 48): First GCD(24, 36) = 12, then GCD(12, 48) = 12. LCM(24, 36, 48): First LCM(24, 36) = 72, then LCM(72, 48). GCD(72, 48) = 24, so LCM = 72 x 48 / 24 = 3456 / 24 = 144.

Related Calculators

Fraction Calculator

Add, subtract, multiply, and divide fractions. Simplify fractions and convert between fractions and decimals.

Ratio Calculator

Simplify ratios, solve proportions, and scale ratios up or down.

Standard Deviation Calculator

Calculate the standard deviation, variance, mean, and other statistics for any data set.

Frequently Asked Questions

What is the difference between GCD and LCM?
The GCD (greatest common divisor) is the largest number that divides all given numbers evenly. The LCM (least common multiple) is the smallest number that all given numbers divide into evenly. For example, for 12 and 18, the GCD is 6 and the LCM is 36.
What does it mean if the GCD is 1?
If the GCD of two numbers is 1, they are called coprime or relatively prime. This means they share no common prime factors. For example, 8 and 15 are coprime because GCD(8, 15) = 1.
Why is the LCM useful?
The LCM is commonly used to find the least common denominator when adding or subtracting fractions. It also appears in scheduling problems, such as determining when two cyclical events will next coincide.
Can I find the GCD and LCM of more than two numbers?
Yes. Apply the two-number formula iteratively. GCD(a, b, c) = GCD(GCD(a, b), c), and the same pattern applies for LCM. This calculator supports any number of inputs.
Does the GCD work with negative numbers?
The GCD is defined for positive integers, but by convention the GCD of negative numbers uses their absolute values. GCD(-12, 18) = GCD(12, 18) = 6. This calculator takes the absolute value of each input automatically.