Euclid's division algorithm for HCF

Euclid's algorithm finds the highest common factor of two numbers by repeated division, with no need to factorise them. It was written down by the Greek mathematician Euclid about 300 BCE and is still the fastest method by hand for large numbers. For many years it was part of the class 10 chapter on real numbers, and it remains the "long division method" for HCF taught from class 6.

Euclid's division lemma

The method rests on one plain fact. For any two positive whole numbers a and b, there is exactly one pair of whole numbers q and r with

a = b × q + r, where r is 0 or more and less than b.

This is just division written out: q is the quotient and r the remainder. For 47 and 5: 47 = 5 × 9 + 2.

The algorithm

1. Divide the larger number by the smaller and note the remainder.
2. If the remainder is 0, the divisor is the HCF.
3. If not, divide the divisor by the remainder.
4. Repeat until the remainder is 0. The last divisor is the HCF.

Worked example: HCF of 455 and 42

• 455 = 42 × 10 + 35
• 42 = 35 × 1 + 7
• 35 = 7 × 5 + 0

The remainder is now 0 and the last divisor is 7. So HCF(455, 42) = 7.

A longer example: HCF of 4052 and 12576

• 12576 = 4052 × 3 + 420
• 4052 = 420 × 9 + 272
• 420 = 272 × 1 + 148
• 272 = 148 × 1 + 124
• 148 = 124 × 1 + 24
• 124 = 24 × 5 + 4
• 24 = 4 × 6 + 0

HCF(4052, 12576) = 4. Factorising these two numbers would have taken far longer.

Why it works

Look at the first line of the first example: 455 = 42 × 10 + 35. Any number that divides both 455 and 42 must also divide 35, because 35 is 455 minus ten 42s. And any number that divides both 42 and 35 must divide 455. So the pair (455, 42) has exactly the same common factors as the pair (42, 35). Each step swaps the pair for a smaller pair with the same common factors, until one number divides the other.

The remainders get smaller at every step and cannot go below 0, so the method always ends.

Three numbers

Find the HCF of two of them, then the HCF of that result with the third. For 455, 42 and 49: HCF(455, 42) = 7, and HCF(7, 49) = 7.

From HCF to LCM

Once the HCF of two numbers is known, the LCM follows: LCM = product ÷ HCF. For 455 and 42 the LCM is 455 × 42 ÷ 7 = 2730.

Typical exam uses

• Largest number dividing with given remainders. Subtract the remainders first, then apply the algorithm.
• Showing a property of numbers. By the lemma with b = 2, every whole number is 2q or 2q + 1: even or odd. With b = 3, every number is 3q, 3q + 1 or 3q + 2.
• Simplifying a large fraction. Divide top and bottom by the HCF found this way.

The HCF and LCM calculator writes out the division steps for any numbers you enter. Syllabuses change from year to year, so check your own board's current syllabus for what is examined.

More