Theory:

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\) (divisor).
 
We can conclude from the above examples:
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\).
Euclid's division lemma
Given positive integers \(a\) and \(b\), there exist unique integers \(q\) and \(r\) satisfying \(a = bq + r, 0 ≤ r < b\).
Here, \(a\) and \(b\) are positive integers, \(q\) is a quotient, and \(r\) is a remainder.
 
Thus, 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!
An algorithm is a set of well-defined steps that describe how to solve a specific problem.
 
A lemma is a proven statement that is used to prove another.
Euclid's division algorithm
Euclid's division algorithm is based on the Euclid's division lemma. This algorithm is used to find the HCF of two positive numbers, say \(c\) and \(d\), \(c > d\).
 
Algorithm to find the HCF of two numbers:
Consider two positive numbers, \(c\) and \(d\), \(c > d\).
 
Step 1: Apply Euclid’s division lemma to \(c\) and \(d\). So, we find whole numbers, \(q\) and \(r\) such that, \(c = dq + r\), \(0 ≤ r < d\).
 
Step 2: If \(r = 0\), \(d\) is the HCF of \(c\) and \(d\). If \(r ≠ 0\), apply the division lemma to \(d\) and \(r\) to obtain another set of quotient and remainder.
 
Step 3: Repeat the procedure until the remainder is zero. The divisor at this stage will be the required HCF of given numbers.
Example:
Use Euclid’s algorithm to find the HCF of \(1524\) and \(236\).
 
Step 1: Since \(1524 > 236\), apply Euclid's division lemma to \(1524\) and \(236\).
 
\(1524 = 236 \times 6 + 108\)
 
Step 2: Since the remainder \(108 \ne 0\), apply the division lemma to \(236\) and the remainder \(108\).
 
\(236 = 108 \times 2 + 20\)
 
Step 3: Since the remainder \(20 \ne 0\), apply the division lemma to the new divisor \(108\) and the new remainder \(20\).
 
\(108 = 20 \times 5 + 8\)
 
Since the remainder \(8 \ne 0\), apply the division lemma to new divisor \(20\) and the new remainder \(8\).
 
\(20 = 8 \times 2 + 4\)
 
Since the remainder \(4 \ne 0\), apply the division lemma to new divisor \(8\) and the new remainder \(4\).
 
\(8 = 4 \times 2 + 0\)
 
Now, the remainder has become zero, so stop the procedure.
 
The divisor at this stage is \(4\).
 
Therefore, the HCF of \((1524, 236)\) is \(4\).
 
Also, note that:
 
HCF \((8, 4)\) \(=\) HCF \((20, 8)\) \(=\) HCF \((108, 20)\) \(=\) HCF \((236, 108)\) \(=\) HCF \((1524, 236) = 4\).
Important!
Although Euclid’s Division Algorithm is stated for only positive integers, it can be extended for all integers except zero, that is, \(b \ne 0\).