Question

find the HCF of 496 and 21 24 by euclid 's division algorithm​

Answer 1

SOLUTION :

Euclid's Division Lemma

If 'a' and 'b' are two positive integers (a > b) their exist unique integers q and r such that a = bq + r , when 0 ≤ r < b

q = quotient

a = dividend

r = remainder

Algorithm ⇒ It is series of well defined steps which gives a procedure for solving a type of problem.

Lemma ⇒ It is proven statement used for another statement.

Now,

Answer

HCF of 496 and 2124

Here let a = 2124 and b = 496

so,

a = bq + r

2124 = 496 × 4 + 140

now, r ≠ 0

we take a = 496 and b = 140

496 = 140 × 3 + 76

now, r ≠ 0

we take a = 140 and b = 76

140 = 76 × 1 + 64

now, r ≠ 0

we take a = 76 and b = 64

76 = 64 × 1 + 12

now, r ≠ 0

we take a = 64 and b = 12

64 = 12 × 5 + 4

now, r ≠ 0

we take a = 12 and b = 4

12 = 4 × 3 + 0

now r = 0

Hence,

HCF (2124, 496) = 4