Euclid's Division Lemma

Euclid’s Division Lemma

It states that for a given positive integers For given positive integers ‘a’ and ‘b’, there exist unique whole numbers ‘q’ and ‘r’ which satisfy the following relation:

a=bq+r, 0≤r≤b.

Euclid’s Division Algorithms:

HCF of any two positive integers a and b, with a>b is as follows:

Step 1: Applying Euclid’s Division Lemma to a and b to find q and r such that

a=bq+r, 0≤r≤b.




Step 2: : If r = 0, HCF (a,b)=b if r≠0, apply Euclid’s lemma to b and r.

Step 3: Continue with this process till the remainder is zero. At this stage, the divisor is the required HCF.


Consider we have two numbers 39 and 490 and we need to find the HCF of both of these numbers. To do this, we choose the largest integer first, i.e. 490 and then according to Euclid Division Lemma, a = bq + r  where 0 ≤ r ≤ b;

490 = 39 × 12 + 22

Now, here a = 490, b = 39, q = 12 and r = 22.

Now consider the divisor as 39 and the remainder 22 and apply the Euclid division method again, we get

39 = 22 × 1 + 17

Similarly, consider the divisor as 22 and the remainder 17 and apply the Euclid division method again, we get

22 = 17 × 1 + 5

Following the same procedure again,

17 = 5 × 3 + 2




Now, we can see that the remainder is zero and further process is not possible, hence the HCF is the divisor left in the last step i.e. 1. We can say that the HCF of 490 and 39 is 1.

Hope you understood the concept of Euclid's Division Lemma. For more detailed CBSE Maths notes  visit-

Our Categories