\documentclass[12pt]{article}

    \oddsidemargin -.25in       % Lt Margin adj for odd pages (0 = 1" margin)
    \evensidemargin -.25in      % Rt Margin adjustment for even pages
    \topmargin -.5in            % adj top margin from 1"
    \footskip .5in
    \textwidth 7in              % width of printed area
    \textheight 9in             % height of printed area

   % \pagestyle{empty}

\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{psfig}

\newcommand{\bfrac}[2]{\displaystyle \frac{#1}{#2}}
\newcommand{\limit}[2]{\displaystyle \lim_{{#1} \rightarrow {#2}} }
\newcommand{\displ}{\displaystyle}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\pict}[3]{\epsfxsize=#1in \epsfysize=#2in  
                            \epsffile{#3.eps}}

\newcommand{\C}{{\mathbb C}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\D}{{\cal D}}
\newcommand{\Q}{{\cal Q}}
\newcommand{\h}{{\mathfrak h}}


\begin{document}

\noindent
{\Large More on Divisibility Proofs  \hfill Name:\underline{\hspace{2.8in}}\\
A\&S100, Section 002 \\
16 October 2002}

\vspace{.2in}

I think I have found a way to make the divisibilty tests for powers of $2$
(i.e. $2,4,8,16,32,$ etc.) a bit easier. (Yeah!)  Before we get to that,
let's look at a few examples.  Consider the number $123,456$.  We can break
this number as follows:
	\begin {center}
	\begin {tabular} {ccc}
	$123,456$ & $=$ & $123,000+456$ \\
	& $=$ & $123 \times 1000 +456$ \\
	& $=$ & $123 \times 10^3 +456$ \\
	\end {tabular}
	\end {center}
Or, if it suits our purposes better, we could break it up as
	\begin {center}
        \begin {tabular} {ccc}
        $123,456$ & $=$ & $120,000+3,456$ \\
        & $=$ & $12 \times 10,000 +3,456$ \\
        & $=$ & $12 \times 10^4 +3,456$ \\
        \end {tabular}
        \end {center}
or even as
	\begin {center}
        \begin {tabular} {ccc}
        $123,456$ & $=$ & $123,400+56$ \\
        & $=$ & $1234 \times 100 +56$ \\
        & $=$ & $1234 \times 10^2 +56$ \\
        \end {tabular}
        \end {center}
In fact, we can split this number anywhere we like in a similar manner. 
In the general case, we have
$$a_m \cdots a_4a_3a_2a_1a_0 = a_m \cdots a_4a_3a_2a_1 \times 10 + a_0$$
\begin {center} or \end {center}
$$a_m \cdots a_4a_3a_2a_1a_0 = a_m \cdots a_4a_3a_2 \times 10^2 + a_1a_0$$
\begin {center} or \end {center}
$$a_m \cdots a_4a_3a_2a_1a_0 = a_m \cdots a_4a_3 \times 10^3 + a_2a_1a_0$$
\begin {center} or \end {center}
$$a_m \cdots a_4a_3a_2a_1a_0 = a_m \cdots a_4 \times 10^4 + a_3a_2a_1a_0$$
or, or, or, . . . Basically, we can keep this up until we run out of digits.
With these general numbers we will not run out of digits.  If you need an $a_5$,
put it in.  If you need an $a_7$, write the number as $a_m \cdots
a_7a_6a_5a_4a_3a_2a_1a_0$.  We now have lots of different ways to write our
number.  We just need to figure out which one is most useful in the proof.  In
the case of proofs for divisibility by $2^k$ it happens to be the one
that contains $10^k$.  Let's take a look.

\newpage
\be
\item Prove that a positive integer is divisible by $8$ if and only if the 
	number formed by the last three digits of the integer are 
	divisible by $8$. \\ \\
	{\it Note: $8=2^3$ so we are going to break the number up at $10^3$.} 
	\\
	\\
	{\bf PROOF:}
	Let $N=a_m\cdots a_3a_2a_1a_0$ be a positive integer.  $N$ is 
	divisible by $8$ if and only if \\ \\
	$N \text{ mod } 8 = 0$ if and only if \\ \\
	$a_m\cdots a_3a_2a_1a_0 \text{ mod } 8 = 0$ if and only if \\ \\
	$(a_m\cdots a_3 \times 10^3 + a_2a_1a_0) \text{ mod } 8 = 0$. \\ \\
	Since $10^3 \text{ mod } 8 = 0$, it now follows that $N \text{ mod }
	8 = 0$ if and only if \\ \\
	$(a_m\cdots a_3 \times 0 + a_2a_1a_0) \text{ mod } 8 = 0$ if and
	only if \\ \\
	$a_2a_1a_0 \text{ mod } 8 = 0$ if and only if \\ \\
	the number formed by the last three digits of $N$ is divisible by $8$.
	$\Box$
\item Prove that a positive integer is divisible by $32$ if and only if the
        number formed by the last five digits of the integer are
        divisible by $32$. \\ \\
        {\it Note: $32=2^5$ so we are going to break the number up at $10^5$.}
        \\
        \\
        {\bf PROOF:}
        Let $N=a_m\cdots a_5a_4a_3a_2a_1a_0$ be a positive integer.  $N$ is
        divisible by $32$ if and only if \\ \\
        $N \text{ mod } 32 = 0$ if and only if \\ \\
        $a_m\cdots a_5a_4a_3a_2a_1a_0 \text{ mod } 32 = 0$ if and only if \\ \\
        $(a_m\cdots a_5 \times 10^5 + a_4a_3a_2a_1a_0) \text{ mod } 32 = 0$. \\ 
	\\
        Since $10^5 \text{ mod } 32 = 0$, it now follows that $N \text{ mod }
        32 = 0$ if and only if \\ \\
        $(a_m\cdots a_5 \times 0 + a_4a_3a_2a_1a_0) \text{ mod } 32 = 0$ if and
        only if \\ \\
        $a_4a_3a_2a_1a_0 \text{ mod } 32 = 0$ if and only if \\ \\
        the number formed by the last five digits of $N$ is divisible by $32$.
        $\Box$
\newpage
\item Prove that a positive integer is divisible by $2$ if and only if the
	last digit of the integer is divisible by $2$.  ({\it Or, said another
	way, the last digit is even.}) \\
        {\it Note: $2=2^1$ so we are going to break the number up at $10^1 =
	10$.}
        \\
        \\
        {\bf PROOF:}
        Let $N=a_m\cdots a_3a_2a_1a_0$ be a positive integer.  $N$ is
        divisible by $2$ if and only if \\ \\
        $N \text{ mod } 2 = 0$ if and only if \\ \\
        $a_m\cdots a_3a_2a_1a_0 \text{ mod } 2 = 0$ if and only if \\ \\
        $(a_m\cdots a_3a_2a_1 \times 10^1 + a_0) \text{ mod } 2 = 0$. \\ \\
        Since $10^1 \text{ mod } 2 = 0$, it now follows that $N \text{ mod }
        2 = 0$ if and only if \\ \\
        $(a_m\cdots a_3a_2a_1 \times 0 + a_0) \text{ mod } 2 = 0$ if and
        only if \\ \\
        $a_0 \text{ mod } 2 = 0$ if and only if \\ \\
        the last digit of $N$ is divisible by $2$.
        $\Box$
\ee 
While we are discussing divisibility proofs, we might as well work through
a couple more of them.  The divisibility tests that follow are for divisors
which are NOT powers of $2$ so we can always go back to our old friend the base
$10$ expansion.  Before doing that though, check to see if the new way of
writing numbers will make things easier.  Sometimes, it is helpful
and can make for a shorter proof, as in the proofs for the divisibility tests
by $5$ and by $10$. However, the new way of writing numbers does not appear to 
be helpful when trying to prove the divisibilty tests for $3$ and $9$ so we will
probably have to continue to use the base $10$ expanision when doing the 
proofs of the divisibility tests for $3$ and $9$.  Sorry! 
\newpage
\be
\item Prove that a positive integer is divisible by $5$ if and only if its 
	last digit is a $5$ or a $0$. \\
	\\
	{\bf PROOF:} Let $N=a_m\cdots a_3a_2a_1a_0$ be a positive integer.
	$N$ is divisible by $5$ if and only if \\ \\
	$N \text { mod } 5 = 0$ if and only if \\ \\
	$a_m\cdots a_3a_2a_1a_0 \text { mod } 5 = 0$ if and only if  \\ \\
	$(a_m\cdots a_3a_2a_1 \times 10 + a_0) \text { mod } 5 = 0$. \\ \\
	Since $10 \text { mod } 5 = 0$, it follows that $N \text { mod } 5 
	= 0$ if and only if \\ \\
	$(a_m\cdots  a_3a_2a_1\times 0 + a_0) \text { mod } 5 = 0$  
	if and only if \\ \\
	$a_0 \text { mod } 5 = 0$ if and only if \\ \\
	the last digit of $N$ is divisible by 5 if and only if \\ \\ 
	the last digit of $N$ is a $5$ or a $0$. $\Box$
\item Prove that a positive integer is divisible by $10$ if and only if its
        last digit is a $0$. \\
        \\
        {\bf PROOF:} Let $N=a_m\cdots a_3a_2a_1a_0$ be a positive integer.
        $N$ is divisible by $10$ if and only if \\ \\
        $N \text { mod } 10 = 0$ if and only if \\ \\
        $a_m\cdots a_3a_2a_1a_0 \text { mod } 10 = 0$ if and only if  \\ \\
        $(a_m \cdots a_3a_2a_1 \times 10 + a_0) \text { mod } 10 = 0$. \\ \\
        Since $10 \text { mod } 10 = 0$, it follows that $N \text { mod } 10
        = 0$ if and only if \\ \\
        $(a_m\cdots a_3a_2a_1 \times 0 + a_0) \text { mod } 10 = 0$  
	if and only if \\ \\
        $a_0 \text { mod } 10 = 0$ if and only if \\ \\
        the last digit of $N$ is divisible by 10 if and only if \\ \\
        the last digit of $N$ is a $0$. $\Box$
\newpage
\item Prove that a positive integer is divisible by $3$ if and only if the sum
	of its digits is divisible by $3$. \\
        \\
        {\bf PROOF:} Let $N=a_m\cdots a_3a_2a_1a_0$ be a positive integer.
        $N$ is divisible by $3$ if and only if \\ \\
        $N \text { mod } 3 = 0$ if and only if \\ \\
        $a_m\cdots a_3a_2a_1a_0 \text { mod } 3 = 0$ if and only if  \\ \\
        $(a_m \times 10^m + \cdots +  a_3 \times 10^ 3 + a_2 \times 10^ 2 +
	a_1 \times 10 + a_0) \text { mod } 3 = 0$. \\ \\
        Since $10 \text { mod } 3 = 1$, it follows that $N \text { mod } 3
        = 0$ if and only if \\ \\
        $(a_m \times 1^m + \cdots +  a_3 \times 1^ 3 + a_2 \times 1^ 2 +
	a_1 \times 1 + a_0) \text { mod } 3 = 0$ if and only if \\ \\
        $(a_m + \cdots + a_3 + a_2 + a_1 + a_0) \text { mod } 3 = 0$ 
	if and only if \\ \\
        the sum of $N$'s digits is divisible by $3$. $\Box$
\ee

Hope this helps! \\ \\ \\

Jakayla
\end {document}


