trunk/c_mtn0/c_mtn0.tex

%$Header$

\chapter[\cmtnzeroshorttitle{}]{\cmtnzerolongtitle{}}

\label{cmtn0}

\beginchapterquote{``If intellectual curiosity, professional pride, and ambition are
                     the dominant incentives to research, then assuredly no one has
                     a fairer chance of gratifying them than a mathematician.  His
                     subject is the most curious of all---there is none in which
                     truth plays such odd pranks.  It has the most elaborate
                     and the most fascinating technique, and gives unrivaled
                     openings for the display of sheer professional skill.  Finally,
                     as history proves abundantly, mathematical achievement, whatever
                     its intrinsic worth, is the most enduring
                     of all.''}
                     {G.H. Hardy \cite{bibref:b:mathematiciansapology:1940}}

\section{Introduction}
%Section Tag: INT0
\label{cmtn0:sint0}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\index{floor function@floor function ($\lfloor\cdot\rfloor$)}%
\index{--@$\lfloor\cdot\rfloor$ (\emph{floor($\cdot$)} function)}%
\index{ceiling function@ceiling function ($\lceil\cdot\rceil$)}%
\index{--@$\lceil\cdot\rceil$ (\emph{ceiling($\cdot$)} function)}%
\section{The Floor \mbox{\boldmath $\lfloor\cdot\rfloor$} And Ceiling \mbox{\boldmath $\lceil\cdot\rceil$} Functions}
\label{cmtn0:sfcf0}

The \emph{floor} function, denoted $\lfloor\cdot\rfloor$, is defined to return
the largest integer not larger than the argument.  For example, 
$\lfloor 3 \rfloor = \lfloor 3.9999 \rfloor = 3$.  For negative arguments, the definition
is identical:  $\lfloor -4 \rfloor = \lfloor -3.9 \rfloor = -4$.

The \emph{ceiling} function, denoted $\lceil\cdot\rceil$, is defined to return
the smallest integer not less than the argument.  For example, 
$\lceil 3.0001 \rceil = \lceil 4 \rceil = 4$.  For negative arguments, the definition
is identical:  $\lceil -4 \rceil = \lceil -4.9 \rceil = -4$.

Note that the definitions presented above for negative arguments
differ from what is commonly implemented in spreadsheet software and other consumer
software.

It can be verfied easily that for 
$a \in \vworkintsetnonneg$, $b \in \vworkintsetpos$,

\begin{equation}
\label{eq:cmtn0:sfcf0:01}
\frac{a}{b} = \left\lfloor\frac{a}{b}\right\rfloor + \frac{a \bmod b}{b}
\end{equation}

\noindent{}and consequently that

\begin{equation}
\label{eq:cmtn0:sfcf0:02}
\left\lfloor\frac{a}{b}\right\rfloor = \frac{a}{b} - \frac{a \bmod b}{b} .
\end{equation}

\noindent{}(\ref{eq:cmtn0:sfcf0:02}) is a very useful identity for 
decomposing expressions involving the \emph{floor($\cdot$)} function.

\section{Tests For Divisibility Of Integers}
%Section Tag: TDI0

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Tests For Divisibility By 2, 3, 5, 6, 7, And 11}

It is often useful to be able to inspect a radix-10 integer and quickly
determine if it can be divided by a small prime number.  This section
presents tests which can be used to easily determine divisibility by
2, 3, 5, 7, and 11.

Placeholder\index{divisibility tests for integers!by 0002@by 2}
reserved for divisibility by 2.

Placeholder\index{divisibility tests for integers!by 0003@by 3}
reserved for divisibility by 3.

Placeholder\index{divisibility tests for integers!by 0005@by 5}
reserved for divisibility by 5.

Placeholder\index{divisibility tests for integers!by 0007@by 7}
reserved for divisibility by 7.

Placeholder\index{divisibility tests for integers!by 0011@by 11}
reserved for divisibility by 11.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Tests For Divisibility By  2$^N$, 6, 9, And 10$^N$}

Placeholder\index{divisibility tests for integers!by 0002N@by 2$^N$}
reserved for divisibility by 2$^N$.

Placeholder\index{divisibility tests for integers!by 0006@by 6}
reserved for divisibility by 6.

Placeholder\index{divisibility tests for integers!by 0009@by 9}
reserved for divisibility by 9.

Placeholder\index{divisibility tests for integers!by 0010N@by 10$^N$}
reserved for divisibility by 10$^N$.


\subsection{David G. Radcliffe's Proof:  Rearrangement Of Digits Of $2^N$}
%Subsection Tag: DGR0

In 07/00, Paul Harvey (\texttt{pharvey@derwent.co.uk}) made the following
post to \texttt{sci.math} \cite{bibref:n:scimathnewsgroup}:

\begin{quote}
{I've got a little problem which is bugging me, perhaps someone out there
can point me in the right direction \ldots{}}

{Does there exist a positive integer which is a power of 2, whose digits can
be rearranged to give a different power of 2?}
\end{quote}

David G. Radcliffe \cite{bibref:i:davidgradcliffe}
responded with a beautiful proof, which is presented below
as a theorem.

\begin{vworktheoremstatement}
No radix-10 positive integral power of 2 (i.e. 1, 2, 4, 8, 16, 32, etc.), with
any leading 0's removed, can be used
to form another radix-10 positive integral power of 2 by simple rearrangement
of the digits.
\end{vworktheoremstatement}
\begin{vworktheoremproof}
Suppose that $x$ and $y$ are two different powers of 2, $y>x$, and that
the digits of $x$ can be rearranged to form $y$.  $y<10x$, since both
$x$ and $y$ must have the same number of digits.  Thus, there
are three possibilities, $y=2x$, $y=4x$, or $y=8x$.

Since $x$ and $y$ have the same digits, but in a different order,
the sum of the digits of $x$ is equal to the sum of the digits of $y$.
It follows that $y-x$ is divisible by 9.  (This follows because
the sum of the digits of an integer $i$, summing the intermediate
sums as many times as necessary to yield a single-digit result,
yield either 9 implying that $i \; mod \; 9 = 0$, or yielding $i \; mod \; 9$.
If the digits of $x$ and $y$ are the same,
the sums of their digits are the same, thus $(x \; mod \; 9) = (y \; mod \; 9)$,
which implies that $((y-x) \; mod \; 9) = 0$, i.e. that $y-x$ is divisible
by 9.)

If $y \in \{ 2x, 4x, 8x \}$, then $y-x \in \{ x, 3x, 7x \}$.  It would
follow that $x$ is divisible by 3, a contradiction.
\end{vworktheoremproof}
\vworktheoremfooter{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Pigeonhole Principle}
\label{cmtn0:sphp0}

The \index{pigeonhole principle}\emph{pigeonhole principle} is a statement 
that if $m$ items are placed into $n$ slots, with $m > n$, then at least one
slot will contain more than one item.  This is also known as
\index{Dirichlet's box principle}\emph{Dirichlet's box principle}.

A related statement is that $m$ items are placed into $n$ slots, 
with $m < n$, then at least one
slot will be empty.

Despite its simplicity, the pigeonhole principle is the basis for many important
proofs and observations in number theory.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Exercises}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent\begin{figure}[!b]
\noindent\rule[-0.25in]{\textwidth}{1pt}
\begin{tiny}
\begin{verbatim}
$HeadURL$
$Revision$
$Date$
$Author$
\end{verbatim}
\end{tiny}
\noindent\rule[0.25in]{\textwidth}{1pt}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%End of file C_MTN0.TEX
1	dashley	140	%$Header$
2
3			\chapter[\cmtnzeroshorttitle{}]{\cmtnzerolongtitle{}}
4
5			\label{cmtn0}
6
7			\beginchapterquote{``If intellectual curiosity, professional pride, and ambition are
8			the dominant incentives to research, then assuredly no one has
9			a fairer chance of gratifying them than a mathematician. His
10			subject is the most curious of all---there is none in which
11			truth plays such odd pranks. It has the most elaborate
12			and the most fascinating technique, and gives unrivaled
13			openings for the display of sheer professional skill. Finally,
14			as history proves abundantly, mathematical achievement, whatever
15			its intrinsic worth, is the most enduring
16			of all.''}
17			{G.H. Hardy \cite{bibref:b:mathematiciansapology:1940}}
18
19			\section{Introduction}
20			%Section Tag: INT0
21			\label{cmtn0:sint0}
22
23
24			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
25			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
26			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
27
28			\index{floor function@floor function ($\lfloor\cdot\rfloor$)}%
29			\index{--@$\lfloor\cdot\rfloor$ (\emph{floor($\cdot$)} function)}%
30			\index{ceiling function@ceiling function ($\lceil\cdot\rceil$)}%
31			\index{--@$\lceil\cdot\rceil$ (\emph{ceiling($\cdot$)} function)}%
32			\section{The Floor \mbox{\boldmath $\lfloor\cdot\rfloor$} And Ceiling \mbox{\boldmath $\lceil\cdot\rceil$} Functions}
33			\label{cmtn0:sfcf0}
34
35			The \emph{floor} function, denoted $\lfloor\cdot\rfloor$, is defined to return
36			the largest integer not larger than the argument. For example,
37			$\lfloor 3 \rfloor = \lfloor 3.9999 \rfloor = 3$. For negative arguments, the definition
38			is identical: $\lfloor -4 \rfloor = \lfloor -3.9 \rfloor = -4$.
39
40			The \emph{ceiling} function, denoted $\lceil\cdot\rceil$, is defined to return
41			the smallest integer not less than the argument. For example,
42			$\lceil 3.0001 \rceil = \lceil 4 \rceil = 4$. For negative arguments, the definition
43			is identical: $\lceil -4 \rceil = \lceil -4.9 \rceil = -4$.
44
45			Note that the definitions presented above for negative arguments
46			differ from what is commonly implemented in spreadsheet software and other consumer
47			software.
48
49			It can be verfied easily that for
50			$a \in \vworkintsetnonneg$, $b \in \vworkintsetpos$,
51
52			\begin{equation}
53			\label{eq:cmtn0:sfcf0:01}
54			\frac{a}{b} = \left\lfloor\frac{a}{b}\right\rfloor + \frac{a \bmod b}{b}
55			\end{equation}
56
57			\noindent{}and consequently that
58
59			\begin{equation}
60			\label{eq:cmtn0:sfcf0:02}
61			\left\lfloor\frac{a}{b}\right\rfloor = \frac{a}{b} - \frac{a \bmod b}{b} .
62			\end{equation}
63
64			\noindent{}(\ref{eq:cmtn0:sfcf0:02}) is a very useful identity for
65			decomposing expressions involving the \emph{floor($\cdot$)} function.
66
67			\section{Tests For Divisibility Of Integers}
68			%Section Tag: TDI0
69
70			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
71			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
72			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
73			\subsection{Tests For Divisibility By 2, 3, 5, 6, 7, And 11}
74
75			It is often useful to be able to inspect a radix-10 integer and quickly
76			determine if it can be divided by a small prime number. This section
77			presents tests which can be used to easily determine divisibility by
78			2, 3, 5, 7, and 11.
79
80			Placeholder\index{divisibility tests for integers!by 0002@by 2}
81			reserved for divisibility by 2.
82
83			Placeholder\index{divisibility tests for integers!by 0003@by 3}
84			reserved for divisibility by 3.
85
86			Placeholder\index{divisibility tests for integers!by 0005@by 5}
87			reserved for divisibility by 5.
88
89			Placeholder\index{divisibility tests for integers!by 0007@by 7}
90			reserved for divisibility by 7.
91
92			Placeholder\index{divisibility tests for integers!by 0011@by 11}
93			reserved for divisibility by 11.
94
95
96			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
97			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
98			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
99			\subsection{Tests For Divisibility By 2$^N$, 6, 9, And 10$^N$}
100
101			Placeholder\index{divisibility tests for integers!by 0002N@by 2$^N$}
102			reserved for divisibility by 2$^N$.
103
104			Placeholder\index{divisibility tests for integers!by 0006@by 6}
105			reserved for divisibility by 6.
106
107			Placeholder\index{divisibility tests for integers!by 0009@by 9}
108			reserved for divisibility by 9.
109
110			Placeholder\index{divisibility tests for integers!by 0010N@by 10$^N$}
111			reserved for divisibility by 10$^N$.
112
113
114			\subsection{David G. Radcliffe's Proof: Rearrangement Of Digits Of $2^N$}
115			%Subsection Tag: DGR0
116
117			In 07/00, Paul Harvey (\texttt{pharvey@derwent.co.uk}) made the following
118			post to \texttt{sci.math} \cite{bibref:n:scimathnewsgroup}:
119
120			\begin{quote}
121			{I've got a little problem which is bugging me, perhaps someone out there
122			can point me in the right direction \ldots{}}
123
124			{Does there exist a positive integer which is a power of 2, whose digits can
125			be rearranged to give a different power of 2?}
126			\end{quote}
127
128			David G. Radcliffe \cite{bibref:i:davidgradcliffe}
129			responded with a beautiful proof, which is presented below
130			as a theorem.
131
132			\begin{vworktheoremstatement}
133			No radix-10 positive integral power of 2 (i.e. 1, 2, 4, 8, 16, 32, etc.), with
134			any leading 0's removed, can be used
135			to form another radix-10 positive integral power of 2 by simple rearrangement
136			of the digits.
137			\end{vworktheoremstatement}
138			\begin{vworktheoremproof}
139			Suppose that $x$ and $y$ are two different powers of 2, $y>x$, and that
140			the digits of $x$ can be rearranged to form $y$. $y<10x$, since both
141			$x$ and $y$ must have the same number of digits. Thus, there
142			are three possibilities, $y=2x$, $y=4x$, or $y=8x$.
143
144			Since $x$ and $y$ have the same digits, but in a different order,
145			the sum of the digits of $x$ is equal to the sum of the digits of $y$.
146			It follows that $y-x$ is divisible by 9. (This follows because
147			the sum of the digits of an integer $i$, summing the intermediate
148			sums as many times as necessary to yield a single-digit result,
149			yield either 9 implying that $i \; mod \; 9 = 0$, or yielding $i \; mod \; 9$.
150			If the digits of $x$ and $y$ are the same,
151			the sums of their digits are the same, thus $(x \; mod \; 9) = (y \; mod \; 9)$,
152			which implies that $((y-x) \; mod \; 9) = 0$, i.e. that $y-x$ is divisible
153			by 9.)
154
155			If $y \in \{ 2x, 4x, 8x \}$, then $y-x \in \{ x, 3x, 7x \}$. It would
156			follow that $x$ is divisible by 3, a contradiction.
157			\end{vworktheoremproof}
158			\vworktheoremfooter{}
159
160			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
161			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
162			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
163			\section{The Pigeonhole Principle}
164			\label{cmtn0:sphp0}
165
166			The \index{pigeonhole principle}\emph{pigeonhole principle} is a statement
167			that if $m$ items are placed into $n$ slots, with $m > n$, then at least one
168			slot will contain more than one item. This is also known as
169			\index{Dirichlet's box principle}\emph{Dirichlet's box principle}.
170
171			A related statement is that $m$ items are placed into $n$ slots,
172			with $m < n$, then at least one
173			slot will be empty.
174
175			Despite its simplicity, the pigeonhole principle is the basis for many important
176			proofs and observations in number theory.
177
178
179			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
180			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
181			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
182			\section{Exercises}
183
184
185			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
186
187			\noindent\begin{figure}[!b]
188			\noindent\rule[-0.25in]{\textwidth}{1pt}
189			\begin{tiny}
190			\begin{verbatim}
191	dashley	278	$HeadURL$
192			$Revision$
193			$Date$
194			$Author$
195	dashley	140	\end{verbatim}
196			\end{tiny}
197			\noindent\rule[0.25in]{\textwidth}{1pt}
198			\end{figure}
199
200			%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
201			%
202			%End of file C_MTN0.TEX
Name	Value
svn:eol-style	native
svn:keywords	Author Date Id Revision URL Header