Question

Euclid's division lemma states that for two positive integers a and b, there exist unique integers q and r such that $a=bq+r$, where r must satisfy

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

Answer 1

Answer: (C)

$0\le r<b$

If $r$ must satisfy$0\le r<b$
Proof,
$..,a-3b,a-2b,a-b,a,a+b,a+2b,a+3b,..$
clearly it is an arithmetic progression with common difference $b$ and it extends infinitely in both directions.
Let $r$ be the smallest non-negative term of this arithmetic progression.Then,there exists a non-negative integer $q$ such that,
$a-bq=r$
$=>a=bq+r$
As,$r$ is the smallest non-negative integer satisfying the result.Therefore, $0\le r\le b$
Thus, we have
$a=b{q}_1+r_1$, $0\le r_1\le b$