2. Euclid’s Division Lemma

The development of geometry by the Greek mathematician Euclid is called Euclid's geometry.
 
He was a mathematics teacher who lived in Alexandria, Egypt.

 

 

Euclid collected and arranged the concepts of geometry that were used in the olden days and wrote the book "Elements". He divided the ideas into \(13\) chapters and made them into \(13\) books.

 

Consider the following pairs of integers \((a, b)\) to get an idea of what Euclid's division lemma is all about.

 

(i) \(25, 4\)   (ii) \(6, 11\)   (iii) \(15, 3\)

 

Now, write the first number using the second number in each pair.

 

(i) \(25 = 4 \times 6 + 1\) [Here, \(6\) is a quotient and \(1\) is a remainder.]

 

(ii) \(6 = 11 \times 0 + 6\) [Here, \(0\) is a quotient and \(6\) is a remainder.]

 

(iii) \(15 = 3 \times 5 + 0\) [Here, \(3\) is a quotient and \(0\) is a remainder.]

 

Note that, in each of the above three pairs, the remainder is smaller than the positive integer \(b\).

 

We can conclude from the above example:

We can also write this relation as:

 

 

Now, let's see Euclid's division algorithm, which is based on Euclid's division lemma.

 

If \(a\) and \(b\) are any two integers, then there exist unique integers \(q\) and \(r\) such that \(a = bq + r\), where \(0 \le r < b\).