GCD Calculator (Greatest Common Divisor)
Enter two to four whole numbers. Leave the third and fourth at 0 if you only need two.
Updated
Report a problem
Formula
The greatest common divisor comes from the Euclidean algorithm: gcd(a, b) = gcd(b, a mod b), repeated until the remainder is 0. For more than two numbers, fold it: gcd(a, b, c) = gcd(gcd(a, b), c).
Worked example
For 48 and 18: 48 = 2 × 18 + 12, then 18 = 1 × 12 + 6, then 12 = 2 × 6 + 0. The last non-zero remainder is 6, so gcd(48, 18) = 6. With a third number, 12, 18 and 30 give gcd(12, 18) = 6 and gcd(6, 30) = 6.
Frequently asked questions
What is the greatest common divisor?
It is the largest whole number that divides every number you entered with no remainder. The GCD of 48 and 18 is 6, because 6 goes into both and nothing larger does.
How does the Euclidean algorithm work?
Divide the larger number by the smaller and keep the remainder, then repeat with the smaller number and that remainder until the remainder is 0. For 48 and 18: 48 = 2 × 18 + 12, 18 = 1 × 12 + 6, 12 = 2 × 6 + 0, so the GCD is 6.
How do I find the GCD of three or four numbers?
Take the GCD of the first two, then the GCD of that result with the next number, and so on. For 12, 18 and 30: GCD(12, 18) = 6, then GCD(6, 30) = 6.
What does it mean when the GCD is 1?
The numbers are relatively prime (coprime): they share no factor except 1. For example, 17 and 5 have a GCD of 1. A fraction whose numerator and denominator have GCD 1 is already in lowest terms.