Greatest Common Divisor: The Euclidean Algorithm

GCD, GCF and HCF are three names for the same thing, which is part of why the topic feels harder than it is. American textbooks say greatest common factor, British ones say highest common factor, and computer science says greatest common divisor. The answer is identical.

Listing factors works, until it doesn't

For small numbers, write both factor lists out. 48 divides by 1, 2, 3, 4, 6, 8, 12, 16, 24 and 48. 18 divides by 1, 2, 3, 6, 9 and 18. The values appearing in both lists are 1, 2, 3 and 6, so the greatest of them is 6.

That method collapses as soon as the numbers get awkward. Try it on 1,071 and 462 and you are testing dozens of candidates. This is where the algorithm earns its keep.

The Euclidean algorithm in three lines

Divide the larger number by the smaller and keep only the remainder. Then divide the old divisor by that remainder. Repeat until you reach zero, and the last non-zero remainder is your answer.

1,071 divided by 462 is 2 remainder 147. 462 divided by 147 is 3 remainder 21. 147 divided by 21 is 7 remainder 0. So the GCD is 21. Check it: 21 × 51 is 1,071 and 21 × 22 is 462. Three divisions and no guessing.

Prime factorisation as a cross-check

Break both numbers into primes and multiply the shared ones. 48 is 2^4 × 3 and 18 is 2 × 3^2. They share one 2 and one 3, so the GCD is 6. This is slower for large numbers, since factorising is hard work, but it is handy when you also need the lowest common multiple.

Where the answer gets used

Simplifying fractions is the everyday case. 48/18 has a GCD of 6, so dividing both parts by 6 gives 8/3. Doing that in one step rather than repeatedly halving is the difference between a tidy answer and a mess. There is more on that in the guide to simplifying fractions.

Then there is the tiling problem, which is the one that makes GCD click. A floor measures 336cm by 210cm and you want the largest square tile that fits a whole number of times in both directions with no cutting. Run the algorithm: 336 divided by 210 leaves 126, 210 divided by 126 leaves 84, 126 divided by 84 leaves 42, and 84 divided by 42 leaves 0. A 42cm tile works, giving 8 across and 5 down.

GCD and LCM are two sides of one coin

For any two numbers, the GCD multiplied by the LCM equals the product of the numbers themselves. 48 × 18 is 864. The GCD is 6, so the LCM must be 864 divided by 6, which is 144. Find one and you have the other for free.

How to use the GCD calculator

Type your numbers into the input fields, one per box, or separated by commas if the tool accepts a list. The answer appears with the working, and most versions show the Euclidean steps, which is what you want when homework asks for a method rather than a result. For fraction work, the fraction calculator guide handles the reduction in one move.

Whole numbers only. Decimals and negatives are either rejected or converted, since divisibility is defined for integers. If you have 4.8 and 1.8, scale both by ten, find the GCD of 48 and 18, then scale back.

Common questions

What is the GCD of a number and zero? It is the number itself. Every integer divides zero exactly, so the largest common divisor of 15 and 0 is 15. The Euclidean algorithm relies on this, since a remainder of zero is what tells it to stop.

Can I find the GCD of three or more numbers? Yes, by working in pairs. Take the GCD of the first two, then the GCD of that result with the third, and carry on. For 48, 18 and 30: GCD(48,18) is 6, and GCD(6,30) is 6.

What if the two numbers share nothing? Then the GCD is 1 and the numbers are called coprime. 8 and 15 are an example, despite neither being a prime number. A fraction whose numerator and denominator are coprime is already in its lowest terms.

Is GCF the same as GCD? Yes, and so is HCF. The wording depends on which side of the Atlantic your textbook was written, not on the maths.