Question : Use Euclid’s division algorithm to find the H.C.F of :
(i) 135 and 225
(ii) 196 and 38220
(iii) 865 and 225
Solution :
(i) We start with the larger number 225.
By Euclid’s Division Algorithm, we have
225 = 135 \(\times\) 1 + 90
We apply Euclid’s Division Algorithm on
Division 135 and the remainder 90.
135 = 90 \(\times\) 1 + 45
Again we apply Euclid’s Division Algorithm on Divisor 90 and remainder 45
90 = 45 \(\times\) 2 + 0
H.C.F(225, 90) = 45
So, H.C.F. of 225 and 135 is 45.
(ii) We have :
Division = 38200 and Divisor 196
38220 = 196 \(\times\) 195 + 0
Hence, H.C.F. (196, 38220) = 196
(iii) By Euclid’s Division Algorithm, we have
867 = 255 \(\times\) 3 + 102
We apply Euclid’s Division Algorithm on the
Divisor 255 and the remainder 102.
255 = 102 \(\times\) 2 + 51
Again we apply Euclid’s Division Algorithm on the divisor 102 and the remainder 51.
102 = 51 \(\times\) 2 + 0
H.C.F (867, 255) = H.C.F(255, 102) = H.C.F(102, 51) = 51.
