Parent Directory | Revision Log

Revision **6** -
(**hide annotations**)
(**download**)
(**as text**)

*Fri Oct 7 01:36:46 2016 UTC*
(6 years, 11 months ago)
by *dashley*

File MIME type: application/x-tex

File size: 9777 byte(s)

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 |