## Introduction to Euclid’s Division Lemma

If we have two positive integers, *a* and *b*, then there are unique integers, *q* and *r*, which satisfy the formula **a = bq + r**, where **0 ≤ r < b**, according to Euclid's Division Lemma.

**Dividend = Divisor × Quotient + Remainder**

## What is Euclid’s Division Algorithm?

Euclid’s Division Algorithm is the process of applying Euclid’s Division Lemma in succession several times to obtain the HCF of any two numbers.

Let’s take an example to see the steps. We need to get the HCF of the following two numbers: 100 and 1080.

To do this, we first choose the highest integer, or 1080, and then use Euclid’s Division Lemma to write 1080 in the form of *a = bq + r*, where **0 ≤ r < b**;

1080 = 100 x 10 + 80

Note that, here *a = 1080*, *b = 100*, *q = 10* and *r = 80*

Apply Euclid’s division lemma again by taking the divisor 100 and the remainder 80.

100 = 80 x 1 + 20

Apply Euclid’s division lemma to 80 and 20 using the same process once again

80 = 20 x 4 + 0

It is evident that the remainder has decreased to zero, hence there is no way to continue. As a result, the divisor ‘*b*’ left in the final step is the HCF. Thus, we can say that 1080 and 100 have an HCF of 20.

## Points to be Noted

- Euclid’s division lemma says that for two positive integers
*a*and*b*, there exists unique integers*q*and*r*such that**a = bq + r**,**0 ≤ r < b** - Euclid’s Division Algorithm is the process of applying Euclid’s Division Lemma in succession several times to obtain the HCF of any two numbers.
- Euclid's Division Algorithm works because if
**a = bq + r**, then**HCF(a,b) = HCF(b,r)**.

## Generalising Euclid’s Division Algorithm

Now let's generalise Euclid’s Division Algorithm. Assuming that we must determine the HCF of any two arbitrary numbers, *a* and *b*, let's move on.

We keep applying Euclid's Division Lemma until we get a remainder of zero:

A = b(q1) + r1

b = r1(q2) + r2

r1 = r2(q3) + r3

...

rn−2 = rn−1(qn) + rn

rn−1 = rn(qn+1) + 0

The residual in the second-to-last step, **HCF(a,b)= rn**, is the HCF. We strongly advise you to use the same line of reasoning as above to demonstrate this. Demonstrate first that *rn* is in fact a common factor between *a* and *b*. Then, demonstrate that any factor that *a* and *b* have in common must also be a factor of *rn*, indicating that *rn* is the greatest common factor.

It's likely that you didn't fully comprehend Euclid's Division Algorithm's reasoning, and you could be tempted to bypass it and continue. But take note—understanding this logic is not only crucial for further explanations, but it's also an excellent mental exercise. Therefore, until you have a firm understanding of the previous topic, do not proceed.

## Shortcut Method for Euclid’s Division Algorithm

Are the above steps unclear to you? Remain calm. This is a quick and easy way. Do you still recall how you used the long division method you learnt in lower levels to find the HCF? To write the steps of Euclid's division algorithm, we shall employ the same technique. This shortcut (computing HCF of 1080 and 100) is for the same example as earlier. The following formula, which we studied in the lower classes, is applied here.

**Dividend = Divisor × Quotient + Remainder**

The HCF in this method is the divisor of the final step that results in the remainder zero. Thus, **HCF(1080,100) = 20** is implied.

## Conclusion

Euclid’s Division Lemma or Euclid division algorithm states that Given positive integers *a* and *b*, there exist unique integers *q* and *r* satisfying **a = bq + r**, **0 ≤ r < b**.

The algorithm can be used to find the HCF of two given numbers. The steps shown below can be used to find the HCF of two positive integers, *c* and *d*, where *c > d*:

- Apply to
*c*and*d*Euclid's division lemma. So, we find whole numbers,*q*and*r*such that**c = dq + r**,**0 ≤ r < d**. - The HCF of
*c*and*d*is*d*if*r = 0*. Apply the division lemma to*d*and*r*if*r ≠ 0*. - Keep doing the previous actions until the remaining equals zero. At this point, the necessary HCF will serve as the divisor.