Enter the numbers in the calculator: the first line of the result gives the GCD, and below it the divisions of Euclid’s algorithm appear, one per line. A single example is enough to see the three routes that lead to the same value.
Worked example: the GCD of 18 and 48
You want to simplify 18/48 and cut two boards, 18 in and 48 in long, into equal pieces that are as long as possible. How long is each piece?
- With factors. The factors of 18 are 1, 2, 3, 6, 9, and 18; those of 48 are 1, 2, 3, 4, 6, 8, 12, 16, 24, and 48. The common ones are 1, 2, 3, and 6.
- With prime factors. 18 = 2 × 3² and 48 = 2⁴ × 3. For each shared prime, take the smaller exponent: 2 × 3 = 6.
- With Euclid. 48 = 18 × 2 + 12; 18 = 12 × 1 + 6; 12 = 6 × 2 + 0. The last divisor before the remainder 0 is 6.
- Use the value. Each piece is 6 in long. Also, 18 ÷ 6 = 3 and 48 ÷ 6 = 8, so 18/48 = 3/8.
Result: GCD(18, 48) = 6.
Check: 6 fits 3 times into 18 and 8 times into 48, and 3 and 8 have no common factor greater than 1. If the GCD were larger, those quotients could still be simplified.
Listing factors works for small numbers, and prime factors when you already have them; with large numbers, Euclid’s algorithm is the short route because it only divides. To see the factorization of each number, use prime factorization.
When to use the GCD and when to use the LCM
The two show up in problems that look alike, but they answer opposite questions. The GCD splits what you have into equal pieces that are as large as possible; the LCM looks for the first point where several measures line up.
| Question | Calculation | Example |
|---|---|---|
| Simplify a fraction | GCD | 36/60: GCD 12, leaves 3/5 |
| Cut equal pieces, as long as possible | GCD | Strips of 42 in and 56 in: pieces of 14 in |
| Share with nothing left over, in the most groups | GCD | 30 pencils and 45 erasers: 15 groups |
| Add fractions with different denominators | LCM | 1/4 + 1/6: common denominator 12 |
| Find when two cycles line up | LCM | Every 4 and every 6 days: after 12 days |
The table already tells you where to start: if you need to divide, it is the GCD, and if you need to combine, it is the LCM. For word problems, the guide to GCD and LCM word problems sorts them with more cases, and GCD vs. LCM explains the rule for deciding.
This calculator shows only the GCD. For two numbers, the LCM follows from it: LCM = product ÷ GCD. With 18 and 48 that is 864 ÷ 6 = 144. If you would rather calculate it directly, enter the same numbers in the LCM calculator.
What you will see in the result
The result shows one line per division. If you enter 18 and 48 in that order, the first line is 18 = 48 × 0 + 18: because the first number is smaller, that division only swaps the pair and does not change the GCD. If you enter 48 and 18, that line does not appear. Either way the result is the same, because the GCD does not depend on the order.
When the numbers are the numerator and denominator of a fraction, divide both by the GCD and you get the fraction in lowest terms. If you want the result directly, the simplify fractions calculator does it without intermediate steps. Dividing by the GCD simplifies; multiplying the numerator and denominator by the same number builds up to an equivalent fraction, and the equivalent fractions page shows both operations together.
Frequently asked questions
How do you find the GCD of three numbers?
Find the GCD of the first two, then the GCD of that result and the third. With 20, 28, and 44: GCD(20, 28) = 4 and GCD(4, 44) = 4. The calculator does these pairs for you with up to 20 integers and numbers the divisions in one sequence.
What happens if one of the numbers is 0?
Zero is divisible by every integer, so GCD(0, 9) = 9: the zero does not change the result. If all the numbers are 0, there is no greatest common divisor, and the calculator returns 0 by convention and says so in the answer.
Can the GCD be negative?
No. The calculator uses absolute values, because a sign does not change which numbers divide evenly: GCD(−35, 14) = 7. Type the minus sign right before the number, as in -35, with each integer on its own line.
How many divisions does it need with very large numbers?
Very few. By Lamé’s theorem, Euclid’s algorithm takes at most five times the number of digits of the smaller of the two numbers. That is why no factoring is needed, even with a hundred digits. The Euclidean algorithm guide explains why.