About the Author
Hans Rademacher was an Affiliate of Rockefeller University and Professor Emeritus of Mathematics in the University of Pennsylvania before his death in 1969. Otto Toeplitz was Professor of Mathematics in Kiel and Bonn.
Read an Excerpt
The Enjoyment of Math
By Hans Rademacher, Otto Toeplitz, Herbert Zuckerman
PRINCETON UNIVERSITY PRESSCopyright © 1957 Princeton University Press
All rights reserved.
The Sequence of Prime Numbers
6 is equal to 2 times 3, but 7 cannot be similarly written as a product of factors. Therefore 7 is called a prime or prime number. A prime is a positive whole number which cannot be written as the product of two smaller factors. 5 and 3 are primes but 4 and 12 are not since we have 4 = 2 x 2 and 12 = 3 x 4. Numbers which can be factored like 4 and 12 are called composite. The number 1 is not composite but, because it behaves so differently from other numbers, it is not usually considered a prime either; consequently 2 is the first prime, and the first few primes are:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ··· .
A glance reveals that this sequence does not follow any simple law and, in fact, the structure of the sequence of primes turns out to be extremely complicated.
A number can be factored a step at a time until it is reduced to a product of primes. Thus 6 = 2 · 3 is immediately expressed as a product of two primes, while 30 = 5 · 6 and 6 = 2 · 3 gives 30 = 2 · 3 · 5, a product of three primes. Similarly, 24 has four prime factors (24 = 3 · 8 = 3 · 2 · 4 = 3 · 2 · 2 · 2), of which three happen to be the same prime, 2. In the case of a prime such as 5 one can only write 5 = 5, a product of a single prime. By means of this step-by-step factoring, any positive whole number except 1 can be written as a product of primes. Because of this, the prime numbers can be thought of as the building blocks of the sequence of all positive whole numbers.
In the ninth book of Euclid's Elements the question of whether the sequence of primes eventually ends is raised and answered. It is shown that the sequence has no end, that after each prime yet another and larger prime can be found.
Euclid's proof is very ingenious yet quite simple. The numbers 3, 6, 9, 12, 15, 18, ··· are all multiples of 3. No other numbers can be divided evenly by 3. The next larger numbers 4, 7, 10, 13, 16, 19, ···, which are multiples of 3 increased by 1, are certainly not divisible by 3; for example, 19 = 6 · 3 + 1, 22 = 7 · 3 + 1, etc. In the same way the multiples of 5 increased by 1 are not divisible by 5 (21 = 4 · 5 + 1, etc.). The same thing is true for 7, for 11, and so on.
Now Euclid writes down the numbers
2 · 3 + 1 = 7
2 · 3 · 5 + 1 = 31
2 · 3 · 5 · 7 + 1 = 211
2 · 3 · 5 · 7 · 11 + 1 = 2311
2 · 3 · 5 · 7 · 11 · 13 + 1 = 30,031, etc.
The first two primes, the first three primes, and so forth, are multiplied together and each product is increased by 1. None of these numbers is divisible by any of the primes used to form it. Since 31 is a multiple of 2 increased by 1, it is not divisible by 2. It is a multiple of 3 increased by 1 and hence is not divisible by 3. It is a multiple of 5 increased by 1, hence not divisible by 5. 31 happens to be a prime and it is certainly larger than 5. 211 and 2311 are also new primes, but 30031 is not a prime. However, 30031 is not divisible by 2, 3, 5, 7, 11, or 13, and hence its prime factors are greater than 13. As a matter of fact, a little figuring shows that 30031 = 59 · 509, and these prime factors are greater than 13.
The same argument may be applied as far as one wants to go. Let p be any prime and form the product of all primes from 2 to p; increase this product by 1 and write
2 · 3 · 5 · 7 · 11 ··· p + 1 = N.
None of the primes 2, 3, 5, ··· p divides N, so either N is a prime (certainly much greater than p) or all the prime factors of N are different from 2, 3, 5, ··· p, and hence greater than p. In either case, a new prime greater than p has been found. No matter how large p is there is always another larger prime.
This part of Euclid is quite remarkable, and it would be hard to name its most admirable feature. The problem itself is only of theoretical interest. It can be proposed, for its own sake, only by a person who has a certain inner feeling for mathematical thought. This feeling for mathematics and appreciation of the beauty of mathematics was very evident in the ancient Greeks, and they have handed it down to later civilizations. Also, this problem is one that most people would completely overlook. Even when it is brought to our attention it appears to be trivial and superfluous, and its real difficulties are not immediately apparent. Finally, we must admire the ingenious and simple way in which Euclid proves the theorem. The most natural way to try to prove the theorem is not Euclid's. It would be more natural to try to find the next prime number following any given prime. This has been attempted but has always ended in failure because of the extreme irregularity of the formation of the primes.
Euclid's proof circumvents the lack of a law of formation for the sequence of primes by looking for some prime beyond instead of for the next prime after p. For example, his proof gives 2311, not 13, as a prime past 11, and it gives 59 as one past 13. Frequently there are a great many primes between the one considered and the one given by the proof. This is not a sign of the weakness of the proof, but rather it is evidence of the ingenuity of the Greeks in that they did not try to do more than was required.
As an illustration of the complexity of the sequence of primes, we shall show that there are large gaps in the series. We shall show, for example, that we can find 1000 consecutive numbers, all of which are composite. The method is closely related to that of Euclid.
We saw that 2 · 3 · 5 + 1 = 31 is not divisible by 2, 3, or 5. If two numbers are divisible by 2 then their sum is certainly divisible by 2 as well. The same is true for 3, 5, etc. Now, 2 · 3 · 5 is divisible by 2, 3, and 5, so 2 · 3 · 5 + 2 = 32 is divisible by 2, 2 · 3 · 5 + 3 = 33 by 3, 2 · 3 · 5 + 4 = 34 by 2, 2 · 3 · 5 + 5 = 35 by 5, and 2 · 3 · 5 + 6 = 36 by 2. Therefore none of the numbers 32, 33, 34, 35, 36 is a prime. This argument fails for the first time for 2 · 3 · 5 + 7 = 37, which is not divisible by 2, 3, or 5.
In the same way we can find 1000 consecutive composite numbers. Let p be the first four digit prime (1009) and form the 1000 numbers
2 · 3 ··· p + 2, 2 · 3 ··· p + 3 ···, 2 x 3 ··· p + 1001.
Each of the numbers 2, 3, 4, 5, ···, 1001, is divisible by one of the primes 2, 3, ···, p and so is 2 x 3 ··· p. Therefore each of the numbers listed is also divisible by one of 2, 3, ··· p, and hence is not a prime itself. We have thus found 1000 consecutive numbers none of which is prime, and consequently there is a gap of at least 1000 numbers in the sequence of primes.
Naturally a gap of such length will not occur until we have gone quite far along in the sequence of primes, but if we go far enough we can, by the same method, find gaps as long as we may desire.
This problem and Euclid's are very similar both in nature and proof, yet the question of gaps in the sequence of primes was not considered by the Greeks. It was taken up by modern mathematicians along with a great number of other related problems. Most of these other problems are not as easy to solve; some remain unsolved at the present time, while others have led to entirely new fields of mathematics.
Let us consider one of these further problems which we can still handle by the same methods and which will give a certain insight into some of the others. The multiples of 3 are 3, 6, 9, ···, and these numbers increased by 1 viz. 4, 7, 10, ··· have occurred above. The remaining numbers 2, 5, 8, 11, 14, 17, 20, 23, ··· are the numbers which have the remainder 2 when divided by 3. Do these last numbers contain infinitely many primes? That is, does the sequence 2, 5, 11, 17, 23, ··· never end? We shall prove that there is an infinite number of these primes.
First we must show that if any two of the numbers 1, 4, 7, 10, 13, ··· are multiplied together, the product is again one of these same numbers. Each of the numbers is a multiple of 3 increased by 1, say 3x + 1. If a second number is 3y + 1, then their product is
(1) (3x + 1) (3y + 1) = 9xy + 3y + 3x + 1 = 3(3xy + y + x) + 1,
which is again a multiple of 3 increased by 1 and hence is in our original set of numbers.
Now if any of the numbers 2, 5, 8, 11, ··· is split into its prime factors, at least one of the prime factors must again be one of 2, 5, 8, 11, ···. For example, 14 = 2 · 7 has the factor 2 and 35 = 5 · 7 has 5. To show that this is always true, we note that each of the prime factors must be either a multiple of 3, in the sequence 1, 4, 7, 10, ···, or in the sequence 2, 5, 8, ···. The only multiple of 3 that is a prime is 3 itself, and it does not divide our chosen number. If all the prime factors were of the kind 1, 4, 7, 10, ···, then by the above remark (1) our number would again be of this kind. Since it is not of this kind, at least one of its prime factors must be one of the kind 2, 5, 8, 11, ···.
We can now proceed as in Euclid's proof except that we consider
2 · 3 · 5 · 7 · 11 ··· p - 1 = M
in place of
2 · 3 · 5 · 7 · 11 ··· p + 1 = N.
M is a multiple of 3 decreased by 1, which means that it is one of 2, 5, 8, 11, ···. Just as with N, it is clear that M is not divisible by any of the primes 2, 3, 5, 7, 11, ···, p. Either M is a prime (greater than p), or all its prime factors are greater than p. In the latter case at least one of the prime factors is one of 2, 5, 8, ···, and hence in both cases we have found a prime of this kind that is greater than p. Therefore the sequence 2, 5, 8, ··· contains an infinite number of primes.
This leaves open the question whether the sequence 1, 4, 7, 10, 13, ··· contains an infinite number of primes. It is quite possible that 2, 5, 8, ··· could contain infinitely many primes while 1, 4, 7, ··· contained only a finite number. The fact is that the latter sequence also contains infinitely many primes, but the proof of this requires completely different methods. In a later chapter we shall gain some insight into these methods. The reason for mentioning these last problems was to point out how the problems and methods of modern mathematics are related to those of the Greeks. This is not only true in isolated cases, but in whole areas of modern mathematics, areas of very great interest in which research is still being carried on.
2. Traversing Nets of Curves
A streetcar company decides to reorganize its system of routes without changing the existing tracks. It wishes to do this in such a way that each section of track will be used by just one route. Passengers will be allowed to transfer from route to route until they finally reach their destinations. The problem is: how many routes must the company operate in order to serve all sections without having more than one route on any section?
For a very small city with car lines as in Fig. 1, the problem is quite simple. One route could go from A to B and a second from C to D, both passing through K. Or a line could go from A through K to D and a second from B through K to C. Finally, a line could go from A through K to C and another from B through K to D. Each of these possibilities necessitates two routes. Of course the company could set up a new transfer point at R, end a route there, and run a shuttle from R to B. But this would only increase the total number of routes needed. By adding more transfer points the number of routes could be increased indefinitely, but we are not interested in doing this, since the original problem asks for the smallest possible number of routes.
Fig. 2 is still a fairly simple network of lines, but the problem is more complicated in this case. One possibility is for one route to run from A around through B, C, D, E, and back to A (a closed route). A second route might go from A through F, G, H, to D. Three more routes, BF, EG, CH, would be needed, making five in all. However, this is not the best possible arrangement. The first two routes could be combined into a single one running from A around through B, C, D, E, and back to A, and then on through F, G, and H to D. This cuts the number of routes to four, but would it be possible to set up just three routes?
In the network of Fig. 3 one route might proceed from A through B, C, D, and E, back to A, and then on through F to B. That would leave three sections, CF, DF, EF, of which two could be combined into a single route CFD, leaving EF as a route by itself. In this case the first two routes pass through F while the third ends at F. The question still remains: would two routes do just as well?
It would not be unduly difficult to list all the possible routes for Figs. 2 and 3 (as we did for Fig. 1) in order to be sure we have the minimum number of routes. However, this would be quite a long procedure for a fairly complicated network, and in any case it would not be a very interesting problem. Also, it would no more be mathematics merely to list all the possibilities for any given network than it is mathematics to multiply together two seven-digit numbers. The spirit of mathematics dictates that we seek out the essentials of the problem and use them to solve it.
The essential thing in this problem is quite simple. We must consider where the ends of the various routes must lie. There must be an end wherever a section has a free end as at A, B, C, and D in Fig. I. Since in this case there must be four ends, and since each route has no more than two ends (a closed route has no ends of course), it is clear that there must be at least two routes between these four ends. By means of a single consideration we have obtained the same result as was obtained above by considering all the possible cases.
In Fig. 2 there are no free ends, but here there are places such as A where three sections come together. At such a place at least one route must end, since two routes can never be on the same section. In Fig. 2 there are eight places of this kind, so there must be at least eight ends of routes. Eight is an even number, the number of ends of four routes. Therefore there must be at least four routes; and, as we have already seen, four routes will do.
In Fig. 3 there are five junctions of the kind we have been discussing, and a sixth point F where not three but five sections come together. We shall call a point like F a junction of the fifth order. At F two pairs of sections might be joined to form routes, leaving one over, as was done in the first discussion of Fig. 3. The same thing would be true for any junction of odd order; one section is always left over, and hence there must be at least one end there. We now see that Fig. 3 requires at least six ends (an even number) and hence at least three routes.
For any network, no matter how complicated, we can easily count the junctions of odd order and divide by 2 to obtain the least possible number of routes. In the three examples so far, the number of junctions of odd order was always even, and it turned out that half this number of routes was not only necessary but also sufficient to meet the requirements of the problem. We would now like to determine whether or not the number of junctions of odd order is always even, and whether half this number of routes will always do for any given network.
Excerpted from The Enjoyment of Math by Hans Rademacher, Otto Toeplitz, Herbert Zuckerman. Copyright © 1957 Princeton University Press. Excerpted by permission of PRINCETON UNIVERSITY PRESS.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
Table of Contents
|1.||The Sequence of Prime Numbers||9|
|2.||Traversing Nets of Curves||13|
|3.||Some Maximum Problems||17|
|4.||Incommensurable Segments and Irrational Numbers||22|
|5.||A Minimum Property of the Pedal Triangle||27|
|6.||A Second Proof of the Same Minimum Property||30|
|7.||The Theory of Sets||34|
|8.||Some Combinatorial Problems||43|
|9.||On Waring's Problem||52|
|10.||On Closed Self-Intersecting Curves||61|
|11.||Is the Factorization of a Number into Prime Factors Unique?||66|
|12.||The Four-Color Problem||73|
|13.||The Regular Polyhedrons||82|
|14.||Pythagorean Numbers and Fermat's Theorem||88|
|15.||The Theorem of the Arithmetic and Geometric Means||95|
|16.||The Spanning Circle of a Finite Set of Points||103|
|17.||Approximating Irrational Numbers by Means of Rational Numbers||111|
|18.||Producing Rectilinear Motion by Means of Linkages||119|
|20.||Euler's Proof of the Infinitude of the Prime Numbers||135|
|21.||Fundamental Principles of Maximum Problems||139|
|22.||The Figure of Greatest Area with a Given Perimeter||142|
|23.||Periodic Decimal Fractions||147|
|24.||A Characteristic Property of the Circle||160|
|25.||Curves of Constant Breadth||163|
|26.||The Indispensability of the Compass for the Constructions of Elementary Geometry||177|
|27.||A Property of the Number 30||187|
|28.||An Improved Inequality||192|
|Notes and Remarks||197|