Proof of Quotient-Remainder Theorem by induction

Question

I am trying to prove the quotient-remainder theorem by mathematical induction:

Quotient-Remainder Theorem:

$\forall a,b \in \mathbb{Z}, b> 0: \ \exists! q, \ r \in \mathbb{Z}, \ a = bq \ + \ r, \ r \in [0,b) $

Proof that $ a \in \mathbb{Z} $ exists:

        Divide into 2 cases: $ a \ge 0 $ or $ a < 0 $

                  Case 1: $ a \ge 0 $

                          Base Case: Let $ a = 0 $.

                                  It is clear that if we let $ q = r = 0 $, then $ a = b(0) + (0) = 0 $.

                                  Hence, base case is true.

                          Inductive Step: Assume $ a = k \in \mathbb{Z} $ exists

                                  Hence, $ k = bq + r $

                          Proof: Let $ a = k + 1\in \mathbb{Z} $

                                  By inductive hypothesis, $ k = bq + r $

                                  Hence, $ k + 1 = bq + r + 1 $ and $ k + 1 = bq + (r + 1) $ where $ r + 1 \in \mathbb{Z} $

                                  by closure property of integers

                                  Thus, $ \forall a \in \mathbb{Z}, a \ge 0 \ $, $ a = bq + r $

                  Case 2: $ a < 0 $

                          Base Case: Let $ a = -1 $.

                                  It is clear that if we let $ q = 0 $ and $ r = -1 $, then $ a = b(0) + (-1) = -1 $.

                                  Hence, base case is true.

                          Inductive Step: Assume $ a = k \in \mathbb{Z} $ exists

                                  Hence, $ k = bq + r $

                          Proof: Assume $ a = -(k + 1) \in \mathbb{Z} $

                                  By inductive hypothesis, $ k = bq + r $

                                  Hence, $ k + 1 = bq + r + 1 $ and $ -(k + 1) = b(-q) + (-r - 1) $ where

                                  $ -r - 1 \in \mathbb{Z} $ by closure property of integers

                                  Thus, $ \forall a \in \mathbb{Z}, a < 0 \ $, $ a = bq + r $

I am not sure if my proof is correct. Also, I do not know how to prove $ r \in [0,b) $ and the uniqueness of $ q $ and $ r $. Could someone please advise me?

Answer 1

Your induction case didn't take $r+1=b $ into account and in the end all you proved was $a=0b+a $.

Do this: assume $a=qb+r;0\le r <b $. If $r <b-1$ then $a+1 = qb + (r+1) $. And if $r=b-1$ then $a+1 =qb +r+1 =qb+b= (q+1)b+0$.

So if $a =qb +r;r\in [0,b) $ has solution the $a+1=pb+s;s\in [0,b) $ has solution.

One can do the same for $a-1$. If $a=qb+r$ and $r > 0$ then $a-1= qb +(r-1) $ is a solution. If $r=0$ then $a-1= (q-1)b +(b-1) $ is a solution.

But I haven't shown they are unique. You can show uniqueness via induction and I spent a long time in my rough draft showing just that. But in the end it was unnecessarily complicated and confusing and, frankly bizarre. (I'll leave it in as a post script.) It's much better to show uniqueness directly.

Suppose $a=qb+r=pq+s $ then $(r-s)=(p-q)b $. If $r,s \in [0,b) $ then $-b < r-s =(p-q)b <b $. So $-1 < p-q < 1$ so $p-q=0;p=q $ and $r=s $.

So solutions are unique.

=== postscript: bizarre rough draft==

Base step. Need to show $0=0b + 0$ is unique.

Proof: (assume all variables in this post are integers.)

If $0=qb +r$ then $r = -qb $. If $q \le -1$ the $r \ge b $ which isn't acceptable. If $q >0$ then $r < 0$ which isn't acceptable. So $0,0$ is unique solution.

Induction case.

$a=qb+r $ is unique solution.

Let $a+1 = pb +s;0\le s <b $ be an acceptable solution (if there is one, which we need to be aware there might not be).

Then $a = pb + s-1;-1\le s-1 < b-1 $. If $s -1 \ge 0$ then $p=q $ and $s=r+1$ (and $r < b-1$) as $p,r $ was a unique solution. So $p=q;s=r+1$ would be a solution and it would be unique.

But it is a solution. So it is unique

Otherwise if our hypothetical solution had $s=0$ then it would follow $r= b-1$. We would have $a+1 = pq +0 = qb +r+1= qb+b =(q+1)b $ and so $p=q+1$ and $s=0$. That would have to be the solution and it would be unique.

But it is a solution. So it is unique.

Answer 2

It isn't quite correct. In your line for the case $a > 0$, "Hence, $k+1=bq+r+1$ and $k+1=bq+(r+1)$ where $r+1 \in \mathbb{Z}$", $r+1$ may be equal to $b$ which violates the statement of the theorem. So you need to add, "If $r+1=b$, then choose $q = q+1$ and $r=0$." A similar statement is necessary in your other inductive step.

Answer 3

I am trying to prove the quotient-remainder theorem by mathematical induction

It's not clear from the context whether the emphasis is on "by induction" or on "prove the quotient-remainder theorem".

If the latter, then the intuition is that $\bigcup_{k \in \mathbb{Z}} \{k b, k b + 1, k b + 2, ..., k b + (b-1)\}$ is a partition of $\mathbb{Z}$ for $b \in \mathbb{N}^+$, since it's a union of adjacent, non-overlapping sets of consecutive $b$ integers each. It follows that any $a \in \mathbb{Z}$ will fall into exactly one such set $\{k b, k b + 1, k b + 2, ..., k b + (b-1)\}$, so taking $q = k, r = a - q b$ proves the proposition, both existence and unicity.