Question

$\text{If HCF (1008, 20) = HCF (20, a)}\text{= HCF(a,b) where}1008=20\times q+a\text{and}20=a\times m+b.$

Here, q, a, m and b being positive integers satisfying Euclid’s division lemma. What could be the values of a and b?

• A. 8, 4
• B. 10, 4
• C. 20, 8
• D. 24, 8

Answer 1

The correct option is A

8, 4

$\text{If}p=d\times q+r,(p>q)\text{where p, q, d, r}\text{are integers and for a given (p, d),}\text{there exist a unique (q, r), then}HCF(p,d)=HCF(d,r).$

Since this relation holds true, the Euclid’s Division Algorithm exists in a step by step manner.
So, to find the HCF(1008, 20), we use Euclid’s division lemma at every step.

$\text{Step 1:}1008=20\times 50+8\Rightarrow \text{HCF(1008, 20) = HCF(20, 8)}\Rightarrow \text{a could be 8.}$

$\text{Step 2:}20=8\times 2+4\Rightarrow \text{HCF(20, 8) = HCF(8, 4)}\Rightarrow \text{b could be 4.}$

$\text{Step 3:}8=4\times 2+0$

$\therefore \text{HCF = 4.}$

$\text{Since}1008=20\times q+a,\text{where q and}\text{a are positive integers which satisfy}\text{Euclid’s division lemma, we must have}0\le a<20.\text{So, a is surely 8 and b is 4.}$