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 -   {q}{b} \] 

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