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)