/[dtapublic]/pubs/books/ucbka/trunk/c_mtn0/c_mtn0.tex
ViewVC logotype

Annotation of /pubs/books/ucbka/trunk/c_mtn0/c_mtn0.tex

Parent Directory Parent Directory | Revision Log Revision Log


Revision 6 - (hide annotations) (download) (as text)
Fri Oct 7 01:36:46 2016 UTC (8 years, 1 month ago) by dashley
File MIME type: application/x-tex
File size: 9777 byte(s)
Initial commit after migrating from CVS.
1 dashley 6 %$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 $
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     $RCSfile: c_mtn0.tex,v $
192     $Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_mtn0/c_mtn0.tex,v $
193     $Revision: 1.4 $
194     $Author: dtashley $
195     $Date: 2002/12/01 21:29:08 $
196     \end{verbatim}
197     \end{tiny}
198     \noindent\rule[0.25in]{\textwidth}{1pt}
199     \end{figure}
200    
201     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
202     % $Log: c_mtn0.tex,v $
203     % Revision 1.4 2002/12/01 21:29:08 dtashley
204     % Safety checkin.
205     %
206     % Revision 1.3 2002/07/31 04:37:50 dtashley
207     % Number theory chapter title changed, some material added.
208     %
209     % Revision 1.2 2001/07/01 19:43:13 dtashley
210     % Move out of binary mode for use with CVS.
211     %
212     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
213     % $History: c_mtn0.tex $
214     %
215     % ***************** Version 3 *****************
216     % User: Dashley1 Date: 12/22/00 Time: 12:56a
217     % Updated in $/uC Software Multi-Volume Book (A)/Chapter, MTN0, Miscellaneous Topics From Number Theory
218     % Tcl automated method of build refined.
219     %
220     % ***************** Version 2 *****************
221     % User: David T. Ashley Date: 7/29/00 Time: 11:49p
222     % Updated in $/uC Software Multi-Volume Book (A)/Chapter, MTN0, Miscellaneous Topics From Number Theory
223     % Edits, addition of solutions manual volume.
224     %
225     % ***************** Version 1 *****************
226     % User: David T. Ashley Date: 7/29/00 Time: 9:34p
227     % Created in $/uC Software Multi-Volume Book (A)/Chapter, MTN0, Miscellaneous Topics From Number Theory
228     % Initial check-in.
229     %
230     %End of file C_MTN0.TEX

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25