GCD Calculator
Find the greatest common divisor — the largest integer that divides two whole numbers exactly with no remainder. Use it to simplify fractions, reduce ratios, and solve number-theory problems.
Last updated: May 2026
Compare with similar
About this calculator
The greatest common divisor (GCD, also called the greatest common factor) of two integers a and b is the largest positive integer that divides both without a remainder. This calculator uses the Euclidean algorithm, which repeatedly replaces the pair (a, b) with (b, a mod b) until the second number becomes 0; the last nonzero value is the GCD. Formally, gcd(a, b) = gcd(b, a mod b), with gcd(a, 0) = a as the base case. Here num1 and num2 are the two inputs, and the tool takes absolute values first, since gcd is defined for magnitudes. The Euclidean method is extremely efficient — it runs in time proportional to the number of digits, far faster than listing every factor. Key edge cases: gcd(a, 0) = |a|, gcd(0, 0) is conventionally 0, and gcd(a, b) = 1 means the numbers are coprime (share no common factor besides 1). The GCD also satisfies the identity gcd(a, b) × lcm(a, b) = |a × b|, which links it directly to the least common multiple. Because every common divisor of a and b also divides their GCD, it is the natural tool for reducing fractions to lowest terms.
How to use
Example 1 — gcd(48, 18). Enter First Number = 48 and Second Number = 18. Apply the Euclidean algorithm: 48 = 2·18 + 12, then 18 = 1·12 + 6, then 12 = 2·6 + 0. The last nonzero remainder is 6, so gcd(48, 18) = 6. Verify by factoring: 48 = 2⁴·3 and 18 = 2·3², and the shared part is 2·3 = 6. Example 2 — gcd(1071, 462). Enter First Number = 1071 and Second Number = 462. Steps: 1071 = 2·462 + 147, then 462 = 3·147 + 21, then 147 = 7·21 + 0. The GCD is 21. Verify: 1071 = 3·7·51 = 3·7·3·17 (i.e. 3²·7·17) and 462 = 2·3·7·11; the common factors are 3·7 = 21.
Frequently asked questions
What is the difference between GCD and LCM?
The greatest common divisor is the largest number that divides both inputs, while the least common multiple is the smallest number that both inputs divide into. They are complementary: GCD pulls out shared factors, LCM combines all factors. They are linked by the identity gcd(a, b) × lcm(a, b) = |a × b|, so once you know one you can get the other. A common mistake is to use GCD when adding fractions — there you actually need the LCM of the denominators for a common denominator. Use GCD to reduce a fraction to lowest terms and LCM to find a shared denominator.
What does it mean when the GCD is 1?
It means the two numbers are coprime (also called relatively prime): they share no common factor other than 1. Coprimality does not require either number to be prime — for example 8 and 9 are coprime even though neither is prime. This property is important in number theory and cryptography; for instance, RSA relies on choosing an exponent coprime to a totient value. A fraction is already in lowest terms exactly when its numerator and denominator are coprime. So a GCD of 1 is a signal that there is nothing left to simplify.
Why is the Euclidean algorithm faster than listing factors?
Listing all factors of a number requires testing divisors up to its square root, which becomes slow for large inputs. The Euclidean algorithm instead shrinks the problem rapidly: each step replaces the larger number with a remainder that is strictly smaller, and the numbers fall in size very quickly. Its running time is proportional to the number of digits, not the size of the values, so it handles huge numbers almost instantly. This efficiency is why it has been in continuous use for over two thousand years. Trying to factor both numbers fully is the common but unnecessarily slow approach.
Can the GCD be found for negative numbers or zero?
Yes. The GCD is defined in terms of magnitude, so this calculator takes absolute values first: gcd(−48, 18) is the same as gcd(48, 18) = 6. For zero, the convention is gcd(a, 0) = |a|, because every integer divides 0, making a itself the largest divisor the pair shares. The single ambiguous case is gcd(0, 0), which is conventionally taken to be 0 since there is no largest common divisor. A frequent mistake is to expect a sign on the result; by definition the GCD is always a non-negative integer.
When should I NOT use a GCD calculator?
Do not use it when you actually need a common denominator or a synchronization cycle — those call for the least common multiple instead. It is also not the right tool for non-integer inputs; GCD is defined only for whole numbers, so decimals or fractions must be cleared first. If you need the full prime factorization (for example to find every divisor), a factorization tool is more informative than the single GCD value. And for more than two numbers, remember that gcd(a, b, c) must be built up stepwise as gcd(gcd(a, b), c), since a basic two-input calculator handles only a pair at a time. Choose the tool that matches whether you need shared factors, multiples, or a full factor list.