Question

According to Euclid’s division algorithm, HCF of any two positive integers a and b with a > b is obtained by applying Euclid’s division lemma to a and b to find q and r such that a = bq + r, where r must satisfy
(a) 1 < r < b
(b) 0 < r < b
(c) 0 $ \le $ r < b
(d) 0 < r $ \le $ b

Answer 1

Hint: First of all, we need to define the Euclid’s division lemma with all its conditions. Then, to get a better understanding of the conditions, we will see some examples and then choose the correct condition from the given options.

Complete step-by-step answer:
Euclid’s Division Lemma is a way to define the relationship between two non-prime numbers a and b. It states that if a and b are two integers, a = bq + r holds true, where q and r are two unique integers.
Euclid’s division lemma can be used to find HCF of any two numbers.
We will see an example to find an HCF and see which of the given options holds true for a = bq + r.
First of all, let us try to find HCF of 32 and 12 using Euclid’s division lemma.
Now, using the lemma, we can say that 32 = 12(2) + 8
Now, the HCF of 32 and 12 will be the same as HCF of b and r, that is 12 and 8.
Now, using the lemma, we can say that 12 = 8(1) + 4
Now, HCF of 8 and 4, will be the same as HCF of 12 and 8 and thus HCF of 32 and 12.
Now, using the lemma, we can say that 8 = (4)2 + 0.
Since, now the r is 0, the HCF will be equal to b.
Therefore, the HCF of 32 and 12 is 4. It is also HCF of 8 and 12 and 8 and 4.
As we can see, the value of r is always less than b and r can also be equal to 0.
Thus, 0 $ \le $ r < b.
Hence, option (c) is the correct option.

Note: Euclid’s division lemma holds true unit a is prime. If a is a prime number, it can only be divided itself, so, b = a, q = 1 and r = 0. It is a very effective way to find HCF if the candidate doesn’t want to use the factorisation method.