State Euclid’s Division Lemma.

First of all, let us understand the basis of Euclid’s division lemma.

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.

Highest Common Factor (HCF) as the name suggests, is the largest number which exactly divides two or more positive integers.

Statement: According to Euclid’s Division Lemma, if a and b are any two positive integers then there exist two unique whole numbers q and r such that

a = b q + r,

where 0 ≤ r < b

Here, a is called the dividend,

b is called the divisor,

q is called the quotient and

r is called the remainder.