Greatest Common Divisor Calculator

Background.

The greatest common divisor earns its keep in a handful of everyday jobs: reducing a fraction to lowest terms, cutting two lengths into equal pieces with nothing left over, or finding the largest square tile that fits a rectangle exactly. For 252 and 105 the answer is 21, which is why 105/252 reduces to 5/12 and why a 252 cm by 105 cm panel divides cleanly into 21 cm squares, 12 along one side and 5 along the other.

There are two ways to find it. The school method factors both numbers into primes and keeps what they share: 252 = 2² × 3² × 7 and 105 = 3 × 5 × 7, so the common part is 3 × 7 = 21. That works for small numbers but becomes hopeless once they get large, because factoring large numbers is hard.

The method used here is older and far faster. Euclid set it out in Book VII of the Elements around 300 BC: divide the larger number by the smaller, keep the remainder, and repeat with the smaller number and that remainder until the remainder is zero. The divisor used in that final, exact division is the answer. It works because anything that divides both a and b also divides a − qb, so replacing the pair (a, b) with (b, a mod b) never changes the set of common divisors.

It stays quick for enormous inputs. Gabriel Lamé proved in 1844 that the number of division steps never exceeds five times the number of digits in the smaller number; the slowest pairs are consecutive Fibonacci numbers, where every quotient is 1.

Both inputs must be positive whole numbers — zero, negatives and decimals are refused. The answer is exact at every size the page accepts, up to the 15-digit input limit.

What is greatest common divisor calculator?

The greatest common divisor of two positive integers a and b, written gcd(a, b), is the largest whole number that divides both without a remainder. It is always at least 1; when it equals 1 the numbers are called coprime, or relatively prime, and share no prime factor. It is also the smallest positive number that can be written as ax + by with whole numbers x and y, a fact known as Bézout's identity.

How to use this calculator.

1. 01Enter the two whole numbers in either order; if the second is larger, the first division step simply swaps them.
2. 02If you are simplifying a fraction, enter its numerator and denominator, then divide both by the result.
3. 03For three or more numbers, work in pairs: find the GCD of the first two, then the GCD of that answer and the third number, and so on.
4. 04Read the GCD. A result of 1 means the numbers are coprime, so a fraction made from them is already in lowest terms.

The formula.

The rule is gcd(a, b) = gcd(b, a mod b), where a mod b is the remainder left when a is divided by b. Applied over and over, it shrinks the pair until the second number reaches zero, and gcd(g, 0) = g ends the process. Each step preserves the common divisors: if d divides a and b, it divides a − q·b, which is exactly the remainder, and anything dividing b and the remainder also divides a. The remainder is always smaller than b, and the first number of the pair at least halves every two steps, so even 15-digit inputs need no more than 75 divisions by Lamé's bound. The work is done with exact integer remainders, never by factoring, so no prime factorization is needed at any point.

A worked example.

Frequently asked questions.

References& sources.

1. [1]NIST Digital Library of Mathematical Functions, section 27.2, Functions of Number Theory.
2. [2]Euclid, Elements, Book VII, Propositions 1–2 (public translation).
3. [3]BIPM, The International System of Units (SI Brochure), 9th ed., version 3.01, coherent derived units and quantity equations.