GCD (Greatest Common Divisor) Calculator
Euclidean algorithm: gcd(a,b) = gcd(b, a mod b). Supports 2-6 integers.
Result
How to use this calculator
- Enter 2-4 positive integers.
- Leave optional fields at 0 to ignore.
About this calculator
The GCD (greatest common divisor) of two integers is the largest number that divides both without remainder. The Euclidean algorithm runs gcd(a,b) = gcd(b, a mod b) until b=0, completing in O(log min(a,b)) steps. For 3+ numbers, GCD is associative: gcd(a,b,c) = gcd(gcd(a,b),c). Common use: simplifying fractions (48/36 → divide by gcd 12 → 4/3), and finding shared periods in problems involving multiple cycles.
How it works — the formula
Euclid's algorithm:
gcd(a, 0) = a
gcd(a, b) = gcd(b, a mod b) when b ≠ 0The greatest common divisor of two non-negative integers is the largest integer that divides both. Euclid's algorithm (Elements VII.1, ~300 BC) computes it in O(log min(a,b)) by repeatedly replacing the larger argument with the remainder of the larger divided by the smaller. The same algorithm extends to find Bézout coefficients (integers x, y with ax + by = gcd(a,b)), which underlies modular inverses in cryptography (RSA, Diffie-Hellman).
Worked examples
- Inputs:
- a = 48, b = 18
- Output:
- 48 mod 18 = 12 → 18 mod 12 = 6 → 12 mod 6 = 0 → gcd = 6
- Inputs:
- a = 35, b = 8
- Output:
- gcd = 1 (35 and 8 share no common prime factor)
- Inputs:
- a = 17, b = 0
- Output:
- gcd(17, 0) = 17 (any number divides 0)
Limitations
- Defined here for non-negative integers; extending to rationals or polynomials uses the same recurrence on the relevant Euclidean domain.
- gcd(0, 0) is conventionally 0 — there is no largest divisor of zero.
- For very large integers (cryptographic sizes, hundreds of digits), use a BigInt-backed implementation; double-precision overflows around 2⁵³.
- The "binary GCD" (Stein's algorithm) avoids modulo on hardware where division is slow.
Implementation uses iterative Euclidean reduction; result is exact for inputs within the safe-integer range.