Euclid’s Division Algorithm
Euclid’s division algorithm is based on Euclid’s division lemma. Euclid’s division algorithm is a technique to compute the Highest Common Factor
(HCF) of two given positive integers.
To obtain the HCF of two positive integers, say a and b, with a > b, follow the steps below:
Step 1: Apply Euclid’s division lemma to a and b. So, we find whole numbers q and r such that, a = bq + r,
Step 2: If r = 0, then b is the HCF of a and b and if , apply the division lemma to b and r.
Step 3: Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.
Examples:
Example. : Use Euclid’s algorithm to find the HCF of 81 and 135.
Solution:
Step 1: Since 135 > 81, we apply the division lemma to 81 and 135,
135 = 81 × 1 + 54
Step 2: Since the remainder , we apply the division lemma to 54 and 81,
81 = 54 × 1 + 27
Step 3: Since the remainder , we apply the division lemma to 27 and 54,
54 = 27 × 2 + 0
The remainder has now become zero, so our procedure stops. Since the divisor at this stage is 27; the HCF of 81 and 135 is 27.
Note that 27 = HCF (27, 54) = HCF (54, 81) = HCF (81, 135)
