Please Login to access more options.

Problem 15(Division Algorithm Proof)

Prove the Division algorithm.

Theorem (Division Algorithm)

Let $a,n\in\mathbb{Z}$, with $n> 0$. Then there exists unique integers $q$ and $r$ (called the quotient and remainder) such that $a=qn+r$ where $0\leq r<n$.

Solution

Let $a,n\in \mathbb{Z}$ and $n>0$. We must prove that there exist unique integers $q$ and $r$ (which we call the quotient and remainder) such that $a=qn+r$ where $0\le r < n$. We first will prove there exist a $q$ and $r$ where $a=qn+r$. Let $S=\{a-nk | k\in \mathbb{Z} \text{ and } a-nk\ge 0\}.$ Suppose $0\in S$. Then $n$ divides $a$ and we obtain $q=\frac{a}{n}$ and we know $r=0$.

Now we suppose $0\notin S$. We claim that $S$ is a nonempty set. To prove this, suppose $a>0,$ then we know $a-n\cdot 0 \in S$, and $S$ has at least one element. Now suppose $a<0,$ then we let $k=2a$ and we have $a-n(2a)=a(1-2n)\in S$. Since $n>0$ we know $1-2n<0$ and we see that $a(1-2n)>0$. Note $a\neq 0$ since $0\notin S$. Thus we see that $S$ is nonempty. We know by the well ordering principle and the fact that every element in $S$ is a positive integer that $S$ has a smallest member, denoted min$\{S\}$. We will let $r=\text{min}\{S\}$ and note $r=a-nk$ for some $k\in \mathbb{z}.$ We let $q=k$ and note this means $q\in \mathbb{Z}$ as well.

Let us show that $r\geq 0$. Since $r=\min(S)$ and each $s\in S\geq 0$ by construction, we know that $r\geq 0$. Now we will prove that $r<n$. Suppose by way of contradiction that $r\geq n$. Then we know $a-n(q+1)=a-nq-n=r-n\geq 0$. Note we are using $k=q+1$. This means $a-n(q+1)\in S$. However, we have $a-n(q+1) < a-nq$, and we said $a-nq$ is the smallest member of $S$. Therefore, we have a contradiction and we know that $r<n$.

The last part we will prove is that $q$ and $r$ are unique for the given $a$ and $n$. We suppose that there exist $q, q', r, r' \in \mathbb{Z}$ such that $a=nq+r$ where $0\leq r < n$ and $a=nq' + r'$ where $0\leq r' < n$. Without loss of generality we may suppose $r'\geq r$. Then we have $nq+r=nq'+r'$, which implies $n(q-q')=(r-r').$ Thus $n$ divides $r'-r$. Since $r'\geq r$ we know $0\leq r'-r$. Since $r\geq 0$ we know $r'-r\leq r'$. Thus since $r'<n$ we can put this all together as follows: \begin{equation*} 0\leq r'-r \leq r' < n. \end{equation*} We know that $r'-r$ is a multiple of $n$, which means $r'-r \in \{0, n, 2n, 3n, \cdots \}$. Thus since $r'-r<n$ and $r'-r\geq 0$ we know the only option left is $r'-r=0$. Therefore we have shown $r'=r$.

Recall that $a=nq-r$ and $a=nq'-r'$. Since these both equal $a$, we get $nq-r=nq'-r'.$ Since $r=r'$ we can add $r$ to both sides, which yields $ nq=nq'.$ By canceling the $n$'s we see that $q=q'.$ Therefore, $r$ and $q$ must be unique. $\square$

Tags
  • When you are ready to submit this written work for grading, add the phrase [[!Submit]] to your page. This will tell me that you have completed the page (it's past rough draft form, and you believe it is in final draft form). Don't type [[!Submit]] on a rough draft.
  • If I put [[!NeedsWork]] on your page, then your job is to review what I've written, address any comments made, and then delete all the comments I made. When you have finished reviewing your work, leave [[!NeedsWork]] on your page and type [[!Submit]]. (Both tags will show up). This tells me you have addressed the comments.
  • I'll mark your work with [[!Complete]] after you have made appropriate revisions.