Maths Real Numbers

Euclid’s Division Lemma

Written by Mary Christina

Euclid’s Division Lemma

Given positive integers a and b there exist unique integers q and r which satisfies the equation a= bq+r, 0 ≤ r < b.

Euclid’s division algorithm is based on this lemma



An algorithm is a procedure which has a series of well defined steps for solving a given problem

Euclid’s division algorithm is a method used to find out the Highest Common Factor (HCF) of two given positive integers.

Recall that the HCF of two given positive integers a and b is the largest integer d which divides both a and b.

Now let us take an example to check how this algorithm works.



Find the HCF of the integers 455 and 42



we will apply the Euclid’s Division Algorithm to compute the HCF

Initially we need to consider the larger integer, in this problem the larger integer is 455.

Then we use the Euclid’s Lemma to obtain

455= 42*10+35

Now consider the divisor 42 and the remainder 35, and apply the lemma again to obtain

 42= 35*1+7

Now consider the divisor 35 and the remainder 7, and apply the lemma again to obtain


Here we see that the remainder becomes zero and so we need not proceed further.

We conclude that the HCF of 422 and 45 is 7.

We can verify this by listing out the factors of 455 and 42 and we see that the HCF of the given numbers to be 7.


Euclid’s Division Algorithm:

To obtain the HCF of two positive integers say a and b, where a > b, follow the steps given below

Step 1: Apply the Euclid’s division lemma to the integers a and b. So we find the whole numbers c and d such that a= bc+d, 0 ≤ d <b.

Step 2: If d=0, d is the HCF of the given integers. If d 0, we need apply the division lemma to b and d.

Step 3: Continue the same procedure till the remainder becomes zero. The divisor at this stage is the required HCF.

Note: This algorithm works because HCF ( a,b) = HCF (c,d) where the symbol HCF(a,b) denotes the HCF of a and b.



Use Euclid’s Algorithm to find the HCF of 867 and 255



Step 1: Here we see that 867> 255, So we apply the division lemma  to 865 and 255 to obtain

 867= 255*3+102

 Step 2: Now the remainder 2550, we again apply the division lemma to the integers 255 and 102 to obtain

 255= 102*2+51

 Step 3: Now we consider the new divisor 102 and the remainder 51, and again apply the division lemma


We see that the remainder is zero now, so we stop at this stage. Since the divisor at this stage is 51, we conclude by saying that the HCF of 867 and 255 is 51.

Note that 51= HCF ( 102,51)= HCF (255,102) = HCF ( 867,255).


NOTE: Euclid’s division algorithm is not only useful for computing the HCF of  large numbers but it is one of the oldest algorithm that the computer had been programmed to carry out.

About the author

Mary Christina

Mary Christina from Chennai, India. She has completed Master Degree in Mathematics and she loves to teach and share about her knowledge in maths for High School and College Students...