Question

According to Euclid's division algorithm, HCF of any two positive integers $a$ and $b$ with $a>b$ is obtained by applying Euclid's division lemma to $a$ and $b$ to find $q$ and $r$ such that $a=bq+r$, where $r$ must satisfy

• A. $1<r<b$
• B. $0<r<b$
• C. $0\le r<b$
• D. $0<r\le b$

Answer 1

The correct option is C $0\le r<b$

According to Euclid's division algorithm, HCF of any two positive integers $a$ and $b$ with $a>b$ is obtained by applying Euclid's division lemma to $a$ and $b$ to find $q$ and $r$ such that $a=bq+r$

The remainder $r$ is either equal to or greater than $0$ but it is always smaller than divisor $b$.

i.e $0\le r<b$

Hence, option C is correct.