%$Header: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_mtn0/c_mtn0.tex,v 1.4 2002/12/01 21:29:08 dtashley Exp $

\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}
$RCSfile: c_mtn0.tex,v $
$Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_mtn0/c_mtn0.tex,v $
$Revision: 1.4 $
$Author: dtashley $
$Date: 2002/12/01 21:29:08 $
\end{verbatim}
\end{tiny}
\noindent\rule[0.25in]{\textwidth}{1pt}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% $Log: c_mtn0.tex,v $
% Revision 1.4  2002/12/01 21:29:08  dtashley
% Safety checkin.
%
% Revision 1.3  2002/07/31 04:37:50  dtashley
% Number theory chapter title changed, some material added.
%
% Revision 1.2  2001/07/01 19:43:13  dtashley
% Move out of binary mode for use with CVS.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% $History: c_mtn0.tex $
% 
% *****************  Version 3  *****************
% User: Dashley1     Date: 12/22/00   Time: 12:56a
% Updated in $/uC Software Multi-Volume Book (A)/Chapter, MTN0, Miscellaneous Topics From Number Theory
% Tcl automated method of build refined.
% 
% *****************  Version 2  *****************
% User: David T. Ashley Date: 7/29/00    Time: 11:49p
% Updated in $/uC Software Multi-Volume Book (A)/Chapter, MTN0, Miscellaneous Topics From Number Theory
% Edits, addition of solutions manual volume.
%
% *****************  Version 1  *****************
% User: David T. Ashley Date: 7/29/00    Time: 9:34p
% Created in $/uC Software Multi-Volume Book (A)/Chapter, MTN0, Miscellaneous Topics From Number Theory
% Initial check-in.
%
%End of file C_MTN0.TEX