Theory:

Euclid
The development of geometry by the Greek mathematician Euclid is called Euclid's geometry.
 
He is a mathematics teacher who lived in Alexandria in Egypt.
 
euclidРесурс1png.png
 
Euclid collected and arranged the concepts of geometry, which is used in olden days and wrote the book "Elements". He divided the ideas into \(13\) chapters and made it as a \(13\) books.
 
Important!
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 the above three pairs 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.
 
Important!
1. The remainder is always lesser 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\).
 
Important!
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.