Question

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

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

Answer 1

The correct option is 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$