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	%$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	$HeadURL$
192	$Revision$
193	$Date$
194	$Author$
195	\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