Question

1. What do you mean by Euclid's division algorithm or Euclid's division Lemma theorem ? Explain with example.​

Answer 1

Answer:

According to Euclid’s Division Lemma if we have two positive integers a and b, then there exist unique integers q and r which satisfies the condition a = bq + r where 0 ≤ r < b.

The basis of the Euclidean division algorithm is Euclid’s division lemma. To calculate the Highest Common Factor (HCF) of two positive integers a and b we use Euclid’s division algorithm. HCF is the largest number which exactly divides two or more positive integers. That means, on dividing both the integers a and b the remainder is zero.

Example-

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

980 = 78 × 12 + 44

Now, here a = 980, b = 78, q = 12 and r = 44.

Now consider the divisor 78 and the remainder 44, apply Euclid division lemma again.

78 = 44 × 1 + 34

Similarly, consider the divisor 44 and the remainder 34, apply Euclid division lemma to 44 and 34.

44 = 34 × 1 + 10

Following the same procedure again,

34 = 10 × 3 + 4

10 = 4 × 2 + 2

4 = 2 × 2 + 0

As we see that the remainder has become zero, therefore, proceeding further is not possible. Hence, the HCF is the divisor b left in the last step. We can conclude that the HCF of 980 and 78 is 2.