Theorem 1.1 (Euclid’s Division Lemma) : Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, 0 ≤ r < b.
Euclid’s division algorithm is a technique to compute the Greatest Common Divisor or 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.
We 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 ≤ 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.
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.
Refer Real Numbers for related problems.