Learn Mathematics through our AI based learning portal with the support of our Academic Experts!

Learn more
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.
Euclid is a Father of Geometry.
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:
Any positive integer \(a\) can be divided by another positive integer \(b\) in such a way that it leaves a remainder \(r\) that is smaller than \(b\).
Theorem 1: Euclid' division lemma
Let \(a\) and \(b\) \((a > b)\) be any two positive integers. Then, there exist unique integers \(q\) and \(r\) such that \(a = bq + r, 0 ≤ r < b\).
We can also write this relation as:
Dividend \(=\) Divisor \(\times\) Quotient \(+\) Remainder
Now, let's see Euclid's division algorithm, which is based on Euclid's division lemma.
1. The remainder is always less than the divisor.
2. If \(r = 0\), then \(a = bq\) so \(b\) divides \(a\).
3. If \(b\) divides \(a\), then \(a = bq\).
Generalised form of 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\).
A lemma is a proven statement that is used to prove another.
An algorithm is a set of well-defined steps that describe how to solve a specific problem.