%$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$, $$\label{eq:cmtn0:sfcf0:01} \frac{a}{b} = \left\lfloor\frac{a}{b}\right\rfloor + \frac{a \bmod b}{b}$$ \noindent{}and consequently that $$\label{eq:cmtn0:sfcf0:02} \left\lfloor\frac{a}{b}\right\rfloor = \frac{a}{b} - \frac{a \bmod b}{b} .$$ \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