Euclid’s Division Lemma

a = b q + r . 

Where q is called the quotient and r is called the remainder where 0 ≤ r < b. 

Note : 

The HCF ( Highest Common Factor ) of two numbers can be found using Euclid's division lemma and the Euclid division algorithm. It says that given any two integers, a and b, there exists a pair of integers, q, and r, such that a = bq + r, where 0 ≤ r < b, is satisfied.

Example 1:

given numbers are, 39(=a) and 6(=b) we can write it in a = bq + r form as,

=> 39 = 6×6 + 3 

where, 

quotient(q) => 6 

remainder(r) => 3

=> Now, the Euclid Division Lemma is, a = b × (q + r) can be written as

=> The quotient and the remainder are unique

Example 2:

Let's a = 23 and b = 5

According to Euclid's Division Lemma, there exist unique integers q and r 

=> a=bq+r, where 0 < r < b -------------------------- eq (1)

=> divide both sides by b

=> then  $$\frac{a}{b}=\frac{bq}{b}+\frac{r}{b}$$ 

=> Now change the position and the equation becomes 

=>  $$q=\frac{a}{b}-\frac{r}{b},-------eq(2)$$ 

=> now  $$q=\frac{23}{5}=4$$  

Tips: 

q=4 indicates how many times b can be subtracted from a before reaching the remainder  r

We start by subtracting multiples of b from a until the result is less than a

 $$23-5=(18)$$  $$18-5=(13)$$  $$13-5=(8)$$  $$8-5=(3)$$ 

Now at this point, we've subtracted b four times before the result became less than b. Therefore q=4

from eq(1)  

 $$r=a-qb$$ 

put the value of q, b, and a in the above equation 

=> $$r=23-4\times 5$$

=> r = 3, now the condition is fulfilled 0 < r < b