Question

Find the hcf of 27664 and 66456 by eucilids division algorithm​

Answer 1

Answer:

HCF of 726 & 275

726=275×2+176

275=176×1+99

176=99×1+77

99=77×1+22

77=22×3+11

22=11×2+0

∴ HCF of 726 & 275 is 11

Answer 2

Answer:

The HCF of 27664 and 66456 = 104

Step-by-step explanation:

Recall the concept:

Euclid's division lemma

If 'a' and 'b' are any two positive integers, there exist two unique integers q and r such that

a = bq + r where 0 ≤ r < b.

To get the HCF of two numbers 'a' and 'b', we should continuously apply Euclid's division lemma until we get a remainder '0'. The HCF is given by the last non-zero remainder.

Applying division lemma with a = 66456 and b = 27664 we get

66456 = 27664 × 2 + 11128

Applying division lemma with a = 27664 and b = 11128 we get

27664 = 11128 × 2 + 5408

Applying division lemma with a = 11128 and b = 5408 we get

11128 = 5408  × 2 + 312

Applying division lemma with a = 5408 and b = 312 we get

5408 = 312  × 17 + 104

Applying division lemma with a = 312 and b = 104 we get

312 = 104 ×3 + 0

The last non-zero remainder = 104

Hence the HCF of 27664 and 66456 = 104

#SPJ2