Use Euclid’s division algorithm to find the H.C.F of :

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.