Please Login to access more options.

Problem 15(Division Algorithm Proof)

Prove the Division algorithm.

Solution

Let $a,n \in \mathbb{Z}$, with $a,n > 0$. Since $a,n \in \mathbb{Z}$, we know that $\frac{a}{n} \in \mathbb{Q}$. There are two cases we will consider. First, suppose $\frac{a}{n}\in \mathbb{Z}$. In this case, let $q=\frac{a}{n}$ and $r=0$, and it follows that $a=qn+r$.

Now, we will suppose that $\frac{a}{n} \notin \mathbb{Z}$. Since $\frac{a}{n} \notin \mathbb{Z}$ and $n>0$, we know that $n\neq 1$. Thus, we know $a>\frac{a}{n}$. Let $S=\left\{ k\in \mathbb{N} | k>\frac{a}{n} \right\}$. Since $a>\frac{a}{n}$ and $a\in \mathbb{N}$, we know that $a\in S$, and hence $S$ is nonempty. By the Well-Ordering principle, we know that $S$ has a least element, call it $j+1$. It follows that $j\leq \frac{a}{n}<j+1$. Multiplying by $n$ we obtain $jn\leq a < jn+n$. Subtracting $jn$ we obtain $0\leq a-jn < n$. Let $r=a-jn$. Let $q=j$. Since $a,n,j \in \mathbb{Z}$, we know that $q,r \in \mathbb{Z}$. Clearly $0\leq r < n$. We compute $qn+r=jn+(a-jn)=a$.

From Ben: This completes the existence half of the proof. It does not complete the uniqueness part, but this is more than than sufficient fora weekly write up. Have fun exploring more topics. This is complete.
  • 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.