GCD Calculator
Find the Greatest Common Divisor (GCD) of two integers instantly.
Did this tool answer your question?
Thanks — this helps us improve the tool.
How to use this tool
- Enter first number and second number in the fields above.
- Results update instantly as you type — or click Calculate.
- Read your gcd and the full breakdown beneath it.
Enter two integers to find their Greatest Common Divisor (GCD) using the Euclidean algorithm.
Formula
GCD(a, b) computed via the Euclidean algorithm:
Repeat: a, b = b, a mod b until b = 0; then GCD = a
How it works
The calculator finds the Greatest Common Divisor of two integers using the Euclidean algorithm: it repeatedly replaces the larger number with the remainder of dividing the larger by the smaller until the remainder is zero, at which point the non-zero value is the GCD. Both inputs are treated as absolute values, so negative integers are handled correctly. The algorithm is exact for all integers and runs in O(log min(a, b)) steps.
Worked example
- Start: a = 12, b = 8
- Step 1: a = 8, b = 12 mod 8 = 4
- Step 2: a = 4, b = 8 mod 4 = 0
- b = 0, so GCD = 4
GCD(12, 8) = 4.
Common mistakes to avoid
- Entering non-integer values such as decimals or fractions -- GCD is defined only for integers and will return a meaningless or error result for non-integer inputs.
- Confusing GCD with LCM: GCD finds the largest shared factor (used to reduce fractions), while LCM finds the smallest shared multiple (used to add fractions) -- they solve opposite problems.
- Assuming GCD(0, n) is undefined -- by mathematical convention GCD(0, n) = n, which the Euclidean algorithm handles correctly but can surprise users who expect an error.
Key terms
- Greatest Common Divisor (GCD)
- The largest positive integer that divides both numbers without leaving a remainder; also called the Greatest Common Factor (GCF).
- Euclidean algorithm
- An efficient method for computing GCD by repeatedly taking remainders; described by Euclid around 300 BCE and still in widespread use.
- Divisor
- An integer that divides another integer exactly, leaving no remainder.
- Coprime (relatively prime)
- Two integers are coprime when their GCD equals 1, meaning they share no common factor other than 1.
- Modulo (mod)
- The remainder after dividing one integer by another; the core operation in the Euclidean algorithm.
Frequently asked questions
- What is GCD?
- The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides both numbers without a remainder.