0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Try to write down the first few steps of your proof. You'll realize that what's proved is $a = 0 \cdot b + a$, which is true of course, but it's not the quotient-remainder theorem you were trying to prove. $\endgroup$
    – dxiv
    Sep 16 '16 at 4:36
  • $\begingroup$ Two problems. You haven't proven uniqueness. And you induction proves for all a; a =0b + a. You did not take into account that r+1 might >= b. $\endgroup$
    – fleablood
    Sep 16 '16 at 5:09
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yup. I understand that r + 1 may be equal to b. r + 1 is the remainder in this case i.e. y = r + 1 < b $\endgroup$
    – Donald
    Sep 16 '16 at 5:05
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ My emphasis is on using proof by induction $\endgroup$
    – Donald
    Sep 16 '16 at 5:02
  • $\begingroup$ I am not sure how to prove my induction though. Are you able to give me some hints to start with? $\endgroup$
    – Donald
    Sep 16 '16 at 6:14
  • $\begingroup$ @LanceHAOH See the other answer posted already. As long as $r+1 \lt b$ your construction works. But when you reach the next multiple of $b$ the proof as written now keeps incrementing $r$ so that it reaches $r+1=b$ and goes outside the target interval $[0,b)$. Instead, you need to increment $q$ and reset $r$ to 0. For uniqueness, assume there are two such distinct representations, and try to derive a contradiction. $\endgroup$
    – dxiv
    Sep 16 '16 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.