# Proof of Quotient-Remainder Theorem by induction

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?

• 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.
– dxiv
Sep 16 '16 at 4:36
• 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. Sep 16 '16 at 5:09

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.

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.

• 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 Sep 16 '16 at 5:05

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.

• My emphasis is on using proof by induction Sep 16 '16 at 5:02
• I am not sure how to prove my induction though. Are you able to give me some hints to start with? Sep 16 '16 at 6:14
• @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.
– dxiv
Sep 16 '16 at 6:22