Parent Directory | Revision Log

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

*Fri Oct 7 01:36:46 2016 UTC*
(7 years, 10 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 | %$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 |