Procedure

HCF by Euclid's algorithm

Arithmetic • Number System • LCM and HCF

Statement

For positive integers

a

and

b

, write

a = b q + r

with

0 \leq r < b

. Every common divisor of

a

and

b

divides

r = a - b q

and every common divisor of

b

and

r

divides

a

, so

HCF (a, b) = HCF (b, r)

. Replacing

(a, b)

(b, r)

and repeating must stop, because the remainders strictly decrease; the last non-zero remainder is

HCF (a, b)

How to use it

1Divide the larger by the smaller, then divide the old divisor by the remainder, and keep going until the remainder is $0$ .
2Read off the last non-zero remainder: that is the HCF.
3Use it in preference to prime factorisation when the numbers are large or awkward to factorise, since it needs only short division.
4For three or more numbers, apply it to two, then to that HCF and the next number.

Worked example

Find the HCF of

252

and

105

Step-by-step

1
$252 = 2 \times 105 + 42$
Why: Divide the larger by the smaller and keep the remainder $42$ .
2
$105 = 2 \times 42 + 21$
Why: The old divisor $105$ is now divided by the remainder $42$ .
3
$42 = 2 \times 21 + 0$
Why: The remainder is $0$ , so the process stops here.
4
$HCF (252, 105) = 21$
Why: The last non-zero remainder is the HCF.

Answer

21

Watch out

The answer is the last NON-ZERO remainder, not the final zero and not the last quotient. It applies to integers only, and to two at a time — running it on three numbers at once is not defined. It gives the HCF, never the LCM; obtain the LCM from it through

HCF \times LCM = ab

Builds on

Dividend

=

divisor

\times

quotient

+

remainder

Also known as

Euclidean algorithm, Euclid's division algorithm, HCF by repeated division, gcd by division, successive division method for HCF, last non-zero remainder

Appears in past papers

2020 (II)

Q44