Question 1. Use Euclid’s Division Algorithm to find the HCF of:
(i) 135 and 225
(ii) 196 and 38220
(iii) 867 and 255
Solution:
(i) 135 and 225
Step 1: Apply the Division Algorithm
Divide 225 by 135:
$$225 = 135 \times 1 + 90$$
Here, 225 divided by 135 gives a quotient of 1 and a remainder of 90.
Step 2: Replace and Repeat
Now, replace 225 with 135 and 135 with 90, then repeat the division process:
Divide 135 by 90:
$$135 = 90 \times 1 + 45$$
Here, 135 divided by 90 gives a quotient of 1 and a remainder of 45.
Step 3: Replace and Repeat Again
Now, replace 135 with 90 and 90 with 45, then repeat the division process:
Divide 90 by 45:
$$90 = 45 \times 2 + 0$$
Here, 90 divided by 45 gives a quotient of 2 and a remainder of 0. Since the remainder is now 0, the divisor at this step, which is 45, is the HCF of 135 and 225. Therefore, the HCF of 135 and 225 is 45.
(ii) 196 and 38220
Step 1: Apply the Division Algorithm
Divide 38220 by 196:
$$38220 = 196 \times 195 + 0$$
Here, 38220 divided by 196 gives a quotient of 195 and a remainder of 0.
Since the remainder is now 0, the divisor at this step, which is 196, is the HCF of 196 and 38220. Therefore, the HCF of 196 and 38220 is 196.
(iii) 867 and 255
Step 1: Apply the Division Algorithm
Divide 867 by 255:
$$867 = 255 \times 3 + 102$$
Here, 867 divided by 255 gives a quotient of 3 and a remainder of 102.
Step 2: Replace and Repeat
Now, replace 867 with 255 and 255 with 102, then repeat the division process:
Divide 255 by 102:
$$255 = 102 \times 2 + 51$$
Here, 255 divided by 102 gives a quotient of 2 and a remainder of 51.
Step 3: Replace and Repeat Again
Now, replace 255 with 102 and 102 with 51, then repeat the division process:
Divide 102 by 51:
$$102 = 51 \times 2 + 0$$
Here, 102 divided by 51 gives a quotient of 2 and a remainder of 0. Since the remainder is now 0, the divisor at this step, which is 51, is the HCF of 867 and 255. Therefore, the HCF of 867 and 255 is 51.