Real numbers-Euclid’s Division Lemma

Theorem 1.1 (Euclid’s Division Lemma) : Given positive integers a and b, there exist unique integers q and r satisfying a = bq +r, 0£ r

This result was perhaps known for a long time , but was first recorded in Book VII of Euclid’s Elements division algorithem is based on this lemma.

Euclid’s division algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers .Recall that the HCF of two positive integers a and b is the largest positive integer d that divides both a and b.

Let us see how the algorithm works, through an example first. Supposewe need to find the HCF of the integers 455 and 42. We start with the larger integer, that is, 455. Then we use Euclid’s lemma to get

455 = 42 x 10 + 35

Now consider the divisor 42 and the remainder 35, and apply the division lemma to get

42 = 35 x 1 +7

Now consider the divisor 35 and the remainder 7, and apply the division lemma to get

35 = 7 x5 + 0

Notice that the remainder has become zero, and we cannot proceed any further . We claim that the HCF of 455 and 42 is the divisor at this stage i.e, 7. You can easily verify this by listing all the factors of 455 and 42. Why does this method work ? It works because of the following result.