Using Euclid’s division algorithm, find the HCF of

i. 405 and 2520


ii. 504 and 1188


iii. 960 and 1575

i. 45

here 405 < 2520,


b = 405 and a = 2520.


By Euclid’s division lemma -


a = bq + r ….(1)


where q is the quotient, r is the remainder and b is the divisor.


Putting it in equation (1) -


2520 = 405(6) + 90.


Here 90 is the remainder, which is not zero. Again applying the Euclid’s divison lemma -


Now, a = 405; b = 90;


405 = 90(4) + 45.


Here 45 is the remainder, which is not zero. Again applying the Euclid’s divison lemma -


a = 90; b = 45;


90 = 45(2) + 0.


remainder is zero.


HCF is 45.


ii. 36


here 504 < 1188,


b = 504 and a = 1188.


By Euclid’s division lemma -


a = bq + r ….(1)


where q is the quotient, r is the remainder and b is the divisor.


Putting the values in equation (1) -


1188 = 504(2) + 180.


Here 180 is the remainder, which is not zero. Again applying the Euclid’s divison lemma -


Now, a = 504; b = 180;


504 = 180(2) + 144


Here 144 is the remainder, which is not zero. Again applying the Euclid’s divison lemma -


Now,a = 180; b = 144;


180 = 144(1) + 36.


Here 36 is the remainder, which is not zero. Again applying the Euclid’s divison lemma -


Now,a = 144; b = 36;


144 = 36(4) + 0.


remainder is zero.


HCF is 36.


iii. 15


here 960 < 1575,


b = 960 and a = 1575.


a = bq + r ….(1)


where q is the quotient, r is the remainder and b is the divisor.


Putting the values in equation (1) -


1575 = 960(1) + 615.


Here 615 is the remainder, which is not zero. Again applying the Euclid’s divison lemma -


Now, a = 960; b = 615;


960 = 615(1) + 345.


Here 345 is the remainder, which is not zero. Again applying the Euclid’s divison lemma -


Now, a = 615; b = 345;


615 = 345(1) + 270.


Here 270 is the remainder, which is not zero. Again applying the Euclid’s divison lemma -


Now, a = 345; b = 270;


345 = 270(1) + 75.


Here 75 is the remainder, which is not zero. Again applying the Euclid’s divison lemma -


Now, a = 270; b = 75;


270 = 75(3) + 45.


Here 45 is the remainder, which is not zero. Again applying the Euclid’s divison lemma -


Now, a = 75; b = 45;


75 = 45(1) + 30.


Here 30 is the remainder, which is not zero. Again applying the Euclid’s divison lemma -


Now, a = 45; b = 30;


45 = 30(1) + 15.


Here 15 is the remainder, which is not zero. Again applying the Euclid’s divison lemma -


a = 30; b = 15;


30 = 15(2) + 0.


remainder is zero.


HCF is 15.


4