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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 278 - (show annotations) (download) (as text)
Wed Aug 14 23:10:36 2019 UTC (4 years, 1 month ago) by dashley
File MIME type: application/x-tex
File size: 8152 byte(s)
Change keyword substitution (migration from cvs to svn).
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

Properties

Name Value
svn:eol-style native
svn:keywords Author Date Id Revision URL Header

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25