GCD Calculator
Calculate the Greatest Common Divisor (GCD) of two or more numbers using the Euclidean algorithm, with step-by-step working shown.
Numbers
#1
#2
GCD
12
Step-by-Step
Start with 48
GCD(48, 36) = 12
How to Calculate the GCD (Greatest Common Divisor)
The Greatest Common Divisor (GCD) is the largest positive integer that divides all of the given numbers without leaving a remainder. This calculator uses the Euclidean algorithm: for two numbers, it repeatedly replaces the larger number with the remainder of dividing the larger by the smaller, until the remainder is zero. The last non-zero remainder is the GCD.
For more than two numbers, the GCD is computed pairwise: GCD(a, b, c) = GCD(GCD(a, b), c). Add two or more numbers below to see the step-by-step computation.
Example
For 48 and 36: 48 = 36 × 1 + 12, then 36 = 12 × 3 + 0. Since the remainder reached 0, the GCD is 12. This means 12 is the largest number that divides both 48 and 36 evenly.
Common Use Cases
- Simplifying fractions to their lowest terms (e.g. 48/36 simplifies to 4/3 using GCD 12).
- Finding the greatest common factor in number theory problems.
- Helping with Diophantine equations and modular arithmetic.
- Scaling ratios down to their simplest whole-number form.
FAQs
What is the GCD of 1 and any number?
The GCD of 1 and any positive integer is always 1, because 1 is the only positive divisor of 1. This means the two numbers are "coprime" or "relatively prime."
Can the GCD be larger than the smallest number?
No — the GCD of a set of numbers can never be larger than the smallest number in the set, since a divisor cannot be greater than the number it divides.
What happens if I enter 0?
Zero is excluded from the calculation. If all entries are zero, the result will be 0. For any positive number n, GCD(n, 0) = n.