1.26 Theorem Prove the existence part of the Division Algorithm.

The Theorem

Let $n$ and $m$ be natural numbers. Then (existence part)
there exists integers $q$ (for quotient) and $r$ (for remainder) such that

m = n q + r

$\begin{align} \ m & = nq +r \notag \\ \end{align}$

and $0 \le r \le n-1.$ Moreover (uniqueness part), if $q$ , $q'$ , and $r$ , $r'$ are integers that satisfy

m = n q + r = n q' + r'

$\begin{align} \ m & = nq +r \notag \\ & = nq' +r' \notag \\ \end{align}$

with $0 \le r, r' \le n-1$ , then $q = q'$ and $r= r'$ .

Attempted Proof

Let $S$ be the set of natural numbers $ni$ , where $i$ is a natural number such that $ni > m$ . By the Well-Ordering Axiom, $S$ has a smallest a smallest element, call it $nj$ .

n j - m n (j - 1)        q \leq n \leq m else n (j - 1) would be a smaller element

$\begin{align} nj - m & \le n && \text{else } n(j-1) \text{ would be a smaller element} \notag \\ n \underbrace{(j-1)} _q & \le m \notag \\ \end{align}$

Since $n(j-1) \le m$ there must exist an integer $r$ such that

n (j - 1)        q + r = m given 0 \leq r

$\begin{align} n \underbrace{(j-1)} _q + r & = m && \text{given } 0 \le r \notag \\ \end{align}$

if $r$ were $\ge n$ then there would exist a natural number $z$ such that $r = n + z$

n (j - 1)        q + n + z n j + z n j n j \geq m \land n j f a l s e = m = m \geq m < m given 0 \leq r given 0 \leq r given 0 \leq r given 0 \leq r

$\begin{align} n \underbrace{(j-1)} _q + n + z & = m && \text{given } 0 \le r \notag \\ nj + z & = m && \text{given } 0 \le r \notag \\ nj &\ge m && \text{given } 0 \le r \notag \\ nj \ge m \land nj &< m && \text{given } 0 \le r \notag \\ false \notag \\ \end{align}$

So we have that $r < n$ .

n (j - 1)        q + r = m given 0 \leq r \leq n - 1

$\begin{align} n \underbrace{(j-1)} _q + r & = m && \text{given } 0 \le r \le n-1 \notag \\ \end{align}$

Let $q$ be the integer $j-1$ , and we get

n q + r = m given 0 \leq r \leq n - 1

$\begin{align} nq + r & = m && \text{given } 0 \le r \le n-1 \notag \\ \end{align}$

□ $\Box$

Getting Blogger to correctly display and preview MathJax was a little tricky. You have to add the following to the <head> section of your template:

<head>
<script src='https://c328740.ssl.cf1.rackcdn.com/mathjax/latest/MathJax.js' type='text/javascript'>    
    MathJax.Hub.Config({
    HTML: ["input/TeX","output/HTML-CSS"],
    TeX: { extensions: ["AMSmath.js","AMSsymbols.js"], 
         equationNumbers: { autoNumber: "AMS" } },
    extensions: ["tex2jax.js"],
    jax: ["input/TeX","output/HTML-CSS"],
    tex2jax: { inlineMath: [ ['$','$'], ["\\(","\\)"] ],
             displayMath: [ ['$$','$$'], ["\\[","\\]"] ],
             processEscapes: true },
    "HTML-CSS": { availableFonts: ["TeX"],
                linebreaks: { automatic: true } }
    });
</script>
...
</head>

Note: You must use https. Using http://cdn.mathjax.org/mathjax/latest/MathJax.js will not work in preview mode, and https://cdn.mathjax.org/mathjax/latest/MathJax.js does not work at all. https://c328740.ssl.cf1.rackcdn.com/mathjax/latest/MathJax.js is the only url that I found to always work correctly1

http://www.mathjax.org/resources/faqs/#problem-https ↩

Page Left Blank

Sunday, March 9, 2014

1.26 Theorem

The Theorem

Attempted Proof

Off Topic

First Post

Blog Archive