### 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.

He is a mathematics teacher who lived in Alexandria in Egypt.

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.