Greatest Common Divisor Calculator
Find the greatest common divisor (also called the greatest common factor or highest common factor) of two to twenty whole numbers. For two numbers the calculator shows every step of the Euclidean algorithm and the fraction in lowest terms.
Two to 20 whole numbers, separated by spaces or new lines.
Result
Enter at least two whole numbers.
The calculation runs in this browser tab. Nothing you enter is uploaded, saved or logged.
What is the greatest common divisor?
The greatest common divisor (GCD) of a set of whole numbers is the largest whole number that divides each of them without a remainder. The divisors of 48 include 1, 2, 3, 4, 6, 8, 12, 16, 24 and 48; those of 18 include 1, 2, 3, 6, 9 and 18. The largest one they share is 6, so GCD(48, 18) = 6.
The GCD is what you divide by to simplify a fraction: 48/18 becomes 8/3 after dividing both parts by 6. When the GCD of two numbers is 1 they are called coprime (or relatively prime): they share no factor other than 1.
How to use the Greatest Common Divisor Calculator
- Type two or more whole numbers, separated by spaces or new lines. Commas are accepted if followed by a space.
- Read the greatest common divisor. For two numbers the table below it lists each division of the Euclidean algorithm.
- The details show whether the numbers are coprime, the prime factors of the GCD and, for two numbers, the fraction in lowest terms.
- Use Copy result to copy the GCD, or Reset to clear the list.
Formula
- Euclidean algorithm
- GCD(a, b) = GCD(b, a mod b), repeated until the remainder is 0
- More than two numbers
- GCD(a, b, c) = GCD(GCD(a, b), c)
- Special cases
- GCD(a, 0) = |a| and GCD(0, 0) is undefined
Each step replaces the pair (a, b) by (b, remainder of a ÷ b). The last non-zero remainder is the GCD. For 48 and 18: 48 = 2 × 18 + 12, then 18 = 1 × 12 + 6, then 12 = 2 × 6 + 0, so the GCD is 6.
The GCD and the least common multiple are linked: for two numbers, GCD × LCM = a × b.
Worked example
The GCD of 48 and 18, with the fraction 48/18 reduced. These are the results the calculator gives:
| Question | Result |
|---|---|
| Input: Whole numbers | 48, 18 |
| Greatest common divisor | 6 |
| Numbers | 48, 18 |
| Coprime | No |
| Prime factors of the GCD | 2 × 3 |
| Fraction in lowest terms | 48/18 = 8/3 |
Assumptions and limits
- Only whole numbers are accepted. For decimals, scale them to whole numbers first (1.5 and 2.5 become 15 and 25).
- Negative numbers are treated by their absolute value, since divisors do not depend on sign.
- Between two and 20 numbers can be entered, each with up to 30 digits. The arithmetic is exact, with no rounding.
- The GCD of several zeros is undefined and the calculator reports it instead of showing 0.
- The Euclidean table is shown for exactly two numbers; with more numbers the result is the same method applied repeatedly.
Frequently asked questions
How do I find the greatest common divisor?
The quickest method is the Euclidean algorithm: divide the larger number by the smaller, replace the larger by the remainder, and repeat until the remainder is 0. The last non-zero remainder is the GCD. You can also list all divisors of each number and pick the largest shared one, or compare their prime factorisations.
Are GCD, GCF and HCF the same thing?
Yes. Greatest common divisor (GCD), greatest common factor (GCF) and highest common factor (HCF) are three names for the same number, used in different countries and textbooks.
How do I use the GCD to simplify a fraction?
Divide the numerator and the denominator by their GCD. For 48/18 the GCD is 6, giving 8/3. The result is in lowest terms exactly when the new numerator and denominator are coprime.
What does coprime mean?
Two numbers are coprime when their GCD is 1, so no number greater than 1 divides both. 8 and 15 are coprime even though neither is prime. The calculator states it in the details.
What is the GCD of a number and 0?
Every number divides 0, so GCD(a, 0) is the absolute value of a. GCD(0, 0) has no largest common divisor, so it is undefined.
Can I find the GCD of more than two numbers?
Yes. Enter up to 20 numbers; the calculator takes the GCD of the first two, then the GCD of that result with the third, and so on. The table of steps is shown only for pairs.