🔢 GCD Calculator: Greatest Common Divisor of Any Numbers

What is the GCD Calculator?

The greatest common divisor of a set of integers is the largest positive whole number that divides every one of them without a remainder. It is the same value people call the GCF (greatest common factor) or the HCF (highest common factor); the names differ but the answer is identical. For 48, 36, and 60 the greatest common divisor is 12, because 12 is the biggest number that goes evenly into all three. Any GCD calculator worth using should return that value along with the reasoning, not just a bare number. Formally the GCD is defined for integers not all zero, it is always at least 1, and it is never larger than the smallest non-zero absolute value in the set. Those two bounds alone catch most arithmetic slips.

There are four standard ways to find it, and this page uses the fastest two while showing the working for both. The first is listing factors: write out every divisor of each number and pick the biggest one they share. For 12 (1, 2, 3, 4, 6, 12) and 18 (1, 2, 3, 6, 9, 18) the shared divisors are 1, 2, 3, 6, so the greatest common divisor is 6. It is intuitive and fine for small numbers, but it collapses immediately once the inputs get large, because finding every factor of a big number is far harder than finding the GCD directly.

The second is the prime factorization method. Every integer above 1 breaks into a unique product of primes, a result known as the fundamental theorem of arithmetic, and the GCD is built from the primes shared by all of the numbers, each raised to the lowest power that appears in any of them. For 48 = 2^4 x 3 and 36 = 2^2 x 3^2, the shared primes are 2 (at the smaller exponent, 2) and 3 (at exponent 1), so the greatest common divisor is 2^2 x 3 = 12. The LCM is the mirror image: take every prime that appears anywhere, at its highest power, giving 2^4 x 3^2 = 144. This calculator prints each number's factorization so you can see exactly where the answer comes from. A classroom variant of the same idea is the ladder or cake method, where you divide the whole row by a common prime, write the quotients underneath, and repeat; the product of the primes down the left side is the GCD, and multiplying that by the leftover row gives the LCM.

The third and fastest method is the Euclidean algorithm, which is what this euclidean algorithm calculator runs under the hood. The rule is gcd(a, b) = gcd(b, a mod b): you repeatedly replace the pair with the smaller number and the remainder of dividing them, and when the remainder reaches zero the last non-zero value is the answer. For example gcd(1071, 462) becomes gcd(462, 147), then gcd(147, 21), then gcd(21, 0) = 21. Three steps, no factoring. It works because any number dividing both a and b must also divide a - qb, so the common divisors never change as you reduce. Lame's theorem bounds the cost: the number of division steps is never more than about five times the digit count of the smaller number, which is why the method stays instant even on numbers hundreds of digits long. The fourth method, the binary or Stein algorithm, replaces division with halving and subtraction and is what some low-level libraries use for speed, but it returns the identical value.

To handle three or more inputs, the greatest common divisor is folded across the list one pair at a time, since gcd(a, b, c) = gcd(gcd(a, b), c). Order does not matter, and you can stop early: once a running GCD hits 1, the answer for the whole set is 1. The same folding idea gives the least common multiple through the identity lcm(a, b) = |a x b| / gcd(a, b), so this tool works as a combined gcd and lcm calculator. A caution on that identity: it is a two-number rule only. For three or more numbers, gcd x lcm does not equal the product, so fold the LCM pairwise as well rather than multiplying everything together. A related extension, the extended Euclidean algorithm, also finds integers x and y with ax + by = gcd(a, b), which is Bezout's identity; that pair is what makes modular inverses and RSA key generation possible.

The everyday use of the greatest common divisor is reducing fractions to lowest terms: divide the numerator and denominator by their GCD and the fraction is fully simplified in one step rather than by repeated halving. The same move simplifies ratios and aspect ratios, so 1920:1080 becomes 16:9 once you divide by their GCD of 120. Beyond arithmetic it drives gear and pulley ratios, tiling and packing questions where you want the largest square that fills a rectangle with no offcuts, scheduling problems where two cycles must line up, music theory rhythm subdivisions, and cryptography, where RSA requires the public exponent to be coprime with a particular value, meaning their GCD must be exactly 1. Programming languages ship it directly: Python has math.gcd, which accepts any number of arguments, and JavaScript developers typically write a three-line Euclidean loop with BigInt for large values. Whenever you need the largest common measure of several whole numbers, the greatest common divisor is the tool for the job, and this page computes it in real time as you type.

When to use it

• Reducing a fraction to lowest terms by dividing the top and bottom by their greatest common divisor.
• Simplifying a ratio such as 1920:1080 down to 16:9 using the GCD of the two terms.
• Checking greatest common divisor homework and seeing the Euclidean algorithm steps behind the answer.
• Finding the largest identical tile or block size that fits two dimensions with no offcuts.
• Confirming two numbers are coprime (GCD of 1) before using them as a modulus and exponent pair.
• Simplifying gear ratios, sampling rates, or recipe scale factors down to their smallest whole-number form.

How to use the GCD Calculator

1. To find the GCD, type two or more integers into the box, separated by commas, spaces, or new lines.
2. Read the greatest common divisor and the least common multiple shown immediately.
3. Scan the Euclidean algorithm table to see how the first pair reduces step by step.
4. Check the prime-factorization view to see which shared factors build the GCD.
5. Sanity check the result: the GCD must divide every input, and cannot exceed the smallest of them.
6. Use Copy result to grab the GCD and LCM, or an example button to load a sample set.

Formula & method

Worked examples

Greatest common divisor and LCM for common integer pairs

Euclidean algorithm reduction for gcd(1071, 462)

Four methods for finding the greatest common divisor

Common mistakes to avoid

• Confusing the greatest common divisor with the least common multiple. The GCD is never larger than the smallest number you entered, while the LCM is never smaller than the largest. If your greatest common divisor came out bigger than an input, you have the two swapped.
• Assuming the GCD of coprime numbers is an error. When numbers share no common prime factor, such as 9 and 28, the greatest common divisor is 1. That is a correct, meaningful result, not a failure to find one.
• Stopping the Euclidean algorithm one step early. The answer is the last non-zero remainder, taken when the remainder becomes exactly 0. Stopping when the remainder is still positive gives a divisor, but not the greatest one.
• Multiplying shared primes at the wrong power. When building the greatest common divisor from prime factors, use the lowest exponent each shared prime reaches. Using the higher exponent overshoots and no longer divides both numbers. The highest exponents give the LCM, not the GCD.
• Using gcd x lcm = product on three or more numbers. That identity holds for exactly two numbers. For 4, 6, and 10 the GCD is 2 and the LCM is 60, but the product is 240, not 120. Fold both quantities pairwise instead.
• Including zero or decimals in the list. The greatest common divisor is defined for integers not all zero, and zero is divisible by every integer. This calculator ignores zeros and decimals so the result stays well defined. If you need a common measure of decimals, scale them to whole numbers first.

Glossary

Greatest common divisor (GCD)

The largest positive integer that divides every number in a set without a remainder. Also written GCF or HCF.

Greatest common factor (GCF)

Another name for the greatest common divisor; factor and divisor mean the same thing here.

Highest common factor (HCF)

The British term for the greatest common divisor. GCD, GCF, and HCF all give the same value.

Euclidean algorithm

A fast method for the GCD that repeatedly replaces the pair with the smaller number and the remainder of dividing them, until the remainder is zero.

Extended Euclidean algorithm

A version that also returns integers x and y with ax + by = gcd(a, b), used for modular inverses and RSA key generation.

Bezout's identity

The fact that for any integers a and b there exist integers x and y such that ax + by equals their greatest common divisor.

Least common multiple (LCM)

The smallest positive integer that every number in the set divides into evenly, found from |a x b| / gcd(a, b) for two numbers.

Coprime (relatively prime)

Two integers whose only common divisor is 1, so their greatest common divisor is 1 (for example 9 and 28).

Prime factorization

Writing an integer as a product of prime numbers; the GCD uses the primes shared by all inputs at their lowest powers.

Divisor

A whole number that divides another exactly, leaving no remainder.

Frequently asked questions