Doubt with wikipedia's proof of Euclidean Division

Question

The proof in the Wikipedia for Euclidean Division is

"Let $q_1 = 0$ and $r_1 = a$, then these are non-negative numbers such that $a = b.q_1 + r_1$. If $r_1 < b$ then the division is complete, so suppose $r_1 ≥ b$. Then defining $q_2 = q_1 + 1$ and $r_2 = r_1 – b$, one has $a = b.q_2 + r_2$ with $0 ≤ r_2 < r_1$. As there are only $r_1$ non-negative integers less than $r_1$, one only needs to repeat this process at most $r_1$ times to reach the final quotient and the remainder. That is, there exist a natural number $k ≤ r_1$ such that $a = b.q_k + r_k$ and $0 ≤ r_k < |b|$."

How can I show that $0 ≤ r_k < |b|$?

Answer 1

Given $a\in\Bbb N_0$, $b\in\Bbb N$, let $$A=\{\,r\in\Bbb N_0\mid \exists q\in\Bbb N_0\colon a=qb+r\,\}. $$ Then $A$ is a non-empty (because $a\in A$) subset of $\Bbb N_0$, hence has a minimal element $r$. For this $r$, there exists $q\in\Bbb N_0$ with $a=qb+r$. If $r\ge b$, we find from $a=(q+1)b+(r-b)$ that $r-b\in A$, contradicting minimality. Hence $0\le r<b$.

Answer 2

The idea is you have

$a = 0*b + a$ and if $0 \le a < b$ you are done. If not you have

$a = 1*b + r_1$ and $r_1 = a-b\ge 0$. If $0\le r_1 < b$ you are done. If not you have $r_1 \ge b$ and

$a = 2*b + r_2$ and $r_2 = r_1 - b$. Now $r_2 < r_1$ also $0\le r_2 \le r_1 -1$. And $r_1 \ge b$ so $r_2 = r_1 - b \ge 0$. Either $0 \le r_2 < b$ or $r_2 \ge b$. If $0 \le r_2 < b$ we are done. If not we have $r_2 \ge b$ and

$a = 3*b + r_3$ and $r_3 = r_2 -b$. Now $r_3 < r_2 < r_1$ so $0\le r_3 \le r_2-1 \le r_1-2$. And $r_2 \ge b$ so $r_3=r_2 - b\ge 0$. Either $0\le r_3 < b$ or $r_3 \ge b$. If $0 \le r_2 < b$ we are done. If not we have $r_3 \ge b$ and

.... we can repeat this....

But each time we repeat this we get $r_k < r_{k-1} < .....< r_1$ and so $0\le r_k \le r_{k-1} - 1 \le ..... \le r_1 -(k-1)$.

We can't repeat that for ever. If $k > r_1 + 1$ times. (Then we'd get $0\le r_{r_1+1} \le r_1 - (k-1) < 0$). so eventually we have to come to the very last time we can repeat it.

....

And this point we have $a = k*b + r_k$ and $r_k \ge b$. BUT THIS IS THE LAST TIME.

$a = (k+1)b + r_{k+1}$ where $r_{k+1} = b - r_k \ge 0$. Now either $0 \le r_{k+1}< b$ or $r_{k+1} \ge b$. If $0\le r_{k+1}< b $ we are done. And if $r_{k+1} \ge b$ we can repeat it and.... NO! We can't repeat it forever and we just so $r_k$ was the last repeat. $b \ge r_{k+1}$ is not an option. And $r_k \ge b$ so $r_{k+1} = b - r_k \ge 0$ ..... so that means $0 \le r_{k+1} < b$ and we are finally done with no repeats avaiable.

....

Example if $a= 35$ and $b= 8$.

We have $35 = 0*8 + 35$

$35 = 1*8 + 27$

$35 = 2*8 + 19$

$35 = 3*8 + 11$

...... now we 1) can't keep going forever and 2) we can't jump from $11 > 8$ but $11 - 8 < 0$ so we've reached the end of our rope! The nest step has to end it!

$35 = 4*8 + 3$ and $0 < 3 < 8$. We couldn't stay above $8$ forever and we couldn't jump to $r_k < 0$ without going through $0 \le r_k < 8$ in between.