(i) 135 and 225 (ii) 196 and 38220 (iii) 867 and 255
Solution: (i) 135 and 225
Step 1
Since 225 > 135, we can apply Euclid’s division lemma to a = 225 and b = 135 to find q and r such that:
225 = 135q + r, 0 ≤ r < 135
So, dividing by 135 we get 1 as the quotient and 90 as remainder.
i.e., 225 = 135 × 1 + 90
Step 2
Remainder r is 90 and is not equal to 0, we can apply Euclid’s division lemma to a = 135 and b = 90 to find q and r such that
135 = 90q + r, 0 ≤ r < 90
So, dividing by 90 we get 1 as the quotient and 45 as remainder.
i.e., 135 = 90 × 1 + 45
Step 3
Remainder r is 45 and is not equal to 0, we can apply Euclid’s division lemma to a = 90 and b = 45 to find q and r such that
90 = 45q + r, 0 ≤ r < 45
So, dividing by 45 we get 2 as the quotient and 0 as remainder.
i.e., 90 = 45 × 2 + 0
Step 4
Since the remainder is zero, the divisor at this stage will be HCF of (135, 225)
Since the divisor at this stage is 45, therefore, the HCF of 135 and 225 is 45.
(ii) 196 and 38220
Step 1
Since 38220 > 196, we can apply Euclid’s division lemma to a = 38220 and b = 196 to find q and r such that:
38220 = 196q + r, 0 ≤ r < 196
So, dividing by 196 we get 195 as the quotient and 0 as remainder.
i.e., 38220 = 196 × 195 + 0
Step 2
Since the remainder is zero, the divisor at this stage will be HCF of (38220, 196)
Since the divisor at this stage is 196, therefore, the HCF of 38220 and 196 is 196.
(iii) 867 and 255
Step 1
Since 867 > 255, we can apply Euclid’s division lemma to a = 867 and b = 255 to find q and r such that:
867 = 255q + r, 0 ≤ r < 255
So, dividing by 255 we get 3 as the quotient and 102 as remainder.
i.e., 867 = 255 × 3 + 102
Step 2
Remainder r is 102 and is not equal to 0, we can apply Euclid’s division lemma to a = 255 and b = 102 to find q and r such that
255 = 102q + r, 0 ≤ r < 102
So, dividing by 102 we get 2 as the quotient and 51 as remainder.
i.e., 255 =102 × 2 + 51
Step 3
Remainder r is 51 and is not equal to 0, we can apply Euclid’s division lemma to a = 102 and b = 51 to find q and r such that
102 = 51q + r, 0 ≤ r < 51
So, dividing by 51 we get 2 as the quotient and 0 as remainder.
i.e., 102 = 51 × 2 + 0
Step 4
Since the remainder is zero, the divisor at this stage will be HCF of (867, 225)
Since the divisor at this stage is 51, therefore, the HCF of 135 and 225 is 51.
Solution 2.
Solution 3.
[Hint: Let x be any positive integer then it is of the form 3q, 3q + 1 or 3q + 2. Now square each of these and show that they can be rewritten in the form 3m or 3m + 1.]
Solution 4
Solution 1