Question

Explain Euclids division lemma

Answer 1

Euclids division lemma , states that for any two positive integers a and b,we can find whole numbers

q and r such that a=bq+r , where r is greater than or equal to 0 but less than b.It can be used to find

the highest common factor of any two positive integers.

Let a>b.If r=o then b is the highest common factor of a and b and if r is not equal to zero find apply

euclids divison lemma to find new divisor b and remainder r.Continue the process untill the remainder

becomes zero.In that case the value of the divisor b is the highest common factor of a and b.