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.