On this page
The long division method, also called continued division, finds the HCF of two numbers without listing a single factor. You keep dividing, each remainder becomes the next divisor, and the answer appears when a division comes out exact. It is quick for big numbers where prime factorisation gets slow, and one extra round handles three numbers.
What is the long division method for HCF?
The method dates back to Euclid's Elements, written around 300 BC. Book VII, Proposition 2 sets out how "to find the greatest common measure of two given numbers not relatively prime" by repeatedly subtracting the smaller number from the larger. Dividing is just a fast way of doing those subtractions in one go.
The whole method rests on one fact: the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. Replace the larger number by its remainder instead, and you have taken away many copies of the smaller one at once, so the HCF still does not change. The numbers shrink at every step until one divides the other exactly.
How do you find the HCF of two numbers by long division?
Follow these steps:
Divide the larger number by the smaller one.
If the remainder is 0, the divisor is the HCF. Stop.
If not, make the old divisor the new dividend and the remainder the new divisor.
Repeat until the remainder is 0. The last divisor is the HCF.
Take 384 and 144.
384 ÷ 144 = 2, remainder 96, because 384 = 144 × 2 + 96.
144 ÷ 96 = 1, remainder 48, because 144 = 96 × 1 + 48.
96 ÷ 48 = 2, remainder 0, because 96 = 48 × 2 + 0.
The remainder is 0 and the last divisor is 48, so HCF(384, 144) = 48.
How do you find the HCF of three numbers by long division?
You never divide three numbers at once. For three or more numbers, gcd(a, b, c) = gcd(gcd(a, b), c), so you find the HCF of any two, then run the method again on that answer and the third number.
Find the HCF of 144, 384 and 504.
Round 1: HCF(384, 144) = 48, as worked out above.
Round 2: now find HCF(504, 48).
504 ÷ 48 = 10, remainder 24, because 504 = 48 × 10 + 24.
48 ÷ 24 = 2, remainder 0, because 48 = 24 × 2 + 0.
The last divisor is 24, so HCF(144, 384, 504) = 24.
Notice that the final answer, 24, is smaller than the 48 from round 1. That is normal: 48 divides 144 and 384, but not 504, so the third number pulls the answer down.
Check the answer by dividing back: 144 ÷ 24 = 6, 384 ÷ 24 = 16 and 504 ÷ 24 = 21. All three are exact, and no number other than 1 divides all of 6, 16 and 21, so 24 really is the highest.
How do you check each remainder?
One bad division in the middle throws off every line after it. Run these two checks on every line before moving on:
Size check: the remainder must be smaller than the divisor. If you get 504 ÷ 48 = 9 remainder 72, the remainder is bigger than 48, so the quotient is too small. Try 10.
Rebuild check: divisor × quotient + remainder must give back the dividend exactly. For the line above, 48 × 10 + 24 = 480 + 24 = 504. If it does not match, redo that line.
What mistakes cost marks in HCF by division?
Dividing the smaller number by the larger at the start. Always put the larger number inside the division.
Writing the quotient instead of the last divisor as the answer.
Swapping the wrong pair: the new dividend is the old divisor, not the old dividend.
Stopping after two numbers when the question has three.
If you keep landing on wrong answers and cannot see which step is off, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer, so you can compare your lines with each step.
Where does this method show up next?
The same HCF is what you need to reduce fractions to their simplest form using HCF, and it is half of the decision in when to use HCF or LCM in word problems. For the history and the proof of why the method always ends, read Euclid's division algorithm: finding the HCF since 300 BC.
Try it now on 60, 84 and 132, run the rebuild check on each line, and confirm your answer by dividing all three numbers by it.
