Euclid’s Division Lemma
Given positive integers a and b there exist unique integers q and r which satisfies the equation a= bq+r, 0 ≤ r < b.
Euclid’s division algorithm is based on this lemma
An algorithm is a procedure which has a series of well defined steps for solving a given problem
Euclid’s division algorithm is a method used to find out the Highest Common Factor (HCF) of two given positive integers.
Recall that the HCF of two given positive integers a and b is the largest integer d which divides both a and b.
Now let us take an example to check how this algorithm works.
Find the HCF of the integers 455 and 42
we will apply the Euclid’s Division Algorithm to compute the HCF
Initially we need to consider the larger integer, in this problem the larger integer is 455.
Then we use the Euclid’s Lemma to obtain
Now consider the divisor 42 and the remainder 35, and apply the lemma again to obtain
Now consider the divisor 35 and the remainder 7, and apply the lemma again to obtain
Here we see that the remainder becomes zero and so we need not proceed further.
We conclude that the HCF of 422 and 45 is 7.
We can verify this by listing out the factors of 455 and 42 and we see that the HCF of the given numbers to be 7.
Euclid’s Division Algorithm:
To obtain the HCF of two positive integers say a and b, where a > b, follow the steps given below
Step 1: Apply the Euclid’s division lemma to the integers a and b. So we find the whole numbers c and d such that a= bc+d, 0 ≤ d <b.
Step 2: If d=0, d is the HCF of the given integers. If d 0, we need apply the division lemma to b and d.
Step 3: Continue the same procedure till the remainder becomes zero. The divisor at this stage is the required HCF.
Note: This algorithm works because HCF ( a,b) = HCF (c,d) where the symbol HCF(a,b) denotes the HCF of a and b.
Use Euclid’s Algorithm to find the HCF of 867 and 255
Step 1: Here we see that 867> 255, So we apply the division lemma to 865 and 255 to obtain
Step 2: Now the remainder 2550, we again apply the division lemma to the integers 255 and 102 to obtain
Step 3: Now we consider the new divisor 102 and the remainder 51, and again apply the division lemma
We see that the remainder is zero now, so we stop at this stage. Since the divisor at this stage is 51, we conclude by saying that the HCF of 867 and 255 is 51.
Note that 51= HCF ( 102,51)= HCF (255,102) = HCF ( 867,255).
NOTE: Euclid’s division algorithm is not only useful for computing the HCF of large numbers but it is one of the oldest algorithm that the computer had been programmed to carry out.