Mathematics · Number Theory
Greatest Common Divisor Calculator
Calculate the greatest common divisor (GCD) of two integers using the Euclidean algorithm.
Calculator
Formula
a and b are two non-negative integers. The algorithm recursively replaces (a, b) with (b, a mod b) until b equals zero, at which point a is the GCD. The GCD is the largest positive integer that divides both a and b without a remainder.
Source: Euclid, Elements, Book VII, Propositions 1–2 (c. 300 BC); NIST Digital Library of Mathematical Functions, dlmf.nist.gov.
How it works
The Euclidean algorithm is one of the oldest known algorithms in mathematics, dating back to Euclid's Elements around 300 BC. Its core insight is that the GCD of two numbers does not change if the larger number is replaced by its remainder when divided by the smaller number. This process is repeated until the remainder is zero, and the last non-zero value is the GCD. Formally: gcd(a, b) = gcd(b, a mod b), with the base case gcd(a, 0) = a.
For example, to find gcd(48, 18): first compute 48 mod 18 = 12, so gcd(48, 18) = gcd(18, 12). Next, 18 mod 12 = 6, giving gcd(18, 12) = gcd(12, 6). Finally, 12 mod 6 = 0, so gcd(12, 6) = gcd(6, 0) = 6. The GCD of 48 and 18 is therefore 6. The algorithm converges rapidly — its number of steps is at most five times the number of decimal digits in the smaller input, making it highly efficient even for very large integers.
Once the GCD is known, the Least Common Multiple (LCM) is computed for free using the identity lcm(a, b) = |a × b| / gcd(a, b). The LCM is the smallest positive integer divisible by both a and b, and it appears naturally when adding or comparing fractions with different denominators. Together, the GCD and LCM fully characterize the divisibility relationship between any two integers.
Worked example
Suppose you need to simplify the fraction 252 / 336. The first step is to find the GCD of the numerator and denominator.
Step 1: Apply the Euclidean algorithm to 252 and 336.
336 mod 252 = 84 → gcd(336, 252) = gcd(252, 84)
252 mod 84 = 0 → gcd(252, 84) = gcd(84, 0) = 84
Step 2: Divide both numerator and denominator by the GCD.
252 ÷ 84 = 3
336 ÷ 84 = 4
Result: The fraction 252/336 simplifies to 3/4 in its lowest terms. We can also note that the LCM of 252 and 336 is (252 × 336) / 84 = 1008, which would be used as the common denominator if adding fractions with these denominators.
Limitations & notes
This calculator operates on non-negative integers only; inputting decimals or fractions will cause values to be rounded to the nearest integer before the calculation proceeds. By mathematical convention, gcd(0, 0) is undefined, but most computational implementations return 0 in this case, as this calculator does. For very large integers (beyond JavaScript's safe integer range of 2^53 − 1, or approximately 9 quadrillion), floating-point precision loss may produce incorrect results; for such cases, a BigInt-based implementation or a dedicated arbitrary-precision library should be used. The calculator accepts only two integers at a time; to find the GCD of three or more numbers, apply the algorithm iteratively: gcd(a, b, c) = gcd(gcd(a, b), c).
Frequently asked questions
What is the difference between GCD and HCF?
GCD (Greatest Common Divisor) and HCF (Highest Common Factor) are two names for exactly the same mathematical concept — the largest integer that divides two or more numbers without leaving a remainder. GCD is the term more commonly used in computer science and American mathematics curricula, while HCF is the traditional term used in British and Commonwealth educational systems. Both refer to the identical value computed by the Euclidean algorithm.
Why is the Euclidean algorithm preferred over trial division?
Trial division finds the GCD by testing every integer from 1 up to the smaller of the two inputs, which requires O(min(a, b)) steps and becomes impractical for large numbers. The Euclidean algorithm, by contrast, uses repeated modular reduction and converges in O(log(min(a, b))) steps — an exponentially faster approach. For two 100-digit numbers, trial division would require up to 10^100 operations, while the Euclidean algorithm completes in roughly 500 steps.
How is the GCD used in simplifying fractions?
To reduce a fraction a/b to its lowest terms, divide both the numerator and denominator by gcd(a, b). The result is the unique equivalent fraction where the numerator and denominator share no common factor other than 1 (i.e., they are coprime). For instance, gcd(36, 48) = 12, so 36/48 = (36÷12)/(48÷12) = 3/4. This is the standard algorithm used by all computer algebra systems when simplifying rational expressions.
What does it mean when the GCD of two numbers is 1?
When gcd(a, b) = 1, the two integers are said to be coprime or relatively prime. This means they share no common factor other than 1 itself; their prime factorizations have no primes in common. Coprimality is a critical property in number theory and cryptography — for example, RSA encryption relies on choosing two large primes p and q such that the public exponent e is coprime to (p−1)(q−1). Coprime integers always have an LCM equal to their product: lcm(a, b) = a × b.
Can the GCD be computed for more than two numbers?
Yes. The GCD of a set of integers {a₁, a₂, ..., aₙ} can be found by applying the two-number Euclidean algorithm iteratively: first compute gcd(a₁, a₂), then compute gcd of that result with a₃, and so on. This works because gcd is an associative operation: gcd(a, b, c) = gcd(gcd(a, b), c). The final result is the largest integer that divides every number in the set simultaneously.
Last updated: 2025-01-15 · Formula verified against primary sources.