GCD Calculator

Think of the GCD as the size of the largest identical tile you can use to perfectly cover two different-length walls without cutting any tile. If one wall is 36 cm and another is 48 cm, the largest tile that fits both without cutting is 12 cm. That is the GCD — not a theoretical concept but a physical constraint on how things divide evenly.

The Euclidean algorithm computes this by repeated subtraction expressed as division with remainder. At each step, you replace the larger number with the remainder from dividing it by the smaller. The process terminates because remainders strictly decrease with each step, and it terminates at zero, leaving behind the GCD. For numbers with hundreds of digits, this algorithm still finishes in microseconds because the number of steps grows only logarithmically with the size of the inputs.

When you extend GCD to three or more numbers, you apply it sequentially: find the GCD of the first two, then find the GCD of that result with the third number, and so on. This works because GCD is associative — the order of operations does not affect the answer. The tool handles this automatically when you enter optional third or fourth numbers.

Use the GCD calculator when you need to simplify fractions to lowest terms, reduce a ratio to its smallest integer form, or figure out how to split multiple quantities into the maximum number of equal groups. It also appears in cryptography (checking that a public key exponent and phi(n) are coprime) and in computer science when computing hash table sizes or stride lengths for memory access patterns.

The GCD is also useful for checking whether two measurements are commensurable — that is, whether they share a rational ratio. If GCD(a, b) is large relative to both numbers, the quantities are closely related by simple whole-number multiples. If GCD returns 1, the measurements are in an irreducible ratio.

Do not use this tool when your inputs are not integers. Floating-point numbers, measurements with decimal precision, or irrational quantities like pi or square roots do not have a GCD in the classical sense. In those cases, you need a numerical approximation method, not the Euclidean algorithm. Also, GCD is not the right tool when you are looking for the smallest shared multiple — that is the LCM, which is a distinct calculation even though the two are mathematically related.

Confusing GCD with LCM. The greatest common divisor and the least common multiple are related but opposite in direction. GCD finds the largest factor shared by all numbers; LCM finds the smallest multiple shared by all numbers. A common mistake when adding fractions is dividing by GCD when you should be multiplying by LCM for the denominator. They are connected by the identity: GCD(a, b) x LCM(a, b) = a x b.

Assuming coprime means prime. Saying two numbers have GCD 1 only means they share no common prime factor. Both numbers can be composite — 8 and 9 are coprime because 8 = 2 x 2 x 2 and 9 = 3 x 3 share no prime. If you use the GCD result to argue that a number is prime itself, that conclusion does not follow.

Applying GCD to non-integers. GCD is defined only for integers. Entering a decimal like 3.5 and 7 does not produce a meaningful result. In practice, if you need the GCD of rational numbers, convert them to integers first by multiplying through by the common denominator. This calculator explicitly rejects decimal inputs to prevent silent wrong answers.

The formal definition: GCD(a, b) is the largest integer d such that d divides a and d divides b. Every common divisor of a and b also divides GCD(a, b) — this makes GCD the generator of the set of all common divisors.

The Euclidean algorithm expressed as a recurrence: GCD(a, b) = GCD(b, a mod b), with base case GCD(a, 0) = a. Each step reduces the problem size because the remainder is always strictly less than the divisor. The number of division steps is at most five times the number of decimal digits in the smaller input — a bound proven by Gabriel Lame in 1844, making this one of the oldest complexity analyses in mathematics.

For multiple inputs, GCD(a, b, c) = GCD(GCD(a, b), c). The simplified ratio displayed by this tool divides each original number by the GCD, producing the smallest-integer representation of their proportional relationship. If GCD(a, b) = 1, the ratio a:b is already in its simplest form and cannot be reduced further without introducing fractions.

The Euclidean algorithm assumes exact integer arithmetic — it produces exact results because integers have no rounding error. At the boundary, numbers near the limit of JavaScript safe integers (above 2^53 - 1, roughly 9 quadrillion) will silently lose precision because JavaScript represents all numbers as 64-bit floats. For inputs above roughly 1 billion, this calculator warns you; for cryptographic applications where 1024-bit or 2048-bit integers are involved, you need a big-integer library, not floating-point arithmetic. The Euclidean algorithm itself is correct at any precision — the constraint is the representation, not the algorithm.