Greatest Common Denominator Calculator

Enter two or three whole numbers to find their greatest common divisor (GCD) with the Euclidean algorithm, plus the least common multiple (LCM) and each number reduced to its simplest ratio.

Quick Facts

Euclidean algorithm
gcd(a, b) = gcd(b, a mod b)
Repeat until the remainder is 0; the last nonzero remainder is the GCD.
GCD-LCM relationship
gcd(a,b) × lcm(a,b) = a × b
For two numbers, the LCM follows directly once you know the GCD.
Fraction reduction
a/gcd over b/gcd
Dividing numerator and denominator by their GCD gives lowest terms.

Your Results

Calculated
Greatest Common Divisor (GCD)
-
Largest integer dividing all entered numbers evenly
Least Common Multiple (LCM)
-
Smallest positive multiple shared by all entered numbers
Simplified Ratio
-
Each number divided by the GCD
Euclidean Algorithm Steps
-
How the GCD was derived

Ready

Enter two or three whole numbers, then press Calculate.

How the Greatest Common Denominator (GCD) Works

"Greatest common denominator" is a widely used name for what mathematicians call the greatest common divisor (also called the greatest common factor, or GCF) — the largest positive integer that divides two or more whole numbers with no remainder. This calculator finds that number for two or three integers using the Euclidean algorithm, then derives the least common multiple (LCM) and shows each input reduced by the GCD.

Formula and method — the Euclidean algorithm

The fastest reliable way to find gcd(a, b) does not require factoring either number. Divide the larger number by the smaller and keep the remainder: gcd(a, b) = gcd(b, a mod b). Replace a with b and b with the remainder, then repeat. When the remainder reaches 0, the previous divisor is the GCD. For example, gcd(48, 18): 48 = 2×18 + 12, so gcd(48,18) = gcd(18,12); 18 = 1×12 + 6, so gcd(18,12) = gcd(12,6); 12 = 2×6 + 0, so the GCD is 6. For three numbers a, b, c, the calculator applies the same process twice: gcd(a, b, c) = gcd(gcd(a, b), c). Once the GCD is known, the least common multiple of two numbers follows from lcm(a, b) = |a × b| / gcd(a, b) — no need to list out multiples.

Common sources of error

  • Non-integer inputs: the GCD and LCM are only defined for whole numbers — decimals like 4.5 have no meaningful GCD.
  • Both numbers zero: gcd(0, 0) is undefined because every integer divides 0, so there is no single largest common divisor.
  • Confusing GCD with LCM: the GCD is the largest shared divisor (always ≤ the smaller number); the LCM is the smallest shared multiple (always ≥ the larger number). Mixing them up gives a number in the wrong direction for the task at hand.

Checking your result

The GCD must always divide every input number exactly, with no remainder — verify this by dividing each entered number by the calculated GCD and confirming the result is a whole number. As a second check, the GCD can never be larger than the smallest number you entered. For two numbers, you can also confirm gcd × lcm equals the product of the two numbers.

Applications

The GCD is the tool behind reducing a fraction to lowest terms: dividing the numerator and denominator by their GCD gives an equivalent fraction that cannot be simplified further. It also comes up when dividing items into equal groups (the largest group size that splits several quantities evenly), tiling or cutting stock material into the largest equal squares or lengths with no waste, and in cryptography and computer science algorithms such as modular arithmetic and the RSA key-generation process.

Frequently Asked Questions

What is the greatest common denominator (GCD) of two numbers?
The greatest common denominator, more precisely called the greatest common divisor or greatest common factor, is the largest positive integer that divides two or more numbers with no remainder. For example, the GCD of 48 and 18 is 6, since 6 is the largest number that divides both evenly.
How does the Euclidean algorithm find the GCD?
Divide the larger number by the smaller and note the remainder, then replace the larger number with the smaller number and the smaller number with that remainder. Repeat until the remainder is 0 — the last nonzero remainder is the GCD. For 48 and 18: 48 = 2×18 + 12, 18 = 1×12 + 6, 12 = 2×6 + 0, so the GCD is 6.
How are the GCD and LCM related?
For two positive integers a and b, GCD(a, b) × LCM(a, b) = a × b. Once you know the GCD, you can find the least common multiple by dividing the product of the two numbers by their GCD, without listing multiples.
How do I use the GCD to simplify a fraction?
Divide both the numerator and denominator by their GCD to reduce the fraction to lowest terms. For 18/48, the GCD of 18 and 48 is 6, so dividing both by 6 gives the simplified fraction 3/8.

Related calculators