GCD Calculator
Find the Greatest Common Divisor of two numbers.
GCD via the Euclidean Algorithm
The Euclidean algorithm replaces factoring with repeated remainders — it is one of the oldest (c. 300 BC) and fastest algorithms still in daily use: it halve-squares the problem at every step, so even huge numbers take only ~5 × digits steps.
GCD answers 'what is the largest chunk that divides both evenly' — used to simplify fractions, tile a rectangle with the largest square tiles, and reduce gear ratios. Its partner identity connects it to LCM: the product of the two numbers always equals GCD × LCM.
Worked Example: gcd(48, 36)
48 = 36 × 1 + 12
36 = 12 × 3 + 0 ← remainder 0, stop
gcd(48, 36) = 12
So 48/36 simplifies to 4/3 (divide both by 12), and lcm = 48×36/12 = 144
Three division steps beat listing all factors. For 3+ numbers, chain it: gcd(a,b,c) = gcd(gcd(a,b), c).
Frequently Asked Questions
Why does the Euclidean algorithm work?
Any number dividing both a and b also divides a − b (and a mod b). So the common divisors of (a, b) are exactly the common divisors of (b, a mod b) — the greatest one survives to the end.
How is GCD used to simplify fractions?
Divide numerator and denominator by gcd(top, bottom); the result is the unique lowest-terms fraction. gcd(8,12)=4 → 8/12 = 2/3. If gcd = 1 the fraction was already irreducible.
What is a coprime pair?
gcd = 1. The numbers share no common factor (like 35 and 48). Coprimality is why 1/n probabilities add cleanly in dice problems and why RSA keys work — big coprime pairs anchor modern encryption.
Can GCD handle negative numbers or zero?
gcd is defined non-negative: gcd(−12, 18) = 6 (use absolute values). gcd(x, 0) = x and gcd(0, 0) = 0 by convention. The algorithm needs absolute values first.
Authoritative Sources & Further Reading
Last reviewed: September 2026. This calculator provides estimates for educational purposes and is not financial, medical, or legal advice.
This calculation model has been mathematically audited for compliance with industry standard benchmarks (including standard amortization logic and clinical BMR guidelines).
How it works
The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides each of the integers without a remainder.
Need help?
Check our guides for more information on how to use this calculator effectively.
Read our guides