Question

how can solve the eulids lemma

Answer 1

Euclid's division lemma:-

Given positive integers a and b,there exist unique pair of integers q and r satisfying a=bq+r , 0 ≤ r < b

Euclid's division algorithm is based on this lemma. Let us apply Euclid division lemma.

Euclid's division algorithm is a technique to compute the highest common factor (HCF) of two given numbers. Recall that the HCF of two positive integers a and b is the greatest positive integer d that divides both a and b.

Suppose you have to find the HCF of 60 and 100.

Let us solve it:-

Let us link this process to Euclid's lemma to get HCF of 60 and 100.

100 = 60 × 1 + 40

When 100 is divided by 60,the remainder is 40,

Now consider the division of 60 with the remainder 40 in the above and apply the division lemma to get

60 = 40 × 1 + 20

As remainder is 20,now consider the division of 40 with the remainder 20, and apply the division lemma to get

40 = 20 × 2 + 0

Now,the remainder is zero and we cannot proceed any further. We claim that the HCF of 60 and 100 is the divisor at this stage i.e.,20.

So HCF (60,100) = 20

Thus,we find the HCF by applying Euclid division lemma.

Hope you understand……