Euclid's Division Lemma
Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, 0≤r
This result was perhaps known for a long time, but was first recorded in Book VII of Euclid’s Elements. Euclid’s division algorithm is based on this lemma.
Euclid’s division algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers. Recall that the HCF of two positive integers a and b is the largest positive integer d that divides both a and b.
Let us see how the algorithm works, through an example first. Suppose we need to find the HCF of the integers 455 and 42.

We start with the larger integer, that is, 455.
Then we use Euclid’s lemma to get 455 = 42 × 10 + 35.
Now consider the divisor 42 and the remainder 35, and apply the division lemma to get 42 = 35 × 1 + 7.
Now consider the divisor 35 and the remainder 7, and apply the division lemma to get 35 = 7 × 5 + 0.

Notice that the remainder has become zero, and we cannot proceed any further. We claim that the HCF of 455 and 42 is the divisor at this stage, i.e., 7. You can easily verify this by listing all the factors of 455 and 42.Why does this method work? It works because of the following result. So, let us state Euclid’s division algorithm clearly.To obtain the HCF of two positive integers, say c and d, with c > d, follow the steps below:

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 ≤rStep 2 : If r = 0, d is the HCF of c and d. If r ≠ 0, apply the division lemma to d and r.
Step 3 : Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.

This algorithm works because HCF (c, d) = HCF (d, r) where the symbol HCF (c, d) denotes the HCF of c and d, etc.Euclid’s division algorithm is not only useful for calculating the HCF of very large numbers, but also because it is one of the earliest examples of an algorithm that a computer had been programmed to carry out.

Remarks :
1. Euclid’s division lemma and algorithm are so closely interlinked that people often call former as the division algorithm also.
2. Although Euclid’s Division Algorithm is stated for only positive integers, it can be extended for all integers except zero, i.e., b ≠ 0.