GCD (Greatest Common Divisor) Calculator

Euclidean algorithm: gcd(a,b) = gcd(b, a mod b). Supports 2-6 integers.

Inputs

Result

Loading calculator…
—

General calculation reads

Amazon affiliate
How Not to Be Wrong
Jordan Ellenberg - math thinking
Shop on Amazon
The Joy of X
Steven Strogatz - accessible math
Shop on Amazon
Scientific calculator (Casio fx-991EX)
Shop on Amazon

As an Amazon Associate we may earn from qualifying purchases. This does not add cost for you.

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 ≠ 0

The 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).

Sources: NIST DADS — Euclidean algorithm · OEIS A050873 — gcd table · Knuth, The Art of Computer Programming Vol. 2 §4.5.2 — analysis of Euclid's algorithm

Worked examples

Example 1
Small inputs
Inputs:
a = 48, b = 18
Output:
48 mod 18 = 12 → 18 mod 12 = 6 → 12 mod 6 = 0 → gcd = 6
Example 2
Coprime inputs
Inputs:
a = 35, b = 8
Output:
gcd = 1 (35 and 8 share no common prime factor)
Example 3
One argument is zero
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.

Frequently asked

What's the difference from LCM?+
GCD = greatest common factor (divides both). LCM = smallest common multiple (both divide it). Linked by gcd(a,b) × lcm(a,b) = a×b.
How fast is Euclidean?+
O(log(min(a,b))) — even for huge numbers, finishes in microseconds. Used in cryptography (RSA key gen).
Negative numbers?+
GCD is always positive. Calculator takes absolute values automatically.
Is gcd(0, n) = n?+
Yes — by convention. Every integer divides 0; n is the largest divisor of itself.
How is this used in fractions?+
Divide numerator and denominator by their GCD to put fraction in simplest form. 48/36 ÷ gcd 12 = 4/3.

Related calculators

LCM (Least Common Multiple) Calculator
lcm(a,b) = |a × b| / gcd(a,b). Smallest number that both a and b divide evenly.
Prime Number Checker
Is n prime? Trial division up to √n; identifies smallest divisor and nearest primes if composite.
Prime Factorization Calculator
n = p₁^a₁ × p₂^a₂ × … Trial division to find all prime factors with multiplicity.
Factorial Calculator (n!)
n! = 1 × 2 × … × n. Computes exactly up to 21! (number limit); approximate via Stirling for larger.
Scientific Notation Converter
Convert decimal ↔ scientific notation. Standard form a × 10^b with 1 ≤ |a| < 10.
Square Root Calculator (√n)
√n with integer-perfect-square check, simplified surd form, and decimal expansion.

More tools you might like

Hand-picked tools that pair well with this one — same audience, same intent.

LCM (Least Common Multiple) Calculator
Calc

lcm(a,b) = |a × b| / gcd(a,b). Smallest number that both a and b divide evenly.

Prime Number Checker
Calc

Is n prime? Trial division up to √n; identifies smallest divisor and nearest primes if composite.

Prime Factorization Calculator
Calc

n = p₁^a₁ × p₂^a₂ × … Trial division to find all prime factors with multiplicity.

Factorial Calculator (n!)
Calc

n! = 1 × 2 × … × n. Computes exactly up to 21! (number limit); approximate via Stirling for larger.

Scientific Notation Converter
Calc

Convert decimal ↔ scientific notation. Standard form a × 10^b with 1 ≤ |a| < 10.

Research Informed Consent Form (Common Rule)
Docs

Informed consent for human-subjects research compliant with 45 CFR § 46.116 (Revised Common Rule, 2018) — includes key information section, risks/benefits, IRB contacts.