Question

Prove the uniqueness of $q$ and $r$ in Euclid division Lemma.
i.e., let $a$ and $b$ be any two positive integers there exist unique integers $q$ and $r$, $a=bq+r,0\le r\le b$.

Answer 1

Euclid's division lemma : Let ‘$a$’ and ‘$b$’ be any two positive integers. Then there exist unique integers ‘q’ and ‘r’ such that
$a=bq+r,0\le r\le b$.
If $b|a$, then $r=0$
Otherwise, $‘r^{\prime }$ satisfies the stronger inequality $0\le r\le b$.

Proof : Consider the following arithmetic progression
$\dots ,a–3b,a–2b,a–b,a,a+b,a+2b,a+3b,\dots$
Clearly, it is an arithmetic progression with common difference $‘b^{\prime }$ and it extends infinitely in both the directions.
Let $‘r^{\prime }$ be the smallest non-negative term of this arithmetic progression. Then, there exists a non-negative integer ‘q’ such that,
$a–bq=r\Rightarrow a=bq+r$
As, $r$ is the smallest non-negative integer satisfying the above result.
Therefore, $0\le r\le b$
Thus, we have
$a=b{q}_1+r_1$ , $0\le r_1\le b$
We shall now prove that $r_1=r$ and $q_1=q$

We have, $a=bq+r$ and $a=b{q}_1+r_1$
$\Rightarrow bq+r=b{q}_1+r_1$
$\Rightarrow r_1–r=b{q}_1–bq$
$\Rightarrow r_1–r=b(q_1–q)$
$\Rightarrow b|r_1–r$
$\Rightarrow r_1–r=0$ [ since $0\le r\le b$ and $0\le r_1\le b\Rightarrow 0\le r_1-r\le 0$ ]
$\Rightarrow r1=r$
Now, $r_1=r$
$\Rightarrow -r_1=-r$
$\Rightarrow a–r_1=a–r$
$\Rightarrow b{q}_1=bq$
$\Rightarrow q_1=q$
Hence, the representation $a=bq+r,0\le r\le b$ is unique.