Class X Mathematics Back to Main 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)