Question

Find HCF :-(use euclid's division algorithm)​

Answer 1

Answer:

$\huge{ \underline{ \underline{ \mathtt{Euclid's \: \: \: division \: \: \: algorithm}}}}$

$\bf\green{Difination:}$

Euclid's division algorithm, as the name suggest, has to do with divisibility of integers. Such simply, it says any positive integer a can be divided by any positive integer b in such a way that it leaves a remainder r that is smaller than b .

$\bf\green{Example:-}$

Q. Use Euclid's division algorithm to find the HCF of 4052 and 12576.

Solution:-

step 1 : Since 12576 ＞4052, we apply the division lemma to 12576 and 4052, to get 12576 = 4052 × 3 + 520

step 2 : Since the remainder 420 ≠ 0, we apply the division lemma to 4052 and 420, to get 4052 = 420 × 9 + 272

step 3 : We consider the new divisor 420 and the new remainder 272, and apply the division lemma to get

420 = 272 × 1 + 148

( like this we will consider all )

step 4 : 272 = 148 × 1 + 124

step 5 : 148 = 124 × 1 + 24

step 6 : 124 = 24 × 5 + 4

step 7 : 24 = 4 × 6 + 0

Therefore, HCF of 4052 and 12576 is 4

Answer 2

Answer:

Euclid's division algorithm is based on Euclid's division lemma. According to this, the HCF of any two positive integers a and b, with a > b, is obtained as follows :

Apply the division lemma to find q and r where a = bq + r,

$0 \leqslant r < b$

If r = 0 , the HCF is b, if r ≠ 0 , apply Euclid's lemma to b and r.

Continue the process till the remainder is 0.The divisor at this stage will be HCF (a, b).

Also HCF ( a, b) = HCF ( b, r)