Question

Describe Euclid Division Lemma​

Answer 1

A Euclids division lemma is a proven statement which is used to prove other statements.

Euclids division lemma : Let ‘a’ and ‘b’ be any two positive integers. Then there exist unique integers ‘q’ and ‘r’ such that

a = bq + r, 0 ≤ r ≤ b.

If b | a, then r=0. Otherwise, ‘r’ satisfies the stronger inequality 0 ≤ r ≤ b.

The basis of the Euclidean division algorithm is Euclid’s division lemma. To calculate the Highest Common Factor (HCF) of two positive integers a and b we use Euclid’s division algorithm. HCF is the largest number which exactly divides two or more positive integers. By exactly we mean that on dividing both the integers a and b the remainder is zero.

Answer 2

Given positive integers a and b there exist unique integers q and r satisfying the equation