Question

examples for euclid's division algorithm and euclid's division lemma

Answer 1

ANSWER :

Euclid's decision lemma:

Euclid's decision lemma states that

In given Positive integer and b, there exist whole number q and r satisfying

a = bq+ r

where 0 < r < b

Euclid's decision algorithm:

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

step one :

Apply the division lemma to find q and r

where a = bq + r , 0 < r < b

step two:

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

step three:

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

That's all .hope you understand.....