Biscuits of Number Theory
Cover illustration by Gregory Nemec Cover design by Carole Goodman, Freedom by Design O 2009 by The Mathematical Association of America (Incorporated) Library of Congress Catalog Card Number 20089391 07 ISBN 9780883853405 Printed in the United States of America Current Printing (last digit) 1 0 9 8 7 6 5 4 3 2 1
The Dolciani Mathematical Expositions
NUMBER THIRTYFOUR
Biscuits of Number Theory Edited by
Arthur T. Benjamin and Ezra Brown
Published and Distributed by The Mathematical Association of America
DOLCIANI MATHEMATICAL EXPOSITIONS Council on Publications Paul Zorn, Chair Dolciani Mathematical Expositions Editorial Board Undenvood Dudley, Editor Jeremy S. Case Tevian Dray Robert L. Devaney Jerrold W. Grossman Virginia E. Knight Mark A. Peterson Jonathan Rogness Joe Alyn Stickles James S. Tanton
The DOLCIANI MATHEMATICAL EXPOSITIONS series of the Mathematical Association of America was established through a generous gift to the Association from Maiy P. Dolciani, Professor of Mathematics at Hunter College of the City University of New York. In making the gift, Professor Dolciani, herself an exceptionally talented and successful expositor of mathematics, had the purpose of furthering the ideal of excellence in mathematical exposition. The Association, for its part, was delighted to accept the gracious gesture initiating the revolving fund for this series from one who has served the Association with distinction, both as a member of the Committee on Publications and as a inember of the Board of Governors. It was with genuine pleasure that tlie Board chose to naine the series in her honor. The books in the series are selected for their lucid expository style and stimulating mathematical content. Typically, they contain an ample supply of exercises, many with accompanying solutions. They are intended to be sufficiently elementary for the undergraduate and even the mathematically inclined highschool student to understand and enjoy, but also to be interesting and sometimes challenging to the more advanced mathematician. 1. Mathematical Gems, Ross Honsberger 2. Mathematical Gems 11, Ross Honsberger 3. Mathematical Morsels, Ross Honsberger
4. Mathematical Plums, Ross Honsberger (ed.) 5. Great Moments in Mathematics (Before 1650), Howard Eves 6. Mmima and Minima without Calculus, Ivan Niven 7. Great Moments in Mathematics (Afer 1650), Howard Eves 8. Map Coloring, Polyhedra, and the FourColor Problem, David Barnette 9. Mathematical Gems 111, Ross Honsberger 10. More Mathematical Morsels, Ross Honsberger 11. Old and New Unsolved Problems in Plane Geometry and Number Theory, Victor Klee and Stan Wagon 12. Problems for Mathematicians, Young and Old, Paul R. Halmos 13. Excursions in Calculus: An Interplay of the Continuou,~and the Discrete, Robert M. Young 14. The Wohascum County Problem Book, George T. Gilbert, Mark Ihsemeyer, and Loren C. Larson 15. Lion Hunting and Other Mathematical Pursuits: A Collection of Mathematics, Erse, and Stories by Ralph P Boas, Jz, edited by Gerald L. Alexanderson and Dale H. Mugler 16. Linear Algebra Problem Book, Paul R. Halmos 17. From Erdos to Kiev: Problems of Olympiad Caliber, Ross Honsberger 18. Which Way Did the Bicycle Go? ... and Other Intriguing Mathematical Mysteries, Joseph D. E. Konhauser, Dan Velleman and Stan Wagon 19. In PóSa S' Footsteps: Miscellaneous Problems and Essays, Ross Honsberger u s Diophantine Eguations, 1. G. Bashmakova (Updated by Joseph Silverman 20. ~ i o ~ h a n t and and translated by Abe Shenitzer) 2 1. Logic as Algebra, Paul Halmos and,Steven Givant 22. Euler: The Master of Us All, William Dunham 23. The Beginning and Evolution ofAlgebra, 1. G. Bashrnaltova and G. S. Smirnova (Translated by Abe Shenitzer) 24. Mathematical Chesnutsfrom Around the World, Ross Honsberger 25. Counting on Frameworks: Mathematics to Aid the Design of Rigid Structures, Jack E. Graver
26. Mathematical Diamonds, Ross Honsberger
27. Proofs that Really Count: The Art of Combinatorial ProoJ;Arthur T. Benjamin and Jennifer J. Quinn 28. Mathematical Delights, Ross Honsberger 29. Conics, Keith Kendig 30. Hesiod's Anvil: faMing and spinning through heaven and earth, Andrew J. Simoson 3 1. A Garden of Integrals, Frank E. Burk 32. A Guide to Complex Yariables (MAA Guides #1), Steven G. Krantz
33. Sink or Float? Thought Pro blems in Math and Physics, Keith Kendig 34. Biscuits of Number Theory, edited by Arthur T. Benjamin and Ezra Brown
MAA Service Center P. O. Box 91112 Washington, DC 20090 1112 18003311MAA FAX: 13012069789
Contents Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Part 1: Arithmetic l. A Dozen Questions About the Powers of Two . . . . . . . . . . . . . . . . . . . . . . . . . James Tanton. Math Horizons, vol. 8, no. 1 (September 2001), pp. 510; 2002 Trevor Evans Award.
2. From 30 to 60 is Not Twice as Hard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Michael Dalezman. Mathematics Magazine, vol, 73, no. 2 (April2000), pp. 151153.
3. Reducing the Sum of Two Fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Harris S. Shultz and Ray C. Shiflett. Mathematics Teacher, vol. 98, no. 7 (March 2005), pp. 486490.
4. A Postmodern View of Fractions and Reciprocals of Fermat Primes . . . . Rafe Jones and Jan Pearce. Mathematics Magazine, vol. 73, no. 2 (April2000), pp. 8397; 2001 Allendoerfer Award.
5. Visible Structures in Number Theory Peter Bonvein and Loki Jorgenson.
..............................
American Mathematical Monthly, vol. 108, no. 10 (December 2001), pp. 89791 0; 2002 Lester Ford Award.
6. Visual Gems of Number Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Roger B. Nelsen. Math Horizons, vol. 15, no. 3 (February 2008), pp. 79,31.
Part 11: Primes 7. A New Proof of Euclid's Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Filip Saidak. American Mathematical Monthly, vol. 113, no. 10 (December 2006), pp. 937938.
8. On the Infinitude of the Primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Harry Furstenberg. American Mathematical Monthly, vol. 62, no. 5 (May 1955), p. 353.
9. On the Series of Prime Reciprocals Ja.mesA. Clarltson.
................................
Proceedings of the AMS, vol. 17, no. 2 (April 1966), p. 541.
10. Applications of a Simple Counting Technique Melvin Hausner.
......................
American Mathematical Monthly; vol. 90, no. 2 (February 1983), pp. 127129.
11. On Weird and Pseudoperfect Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . S. J. Benltoslti and P. Erdds. Mathematics of Computation, vol. 28, no. 126 (April 1974), pp. 617623.
12. A Heuristic for the Prime Number Theorem . . . . . . . . . . . . . . . . . . . . . . . Hugh L. Montgromery and Stan Wagon. Mathematical Intelligencer, vol. 28, no. 3 (2006), pp. 69. vii
13. A Tale of Two Sieves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Carl Pomerance. Notices of the AMS, (December 1996), pp. 14731485; 2001 Conant Prize.
105
Part 111: Irrationality and Continued Fractions 14. Irrationality of the Square Root of TwoA Tom M. Apostol.
Geometric Proof . . . . . . . . . 107
American Mathematical Monthly, vol. 107, no. 9 (November 2000), pp. 841842.
15. Math Bite: Irrationality of Harley Flanders.
&
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Mathematics Magazine, vol. 72, no. 3 (June 1999), p. 235.
16. A Simple Proof that n is Irrational . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 Ivan Niven. Bulletin of the AMS, vol. 53 (1947), p. 509.
17. n,e and Other Irrational Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 Alan E. Parlts. American Mathematical Monthly, vol. 93, no. 9 (November 1986), pp. 722723.
18. A Short Proof of the Simple Continued Fraction of e . . . . . . . . . . . . . . . . 115 Henry Cohn. American Mathematical Monthly, vol. 113, no. 1 (January 2006), pp. 5761.
19. Diophantine Olympics and World Champions: Polynomials and Primes Down Under . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 Edward B. Burger. American Mathematical Monthly, vol. 107, no. 9 (November 2000), pp. 822829; 2004 Chauvenet Prize.
20. An Elementary Proof of the Wallis Product Formula for Pi . . . . . . . . . . 129 Johan Wastlund. American Mathematical Monthly, vol. 114, no. 10 (December 2007), pp. 9 149 17.
21. The Orchard Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 Ross Honsberger. Mathematical Gems, Chapter 4, pp. 4353, Dolciani Mathematical Expositions, MAA, 1973.
Part IV Sums of Squares and Polygonal Numbers
141
22. A OneSentence Proof that every Primep 1 (mod 4) is a Sum of TwoSquares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 D. Zagier. American Mathematical Monthly, vol. 97, no. 2 (February 1990), p. 144.
23. Sum of Squares 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 Martin Gardner and Dan Kalman. Proofs Without Words: Exercises in Esual Thinking, Classroom Resource Materials, MAA, p. 78.
24. Sums of Squares VI11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 Roger B. Nelsen. Proofs Without Words 11:More Exercises in Esual Thinking, Classroom Resource Materials, MAA, p. 88.
25. A Short Proof of Cauchyls Polygonal Number Theorem . . . . . . . . . . . . Melvyn B. Nathanson. Proceedings of the AMS, vol. 99, no. 1 (January 1987), pp. 2224.
26. Genealogy of Pythagorean Triads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A. Hall. Mathematical Gazette, vol. 54, no. 390 (Deceinber 1970), pp. 377379.
Part V: Fibonacci Numbers 27. A Dozen Questions About Fibonacci Numbers . . . . . . . . . . . . . . . . . . . . . James Tanton. Math Horizons, vol. 12, no. 3 (February 2005), pp. 59.
28. The Fibonacci NumbersExposed Dan Icalman and Robert Mena.
..............................
Mathematics Magazine, vol. 76, no. 3 (June 2003), pp. 1671 8 1.
29. The Fibonacci NumbersExposed More Discretely . . . . . . . . . . . . . . . . Arthur T. Benjamin and Jennifer J. Quinn. Mathematics Magazine, vol. 76, no. 3 (June 2003), pp. 1821 92.
Part VI: NumberTheoretic Functions 38. Great Moments of the Riemann zeta Function . . . . . . . . . . . . . . . . . . . . Jennifer Beinelte and Chris Hughes. Original article. 31. The Collatz Chameleon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Marc Chamberland. Math Horizons, vol. 14, no. 2 (November 2006), pp. 58.
32. Bijecting Eulerls Partition Recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . David M. Bressoud and Doron Zeilberger. American Mathematical Monthly, vol. 92, no. 1 (January 1985),pp. 5455.
33. Discovery of a Most Extraordinary Law of the Numbers Concerning the Sum of Their Divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Leonard Euler. Translated by George Pólya. Mathematics and Plausible Reasoning, Volume 1, Princeton University Press, (1954),pp. 9098.
34. The Factorial Function and Generalizations . . . . . . . . . . . . . . . . . . . . . . Manjul Bhargava. American Mathematical Monthly, vol. 107, no. 9 (November 2000), pp. 783799; 2003 Hasse Prize.
35. An Elementary Proof of the Quadratic Reciprocity Law . . . . . . . . . . . . Sey Y. Kim. American Mathematical Monthly, vol. 11 1 , no. 1 (January 2004), pp. 4850.
Part VII: Elliptic Curves, Cubes and Fermat's Last Theorem 36. Proof Without Words: Cubes and Squares . . . . . . . . . . . . . . . . . . . . . . . J. Barry Love. Mathematics Magazine, vol. 50, no. 2 (March 1977), p. 74.
37. Taxicabs and Sums of Two Cubes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 Joseph H. Silverrnan. American Mathematical Monthly, vol. 100, no. 4 (April 1993),pp. 33 1340; 1994 Lester Ford Award.
38. Three Fermat Trails to Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 Ezra Brown. The College Mathematics Journal, vol. 3 1, no. 3 (May 2000), pp. 162172; 2001 Pólya Award.
39. Fermat's Last Theorem in Combinatorial Form . . . . . . . . . . . . . . . . . . . 285 W. V. Quine. American Mathematical Monthly, vol. 95, no. 7 (AugustSeptember 1988), p. 636.
40. "AMarvelousProof' . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fernando Q. Gouvea.
287
American Mathematical Monthly, vol. 101, no. 3 (March 1994), pp. 203222; 1995 Lester Ford Award.
About the Editors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
lntroduction
"Powdemilk Biscuits: Heavens, they're tasty and expeditious! They're made from whole wheat, to give shy persons the strength to get up and do what needs to be done."  Garrison Iceillor, A Prairie Home Companion You are probably wondering, "What exactly are biscuits of number theory?" In this book, we have an assortment of articles and notes on number theory, where each item is not too big, easily digested, and makes you feel al1 warrn and fuzzy when you're through. We hope they will whet your appetite for more! Overall, we felt that the biscuit analogy hit the spot (in addition, one of the editors bakes biscuits for his students). In this collection, we have chosen articles that we felt were exceptionally wellwritten and that could be appreciated by anyone who has taken (or is taking) a first course in number theory. This book could be used as a textboolt supplement for a number theory course, especially one that requires students to write papers or do outside reading. Here are some of the possibilities:
o
Each piece in the collection is a fine starting point for classroom discussions. After telling the Ramanujan story about sums of two cubes, an instructor can ask the class what questions this story might prompt. Students can be given a list of cubes and asked to veri@ Ramanujan7sclaim. Some of the material in Silverman's Taxicabs article can show thein how following up on an innocent little remark can lead to some quite wonderful mathematics. The articles can be used as followups to classroom presentations. For example, after introducing the Fibonacci numbers, have some students read the Tanton paper and assign one or more of the "Talting it Further" questions. Have others read the two matched "Fibonacci numbersexposed" papers and describe how they are the same and how they are different. Students who see the standard proofs ofthe infinitude ofthe primes or the Quadratic Reciprocity Law and who are curious about other proofs can be directed to the altemative proofs in this collection and encouraged to present them to the class. This could lead to students' searching for other proofs in the literature and writing them up in a paper. Students in most courses in number theory leam about Paul Erdds. Have them read Erdos' paper in this collection, worlt out the details, and present them to the class, along with a detemination (with proof) of the instructor's Erdds number. Zagier's onesentence proof of the TwoSquares Theorein gives students an opportunity to work out the details of a very short proof. In doing this, they leam the mathematics behind that proof. Another possibility is for students to present Jackson's oneline proof that every primep = 8n + 3 is of the form a2 + 2b2, and perhaps create proofs of their own for similar results. Many of the papers contain material that might give students a start on an undergraduate research project. For students who wonder how to do research in number theory, have them read
lntroduction
Pólya's translation of Euler's paper on suins of divisors, so they can see how one of the masters did it. The Arithmetic section contains articles that can give future secondaryschool teachers ideas on how to introduce their students to patterns hidden in powers of two and fractions and to pictures hidden in numbers. We have just mentioned many of the biscuits by title, but al140 of them have interesting mathematics for number theorists, young and notsoyoung. After soine of the articles, we provide "second helpings" where readers can learn about fürther developments and other topics related to the article. This project began at the MAA Northeastern Section meeting in November, 2004. Dwing a break between tallts, the two editors chatted about a possible invited paper session for MathFest 2005 in Albuquerque. Ten minutes later, we had a topic and a format: four speakers, each with a halfhour slot, would present what we called "Gems of Number Theory." A halfhour aRer that, we had a list of potential speakers who would exactly fill the bill. A few weelts later, we had our program. The large and appreciative audience at MathFest 2005 heard Marc Chamberland speak on the Collatz 3x + 1 Problem, Ed Burger on Diophantine Approximation, Jennifer Beineke on Great Moments of the Riemann zeta Function, and Roger Nelsen on Visual Gems of Number Theory. The two of us decided that the session was a success. The MAA thought so, too. Not long after MathFest 2005, we got a request from Don Van Osdol of the MAA encouraging us to put together a book based on the four session talks. The four speakers at our session thought this was a fine idea and agreed to contribute their work. We then set about looking for other articles that would be suitable for an undergraduate audience. We began with a list of al1 of the recent MAA prizewinning papers on number theory. Then, we sent emails to current aiid recent editors of the MAA journals, some wellknown number theorists, and a selection of recent MAA presidents, asking them for suggestions; the response was both ovenvhelming and gratiQing. We read through many baclt issues of the MAA journals aiid the AMS Notices. At one point, the number of suggestions was up into seven bits! Then the whittlingdown process began, and it was not easy. For one thing, no sooner had we brought the list down to a manageable size than one of us would toss a few more into the mixand we'd start over again. Finally, the list converged to the collection you have before you. And what a collection it is. Prizes won by these papers include the Allendoerfer, Chauvenet, Conant, Trevor Evans, Lester Ford, Hasse and Pólya Awards. Among the authors are recipients of the MAA's Haiino and Alder Awards for Distinguished Teaching, as well as Martin Gardner, George Pólya, Paul ErdBs, and Leonhard Euler. We have included many visual delights, and some of the proofs are very likely proofs from "The Book", Erdos' imaginary compendium of perfect proofs. We have divided the collection into seven chapters: Arithmetic, Primes, Irrationality, Sums of Squares and Polygonal Numbers, Fibonacci Numbers, Number Theoretic Functions, and Elliptic Curves, Cubes, and Fermat's Last Theorem. Before each chapter, we provide the reader with a summary of the articles that appear there. (You might cal1 this an "aroma.") As with any anthology, you don't have to read the Biscuits in order. Dip
lntroduction
xiii
into them anywhere: pick soinetliing from the Contents that strikes your fancy, and have at it. If the end of an article leaves you wondering what liappens next, then by al1 means dive in and do some research. You just might discover something new! We would like to acknowledge the following people for their advice and assistance with this book: Don Albers, Jerry Alexanderson, Tom Apostol, Jennifer Beineke, Lowell Beineke, Ed Burger, Marc Chamberland, Karl Dilcher, Undenvood Dudley, Frank Farris, Ron Graham, Richard Guy, Deanna Haunsperger, Roger Horn, Christopher Hughes, Dan Kalman, Steve Kennedy, Hugh Montgomery, Roger Nelsen, Ken Ono, Bruce Palka, Carl Pomerance, Peter Ross, Martha Siegel, Jim Tattersall, Don Van Osdol, Stan Wagon, and Paul Zom. Finally, we wish to thank our families for their support. It has been a pleasure working with MAA putting this collection together. We are particularly grateful to Elaine Pedreira, Beverly Ruedi, and especially Rebecca Elmo for their hard work, high standards, and dedication to this project.
 Arthur Benjamin 
Ezra Brown
August 8,2008
Part 1: Arithmetic
In Chapter XI of Lewis Carroll's Alice b Adventures in Wonderland, the Mock Turtle, in describing his schooling to Alice, referred to the four branches of arithmetic as Ainbition, Distraction, Uglification and Derision. Our first six Biscuits will treat al1 of these and more. We begin with Jiin Tanton's "A dozen questions about the powers of two" (Math Horizons, vol. 8, no. 1 (September 2001), pp. 510), an Evans Awardwinning exploration of the surprising ainount of interesting mathematics to be found among the powers of two. In Tanton's inimitable style, a dozen questions about the powers of two lead to answersand even more questions. He aslts questions about weighing problems, sums of truncated triangular numbers, Egyptian multiplication, checlters in a circle, a variant of the game Survivor, folding fractions, leading digits, and more. Most answers include a challenge to "Take It Further." Read this most enjoyable paper with pencil and paper in hand, and then explain the following complete sequence: 4, 1, 5,2,9,6,46, 3,53. Early in number theory classes, we learn that 30 is the largest integer n such that every positive integer strictly between 1 and n and relatively prime to n is a prime. In 1907 H. Bonse gave a clever proof that hinges on the fact that the product of the first n prime numbers exceeds the square of the (n + 1)" prime. Very neat, but what comes next? 1s there a largest number n such that every positive integer less than n and relatively prime to n is a prime power? Do some exploring and guess. Then read our next Biscuit, in which Michael Dalezinan strengthens Bonse's Inequality and answers this and other similar questions in "From 30 to 60 is not twice as hard" (Math. Magazine, vol. 73, no. 2 (April 2000), pp. 1511 53). At the end of this paper, Dalezman invites you to veriSl that 2730 is the largest integer n such that al1 positive integers less than n and prime to n have at most two prime divisors, multiplicities included. Replace "two" by "three" and "four", and the answers are 2 10210 and 29099070, respectively. We add the fractions and $ by finding the least common denominator, adjusting the numerators, and adding. If and $ are reduced fractions then, depending on the values of c and d, the resulting fraction might never, sometimes, or always be further reducible. b b The answer is "nevei' for $ and E,"sometimes" for 6 and 5 ,and "always" for and Harris Shultz and Ray Shiflett were at a workshop where this came up, and they wondered what the pattern was. In their article "Reducing the sum of two fractions" (Mathematics Teacher, vol. 98, no. 7 (March 2005), pp. 486490), they te11 us what they found and gently lead us to the answers. (Again, malte a guess, then read the article.) At the end, they encourage their readers to explore deeper waters: "It would be interesting to luiow how much of the facts about reducing numerical fractions carry over to the class of rational functions." It would, indeed! Let n be a positive integer, and let f be a mapping on Z mod n, the integers mod n.
e
h.
e
fi
2
Part 1:Arithmetic
For x E Zmod n, the forward orbit of x under f is the set (x, = x, x2 =f(x,), x, =f(x,) . ..). Now, join the points (xl, xl), (xl, x2), (x2,x2), (x2,x3), .. .. The picture you get should look familiar, because this graphical iteration method generates pictures similar to those that appear in every book on dynamical systems. Rafe Jones and Jan Pearce use this method to tackle a modest goal in our next Biscuitnothing less than bringing the beauty of fractions to the postmodern era of America's visuallyoriented, quantitatively illiterate culture. They begin their Allendoerfer Awardwinning paper, "A postmodern view of fractions and the reciprocals of Fermat primes" (Math. Magazine, vo1.73, no. 2, (April2000), pp. 8397), by reminding us that the amazing fractal images of chaos theory took popular culture by stonn. Wouldn't it be nice, they wonder, if this transformation of chaotic dynamical systems from differential equations, analysis and algebra into posters and tee shirts of the Mandelbrot set can be applied to, say, fractions? They do not simply wonder. They apply to the study of certain fractions the graphical techniques that were used to transform the Mandelbrot set from algebra to cultural icon. The resulting paper is a picturefilled treatment of such topics as rotational graph pairs, rotational symmetry, fractions with prime denominators, and perfectly syinmetric numbers. At the end, they apologize that they were not able to include al1 of their striking images in the paperbut they provide a pointer to their web site. Mathematics, including number theory, is the science of patterns, and nothing helps us better in discovering new patterns than a good picture. In "Visible structures in number theory" (Amer. Math. Monthi'y, vol. 108, no. 10 (December 2001), pp. 897910), Peter Bonvein and Loki Jorgenson present pleasing periodic patterns provided by polynomials, Pascal's triangle, and n. This paper, which was awarded the MAA's Lester Ford Award, presents a number of open questions that are provoked by these pictures, including the metamathematical question "What does it mean to prove a theorem visually or experimentally?" If you read MAA journals, you know that Roger Nelsen is the preeminent collector of Proofs Without Words (PWWs) anywhere. Our final arithmetical Biscuit is a selection of his "Visual gems of number theory" (Math Horizons, vol. 15, no. 3 (February 2008), pp. 79, 3 1). These visual treats include characterizations of primitive Pythagorean triples, Euclid's perfect nuinber formula, relationships between triangular numbers and squares, a proof that & is irrational, and Larson's elegant wordless proofsurely one for Paul Erdbs' mythical "Boolc" of perfect proofs that every triangular number is a "choose ~ W O "binomial coefficient. Read them and marvel, then try your hand at making up some yourself. For example, the sum of the first m even squares 22 + 42 +  + (2m)2 is a "choose three" binomial coefficient. Find a PWW of this.
A Dozen Questions About the Powers of Two James Tanton
Everyone is familiar with the powers of two: 1,2,4,8, 16, 32,64,128, and so on. They appear with surprising fiequencythroughout mathematics and computer science. For example, the number of subsets of a finite set is a power of two, as too is the sum of the entries of any row of Pascal's triangle. (Mathematically, these two statements are the same!) The largest prime number known today is one less than a power of two, a cube of tofu can be sliced into a maximum of 2" pieces with n planar cuts, and every even perfect number is the suin of consecutive integers from 1 up to one less than a power of two! Here 1have put together a dozen curiosities al1 about the powers of two. These puzzles toy with results and ideas from classic number theory and geometry, game theory, and even popular TV culture (one problein is about a variation of the game Survivor)! 1 hope you enjoy thinking about them as much as 1did.
1. A Weighty Problem A woman possesses five stones, each weighing an integral number of kilograms. She claims, with the use of a simple seesaw balance, she can match the weight of any stone you give her and thereby determine its weight. She maltes this claim under the proviso that your stone is of integral weight and weighs no more than 3 1 ltilograms. What are the weights of her five stones?
2. Multiplication without Multiplying Here's an alternative method to long multiplication: Head two columns with the numbers you wish to multiply. Progressively halve the figures in the lefthand column (ignoring remainders) while doubling the numbers on the right. Continue this operation until the lefthand column is reduced to 1. Delete al1 rows with an even number in the lefthand column and add al1 the surviving numbers from the righthand column. This sum is the desired product.
Why does this work?
Part 1:Arithmetic
3. Truncated Triangular Numbers The numbers 5, 12, and 5 1, for example, can be written as a sum of two or more consecutive positive integers: 5=2+3 12=3+4+5 51=6+7+8+9+10+11. Which numbers cannot be written as a sum of at least two consecutive positive integers?
4. Survivor N people, numbered from 1 to N, are stranded on an island. They play the following variation of the TV gaine Survivor: Members of the group vote whether person number N should survive or be escorted off the island. If 50% or more of the people agree to this person's survival then the game ends here and the N people al1 take an equal share of a $1,000,000 cash prize. If, on the other hand, the Nth person is voted off the island, the remaining N  1 people will take a second vote to determine the survival of the (N 1)th player (again with a quota of 50%). They do this down the line until a vote eventually passes and a person survives. The cash prize is then shared equally among al1 the folks remaining after this successful vote. Assume that al1players are greedy, but rational, thinkers; that they will always vote for their own survival, for example, and will vote for the demise of another player provided it does not lead to their own demise as a consequence. The question here is simple: who survives?
5. Pascal Curiosity Prove that al1 entries in the 2"th row (n E N) of Pascal's triangle are odd.
6. Checkers in a Circle Betty places a number of blaclc and white checkers in arbitrary order on the circumference of a circle. (Say Betty lays down N checkers.) Charlie now places new checkers between the pairs of adjacent checkers in Betty's ring: he places a white checker between every two that are the same color, a black checker between every pair of opposite color. He then removes Betty's original checkers to leave a new ring of N checlcers in a circle. Betty then performs the same operation on Charlie's ring of checlcers, following the same niles. The two players alternate performing this maneuver over and over again on the circle of checkers before them. Show that if N is a power of two, al1 the checlcers will eventually be white, no matter the arrangement of colors Betty initially puts down.
7. Classic Number Theory 1s 291 1 prime? What about 291+ l ?
8. De Polignac's Remarkable Conjecture In the midnineteenth century, the French mathematicianA. de Polignac made a remarkable observation: It seems that every odd number larger than one can be written as a sum of a power of two and a prime.
A Dozen Questions About the Power of Two
He claimed to have checked this for al1 odd numbers up to three million! Can you prove de Polignac's conjecture?
9. Stacking Dilemma Two line segments can sit in onedimensional space touching in a zerodimensional subspace, namely, a point: It is possible to arrange four triangles in a plane so that each triangle intersects each other triangle along a onedimensional line segment of positive length:
1s it possible to arrange eight tetrahedra in threespace so that each tetrahedron meets every other tetrahedron along a portion of surface of positive area?
10. The Game of 579 Here's a classic game for two players. It is played with three piles of coins, one with five coins, the second with seven and the third with nine coins. At each turn a player picks up as many or as few coins as she chooses from a single pile. The player who picks up the last coin wins.
What strategy could the first player employ to guarantee a win?
Part 1:Arithmetic
6
11. Folding Fractions It is possible to place a crease mark exactly halfway along a strip of paper simply by folding the paper in half. Then, using this mark as a guide and folding the left and right portions of the paper, we can accurately place creases at positions '/,and respectively. 1s it possible to accurately place a crease mark at position % on the paper?
v4
12. Where are the 7's? Does any power of two begin with a seven? If so, does any power of two begin with 77?
Comments, Answers and Further Questions
.
1 Her stones weigh 1,2,4,8 and 16 ltilograms respectively. As every positive integer can be written uniquely as a sum of distinct powers of two, she can match any weight up to 1 + 2 + 4 + 8 + 16 = 3 1 lcilograms with these stones. Taking It Further. Using a seesaw balance and a different set of five stones the woman can actually accomplish a much more impressive feat: she can determine the integral weight of any rock you give her weighing up to 243 lcilograms! What are the weights of these five different stones? Hint: The woman no longer claims she can match the weight of your stone, only that she can determine its integral value.
2. Removing the last digit of a number written in base two either divides the number in half or subtracts 1 and then divides by two, depending on whether the number is even or odd. (For example, the binary code for the number 13 is 1101. Deleting the last digit gives 110 which represents 6.) Thus one can determine the binary code for a nuinber simply by repeatedly dividing by 2 (ignoring remainders), and keeping track of whether or not the result is even or odd along the way. We can thus read off the binary code of 73 from the left column of the table as 1001001. This means 73 = 1 + 23+ 26, and so 73 23 = (1 + Z3 + 26) 23. Expanding the brackets yields: 73
x 23
1 X 23 t2X23
=
t22Jt23+ 23 x 23
+++e+
is+s% +
26 x 23.
A Dozen Questions About the Power of Two
7
The desired prod~~ct is precisely the surn of terrns (resulting from doubling the number 23 multiple times) that correspond to the placement of ones in the binary code of the number 73, namely, the placeinent of odd terms in the left column. This method works for any pair of natural numbers you wish to inultiply.
Comment. Coinputers perfom multiplication in this way. The halving and doubling operations are trivial when al1 numbers are expressed in base 2.
3. Al1 numbers except the powers of two can be written as a surn of at least two consecutive integers. If N is a number of the fonn N = ( n + 1)+ ( n + 2 ) +
+ ( n + k)
for n, k E N with k 1 2, then
If k is odd, then (2n + k + 1) is even and it follows that k is an odd factor of N. If, on the other hand, k is even, then (2n + k + 1) is an odd factor of N. Either way, N possesses an odd factor and so cannot be a power of two. Conversely, al1 numbers possessing an odd proper factor, can be written as a surn of two or more consecutive numbers. Suppose N = ab with a, b E N, b > 1, a 1 3, and a odd. Then N=b+b+b+b+..+b atimes + (b  1) = (b  (a  1)/2) + + b + (b + 1) + + (b + ( a  1)/2). If b  (a  1)/2 > O we are done. If not, the first few tenns of this surn are negative and will cancel the first few positive terms in the latter part of this sum. We need to show that, after cancellation, at least two positive terms survive. Simple algebra verifies that indeed (b  (a  1)/2) 5 b + (a  1)/2  2.
Taking it Further. Classify those natural numbers that can be expressed as a surn of at least three consecutive positive integers.
4. One person on the island (N = 1) will certainly vote for hiinself and so survive. With two people on the island (N = 2 case), player 1 will not vote for player 2's survival (he'll survive without her) but player 2 will. Thus player 2 survives and both folks share the prize. With three players (N = 3 case), players 1 and 2 will vote for player 3 'S demise (they're fine without her) and even voting for herself, player 3 will not gamer enough votes to survive. Players 1 and 2 will again share the prize. Consider the game with four people on the island. Player 4 will certainly vote for his suwival. So too will player 3, for without player 4, the previous analysis shows player 3 will not survive. Even though players 1 and 2 will vote against player 4, player 4 has enough votes to survive, and thus al1 four players stay on the island and share the prize. For a game with N < 8 players, players 1 through 4 have no need to vote for the surviva1 of higher numbered players. Players 5, 6, and 7 are therefore doomed to leave the island. We need the addition of an eighth player in the game to ensure their (and this eighth player 'S) survival.
Part 1 :Arithmetic
8
In this way we see that the number of people who suivive our game Suwivor is the largest power of two less than or equal to the number of people initially on the island.
Taking it Further. How do the results of the game change if players must attain strictly more than 50% of the votes in order to survive?
5. We are asked to show that each entry of the 2"th row of Pascal's triangle is congruent to 1 (mod 2). Regard the top row of Pascal's triangle as an infinite string of zeros except for a single "1" in the 'center.' Then every entry in the remaining rows of the triangle is the sum of the two nearest terms in the row above it. Worlting modulo 2, the first five rows of Pascal's triangle are thus:
... o ... ... O ...
... o
o O
o O
o 1
O
O
1
s..
e . .
O... O
1
O
o O
o
1 1
1
o O
1
O
1 1
O
o
1 1
...
o ...
Certainly al1 the terms of the first, second, and fourth rows of the triangle are 1 (mod 2). Also, the two 1'S on the fifth row are sufficiently spaced apart to generate their own copies of the first four rows of the triangle. We thus obtain a row of eight 1'S in the eighth row of Pascal's triangle. The ninth row then consists of two single 1'S which are sufficiently far apart to generate their own copies of the first eight rows of Pascal's triangle, ending with a sixteenth row which is nothing but 1'S; and so on. An induction arguinent shows that al1 2" entries of the 2"th row of Pascal's triangle are indeed congruent to 1 (mod 2).
Taking it Further. Prove that
is even for n, k E N with I < k < 2". 1s
(',"]
ever
odd for n 1 l ?
6. Break the circle and line the checkers in a row, noting that the first and last checlters are 'adjacent.' Represent this row of checkers as a string of O's and l's, where 'O' represents a white checker, and ' 1' a black checker. The transformation described in the checker game creates a new string of O's and 1'S where each entry in the second row is the sum of the two nearest entries from the top row (with the appropriate interpretation for the end digits given the 'wrap around' effect for the string). Suppose N is a power of 2. Consider a game starting with a single black checker. Due to the cyclic syrnmetry of the game, we may as well assume the black checlter is placed at the beginning of the string, and thus the game can be represented by a string of the forrn: 1000...o. Note that N  1 applications of the transformation generate the first N rows of Pascal's triangle modulo 2 (the 'wrap around' effect does not affect the formation of this initial portion of the triangle). By question 6, al1 entries of the final row are 1. Thus after N  1 steps, al1 checkers in the checker game will be black. One more application of the transformation yields nothing but white checlters. An arbitrary game can be thought of as a superposition of individual games involving single black checkers. For example, the game represented by 0 110 is a superposition,in some sense, of the games O 1O0 and 00 10. The checlter game transformation commutes with
A Dozen Questions About the Power of Two
9
'exclusive or' binary addition (that is, binary addition without carrying 1'S). As O100 and O010 both converge to 0000, it follows that O110 converges to 0000 + 0000 = 0000. This argument shows that al1 checker games, involving a power of two number of checkers, yield nothing but white checlcers in at most that many steps.
Taking It Further. Can anything be said for games with N checkers where N is not a power of two?
7. First note that 291= (27)13.The identities x131 = ( x  l ) ( x l 2 + x 1 l + . . . + x + 1) and x13 + 1 = ( x + l)(x12.11+
  . x + 1)
show that 27 1 = 127 and 27 + 1 = 129 are factors of 291 1 and 291+ 1 respectively. (So too are 8 191 and 8 193.) Thus neither number is prime.
Comment. Numbers of the form 2"  1 are called Mersenne Numbers. If n is composite, the above argument generalizes to show that 2"  1 too must be composite. If n is prime, however, the situation is less clear. For example, 2"  1 is prime for n = 2, 3, 5, 7, 13, 17 and 19, but not for n = 11. Nonetheless, Mersenne numbers have proven to be a rich source of large prime numbers, the largest known today being 26972593  1.
Taking It Further. 1s 291 3 prime? What about 291 5 and 291 7?
8. Don't bother! It isn't true. De Polignac missed the number 127 which cannot be written as a sum of a power of two and a prime. (One only need check this for the powers 2" with n=O, . ..,6.) If only de Polignac noticed this slip, he could have saved himself literally months of very hard work! 9. To arrange eight tetrahedra in threespace in the appropriate way, use the following diagram of eight triangles in a plane. Connect the four shaded triangles to a point hovering below the plane of the drawing, and the four unshaded triangles to a point hovering above the plane of the drawing. This yields eight suitably touching tetrahedra.
Taking It Further. Prove it is impossible to arrangefive triangles in a plane that meet pairwise in a line segment of positive length. 1s it possible to arrange nine tetrahedra in threespace in the appropriate way?
10. Express the numbers of coins in each pile in binary notation and write these numbers as rows of a table:
Part 1: Arithmetic
Notice there are an odd number of 1'S appearing in the ones, twos and eights columns of the table. To guarantee a win, the first player should always move so as to produce an even number of 1'S in each column. Her first turn is thus to convert the number 1001 into 0010, that is, to reduce the pile of nine coins to two coins. Her opponent will then be forced to create a table with an odd number of 1'S in at least one column, and therefore a gaine with at least one remaining coin. Player 1 always operating this way thus offers her opponent no hope of ever winning.
Taking It Further. Reverse 579 is played the same way except this time the person who picks up the last coin loses. Does either player have a best strategy in this variation of the game?
11. Placing a crease mark halfway between two previously constructed crease marks can only ever produce fractions of the form "/,, where N is a power of two. And conversely, every fraction of this form can be created via a finite sequence of such folding operations (see below). Thus there is no (finite) procedure for constmcting the fraction y7.However, as every number can be approximated arbitrarily closely by a fraction of the form indicated Cjust tmncate its binary decimal expansion for example), it is possible to place a crease at any position we choose with any desired degree of precision. Alternatively, sne can use the following procedure for placing a crease arbitrarily close to the position 5/,. Begin by making a guess as to where this fraction lies along the strip and place a crease at this location. Now fold the right portion of the strip in half to place a crease halfway between the guess and the right end of the paper. This produces a crease mark at position 6/, with the error reduced in half. Now fold from the left to produce a crease at position ?17with error reduced in half yet again, and then, finally, fold fioin the right to produce a crease mark at position v7with one eighth the original error. Repeating the "RLR sequence of folds multiple times yields a sequence of crease marlts that rapidly converge to the true 5/,position. Taking it Further 4 . It is no coincidence that the sequence of folds "RLR" miinics the binary representation 101 of the number five. Show that if N is one less than a power of two, then the sequence of left and right folds that hones in on the fraction VN is precisely the binary expansion of a read baclwards with ' 1' representing 'right' and 'O' representing 'left.' Taking it Further 2. Consider a fraction of the form "/n. Write a as an ndigit binary number (you may need to place zeros at the beginning), and read this binary expansion backwards as a sequence of instructions with ' 1' and '0' representing 'right' and 'left' again. Show that if you follow these instructions through just once the final crease mark formed lies precisely at position V2n.
Taking it Further 3. Let q be any fraction in the interval [O, 11. Show that, with a square sheet of paper, it is possible to produce, in a finite number of folds, a creased line segment precisely q units long.
A Dozen Questions About the Power of Two
12. We seek integers n and k stich that that is, If {x) denotes the fractional part of the number x, we thus are being asked to find a value n for which Working on the interval [O, 1) with 'wrap around' effect (that is, working modulo l), we hope to find a multiple of loglO2that falls within the segment [log,, 7, loglo 8), which is about 0.058 units long. It is easy to show that log,, 2 is an irrational number (an equation of the form 2b= 1Oa can only hold if both exponents are zero) and consequently no two distinct multiples of loglo2 have the same fractional part. Thus, of the first 21 multiples of log,, 2, at least two if them must lie within a distance of 1/2, = 0.05 from each other (considering the wrap around effect). Cal1 these multiples mlog,, 2 and (m + q)log,, 2. It then follows that the multiples (m + q)loglo 2 and ( m + 2q)loglo 2 are also within this distance of each other, as too are (m + 2q)loglO2and (m+3q)loglO2, and so on. Creeping along this way, we must eventually hit upon a multiple of lag,, 2 that lies in the interval [log,, 7, loglo8). This shows that powers of two beginning with a seven do exist. (The diligent reader may have discovered that 246is the first power of two which begins with a 7.) We can say more: The above argument shows that the multiples of log,, 2 fonn a dense set in the interval [O, 1) and so there are infinitely many multiples that lie in any given segment. Thus there are infinitely inany powers of two that begin with seven and, in some sense, we can say that 7 occurs as a first digit 5.8% of the time! Similarly, loglo78  loglo77 0.56% of the powers of two begin with '77' and there are infinitely many powers of two that begin with any prescribed (finite) set of digits! (For example, there are infinitely many powers of two that begin with the first billion digits of pi!)
Acknowledgments and Further Reading Severa1 of these puzzles explore classic ideas from number theory. The interested reader can look at Jay R. Goldman's beautiful text The Queen of Mathematics, A Historically Motivated Guide to Number Theory (A. K. Peters, Ltd., 1998), for example, to learn more about this fascinating and challenging subject. 1first learned of the classificationof tnincated triangular numbers as a result discovered by eight year old Mit'ka Vaintrob of New Mexico. He followed a geometric approach, literally truncating triangular arrays of coins or buttons to create trapezoids with at least two rows. His analysis of those numbers which can be expressed as a sum of three consecutive integers is a remarkable achievement. Gengzhe Chang and Thomas Sederberg give a complete analysis of the circular checkers game in their wonderful book Over and Over Again (Mathematical Association of America, 1997). Question 9, with its obvious extensions, is a very old and extremely hard question. It is luiown that it is always possible to arrange 2" highdimensional "simplices" in nspace that meet, pairwise, in regions of (n  1)space of positive volume, but it is not at al1 clear whether one can do more. It has long been luiown that is impossible to arrange five triangles in a plane in this way, but it wasn't until 1991 that J. Zalts was able to prove the impossibility of arranging nine tetrahedra in threespace. Analysis of higherdimensional spaces is still an
Part 1:Arithmetic
12
area of open research. See Martin Aigner and Günter M. Ziegler's Proofs from the Book (SpringerVerlag, 1999), Chapter 13, for a discussion on this fascinating topic. The 579 game, of course, is a specific instance of the famous gaine Nim. One can explore the subject of nimbers in John H. Conway and Richard K. Guy's The Book of Numbers (Copernicus, 1996). Changing the value of the quota in the game Survivor leads to some very interesting matheinatics; my colleague Charles Adler and 1 are currently writing about some curious results froin this game.
ASecond Helping This is one of my favourite "dozenal" articles. The weighty problem (question 1) caught me by surprise when 1 realized that ternary expansions using digits 1, 0, and 1 can be "stretched" to just the even numbers to yield the astounding result claimed in the solutions. Never forget: Even classic problems that have been bandied about for decades can yield new twists and delights! (See "Introducing binary and ternary expansions via weighings." College Mathematics Journal, 33 no. 4 (2002), 171 8, for details.) The survivor problem (question 4) is closely related to the problem of iterating the approximate squaring functionf (x) = x[x] ,which caught the attention of J. C. Lagarias and N. J. A. Sloane. (See their paper "Approximate Squaring" Experimental Mathematics, vol 13 (2004) NO 1; 113128.) 1 failed to inention in the article that counting the powers of two that begin with a seven (question 12) offers an explanation of an intriguing phenomenon known as Benford's Law. It is said that, in 1881, American astronomer Simon Newcomb noticed that in public resource collections the first few pages of boolts of numerical tableslogarithms tables, for instancewere generally more worn and grimy than latter pages. These first pages contain data values that begin with "1 ." He thought this curious. The same phenomenon was later independently observed in 1938 by physicist Frank Benford, who went further and examined large collections of data tables from a wide variety of sources: population growtli, financia1 data, scientific activities. He observed that, with some consistency, about 30.1% of the entries in a data set begin with a "1", about 17.6% with a "2", about 12.5% with a "3," al1 the way down to about 4.6% with a "9". This observation has become luiown as Benford's Law. The IRS today uses Benford7slaw to quickly scan first digits for possibly falsified tax records. Explanation: Any phenoinenon that is based on some kind of exponential growth (population figures, scientific studies, interest rates, the powers of two) can be analyzed in exactly the same way we analyzed first digits of powers in the article!
Originally appeared as: Tanton, James. "A Dozen Questions about the Powers of Two." Math Horizons. vol. 8 (September 2001): pp. 51 0.
From 30 to 60 is Not Twice as Hard Michael Dalezman
Eudid's proof tliat there are infinitely many priines [3, p. 251 can be inodified to yield a proof of a siinple inequality: If p p z , . . is tlie sequence of priine iiuinbers and n >: 2 then p , p,, . . . p,, > pll+,. In 1907, Bonse [l] gave an eleinentaiy proof of a stronger inequality, now called Bonse's Inequality [4]: If n 2 4 tlien p p , . . . ,p , > p;+, . Bonse tlien used his iiiequiility to prove tliat 30 is tlie largest integer 111 with tlie following property:
,
I i 1< k
< ?IZ
aiid ( lc , m ) = 1, tlien
k is ,a prime.
In tliis note we @vean elernentaiy proof of a stronger inequality alid use it to prove that 60 is the largest integer »1 witli the following property: If 1 < 7c < m
and ( Ic , rn)
=
1 , tlien 7c is a prime power
We tlien iridicate liow tlie iiiequality can be streiigthened and liow the result can be generalized. The following notations will be rised:
w ( k ) : the number of distinct priine divisors of k; N k ) : the iiuinber of priine divisors of k , counting inultiplicity; 1r 1: the largest integer not gi4eatertlian x; T ( z): tlie iiumber of priines not exceeding x ;
+(k):
tlie iiuinber of positive integers priine to k and not exceeding k.
THEOREM 1. I j n 2 4 , theu p , p, 0 0 4 p >pIl+:, t, p,,,,. This inequality follows readily froin Bertrand's postulate [3, p. 3671 but we give liere a proof tliat is selfcontaiiied.
Proof: The result caii easily be verified for n
< 10. Let i = [$], and suppose
p,_,  1, t = i, 2 , . . . , pi. For al1 t , Let us consider the p, integers N, = t p l p, N, < p , p, p, < pn +, aiid is prime to pl,pe ,. . . , p, . Tlius if q, is tlie sinallest prime dividing N,, tlien pi S q, < p,,,, . Tlie q,'s are distinct, for if q, = q,,, witli t + t', then q,l N,  Ntr = ( t  t ' ) p, p, p, l , so q,lt  I'; tliis is iiiipossible since 1< t , t' p,. Hence tlie iiumber of N,'s inust be no greater tlian tlie iiuinber of primes q such that p, < q < p,,,, . Therefore p, 5 n + 2  i. But i = E , so n S 2i 121 +1and pi~i+3.Thelastinequalityclearlyfailsfori~5,soitfailsforn>I0. . + O
,
DEFTNTTION. Aii integer in satisfies property Psif forall
k suchthat1 He used this result to sliow tliat 1260 is tlie largest iliteger witli tlie property:
pi+,.
IfI.c;k t';f+ for suffiiciently large n. Using tliis iiiequality, he wrote, he hnd found tlmt 30,030 was tlie largesr integer with tlie property: I f l ~ k < m and
(k,m)=i
then
fi(k)~3.
(Actually, Boilse erred; tlie corred nuinber is 60,060.) Land~iu[2] ggeeidked Bonse's results, proving that for every iiiteger s i 1 there exists an iiiteger n, such that TI
2 n ,=1pl
y,
p,, > p:::;
lie coiicluded that tliere exists a Inrgest iiiteger m, with tlie propoperty: 1f 1 g k < m , and ( k , , m , s = ) 1, tlleii Q ( k ) 5 s . Our results too, can be extended and getier;ilized.
To prove this, we replace i
= [$]
by i =
[S]ín tlie proof of Tlreorein 1;we get
From 30 to 60 is Not Twice as Hard
15
Tlie reverse to tliis inequalit~will be a conseqiieiice of tlie followiiig 3 leiiiinas: L~lrfvfh1.
FOT a11 intcgers
(i
2 2 ni~c[furnll x
>0
Tliis follows froin the fact that tlie intcrval froiii contaiins at inost +(a) primes.
a(x)
/vi to
X
;+(a)
+ (o  1).
( k + l ) n (for k = l.,2,.. . L)l:
Tliis is obtaiiied as follows: For any s > O, we let i = n ( x ) then substitute i  1 for ~ ( r and ) p, for x iii Lenrnia 1.
+ 1, tlieii
x < pi. We
Tliis follows frorii tlie fact tl~at
Tlieoreiii 2 c m be iised to prove tliat, for eveiy S , tliere exists a largest iiiteger satisfying P3.As in the case s = l., we liave tlie followiirg result:
in,
To prove the existeiice of m,9,let m be aii iiiteger satisf~iiig.T9,aiid let us assuine that, for some 2 2 u,, we llave
By Leiiima 4, tliis implies p , p , pi+, S m; tliis contradictioii proves tliat m < p, 11, pi1, and tlius establislies the existente of ?n,$. Bounds fos m, We will now show tliat
PIoof We saw tliat ?iz, < TJ p , p,, lf y ,,, P., + . pit,+ 1 nlY tlien 1,em~iia4 gives y pz p,,, S m , On tlie otlier liand, by defiiritioii of n , we liave y I 11, 1). , < 1 1 , ~pn, ~ + pil, . Tliis slio\vs tliat p po * pIt, satisfies P9aalid gives tlie lower boui~dfor 1 ~ 1 , . +
\.
* * e
The reader is invited to veiify tlint n, ancl in, = 29,099,070.
= 6,
,
,
n,
= 7, n, = 9,
rn,
= 2730,
jtz,
= 210,21.0
REFERENCES 1. H. Boilse, Übr~r.eilie bekariiite E:ige~ischaft cter Zilil 30 uizc.1 ilir.~I~~rallge~i~c'i~~rrui~g, cIrc:!?iv ( 1 ~ 1 Mritlzomc~tikflor1 Plz!pik ( 3 ) 12 (2907). 292295. 2. Eclm~incll,andau, II~cllic/l~rtclt rler Leh~avoclll chr T~crfc~ilntig rler P i  i ~ t ~ z t ~ lval. r l ( ~1,~Clielseii, ~, New York, NY, 1053, PP. 2229234. 3. Ivair Niven, Ilelll~crtS. 'Lucker.iticin,aizct Ifiigh 1,. Moiltgoi>iciy, AII Piitro(11rclior~to tire 'l'llc.or!j c?f Nttvtbers, 5"' Ecl*tioii, Wiley, New York, NY, 1901, 4. J. V. Uspc~skyancl M. A. Hcaslct, Eletrwr~tcrr!~ Ni~r,ll)er'fllcíor!y,McGrarv Hill, Nerv York, NY, 1939, p. 87.
Part 1:Arithmetic
Originally appeared as: Dalezman, Michael. "From 30 to 60 is not Twice as Hard." Mathematics Magazine. vol. 73, no. 2 (April2000): pp. 151153.
Reducing the Sum of Two Fractions Harris S. Shultz and Ruy C. Shiflett
Sometimes when we add fractions, the sum can be reduced even though we have used the least common denominator. Other times, the sum cannot be reduced. For example, if we add 113 + 116, the sum 316 can be reduced to 112. However, 215 + 116 = 17/30 cannot be reduced. Let's look at another example:
This can be reduced to 23/35. However, when we add 2/21 101105 + 281105 = 381105, which cannot be reduced.
+
4/15, we obtain
There are pairs of denoininators for which it seems we never can reduce the sum. For example,
which cannot be reduced. If we try 3/10 and 5/12, we obtain 18/60 + 25/60 = 43/60, which still cannot be reduced. By trying other numerator values, the reader will discover that whenever you add al10 + b/12, where each of the two addends is in lowest terms, the resulting sum having denominator equal to 60 (the least common denominator) cannot be reduced. On the other hand, there are pairs of denominators for which it seems we always can reduce the sum. Choose an a and b for which al20 and bl 12 are reduced and add them using the least common denominator 60. Every choice seems to produce an ailswer that can be reduced. You should now be wondering if this is true for al1 choices of a and b. Severa1 years ago, while discussing adding and reducing fractions in a workshop, we observed that certain sums of two fractions can be reduced while others cannot be reduced and wondered why. If there was a pattern, it was not immediately obvious. And searches of the literature did not provide us with any background information. This led us to pose the following general question: Given a pair of natural numbers, c and d, when does there exist a pair of natural numbers a and b for which when a/c and bld are added to form a single fraction, that fraction can be reduced? It is assumed that the denominator of the sum is the least common multiple of c and d and that the addends a/c aiid bld are in lowest terms. As is common practice, we shall say that u and v are relativelyprime if they have no common prime factor. For example, 15 and 14 are relatively prime since 15 = (3)(5) and 14 = (2)(7). If a/c is reduced to lowest terms, then a and c must be relatively prime. In adding 7/60 to 11/36, we write 60 = (22)(5)(3) and 36 = (22)(32), find the least common multiple to be (22)(5)(32), and multiply the numerator and denominator of the first fraction by u = 3 and the second by v = 5. Notice that u and v are relatively prime. This will always be true, as we shall see shortly. That is, if m is the least common
dirYIUs,.
=,.
"
Part 1:Arithmetic
18
multiple of numbers c and d, then there are relatively prime integers, u and v, where m = cu = dv. To proceed from here, we need two useful facts: Fact 1: If r, S, t are given integers with r + s = t and if the number n divides any two of the numbers r, S, and t, then n divides the third number. For example, consider 18 + 49. We lcnow that 7 divides 49 but not 18. Therefore, by Fact 1, we know that 7 cannot divide 18 + 49, without even doing the arithmetic. Fact 2: r and s are relatively priine when and only when there exist integers x and y for which rx + sy = 1. For example, 15x + 14y = 1 when x = 1 and y = 1. It should be noted that, in this result, x and y have to also be relatively prime, as are y and r and s and x. The proof of Fact 2 is based on the result in Number Theory stating that if r and s are any nonzero integers, then there exist x and y such that rx + sy is equal to the greatest common factor of r and s. Proof of this can be found in Burton (1998).
The General Case In number theory, we often need to lcnow the exact power of a prime that divides an integer. This power for a primep and an integer n is called the "porder of n," written ordp(n). So, for example, since 150 = (2)(3)(52), ord5(l50) = 2, ord3(l50) = 1, and ord7(l50) = 0. It turns out that the answers to our questions about whether or not the sum of two fiactions can be reduced depends on the existence of a common prime factor of the denominators that shows up with exactly the same exponent in their prime factorizations. In other words, everything depends on the primes p with the property that ordp(c)= ordp(d).As a shorthand, we cal1such a prime balanced for c and d. Primes for which ordP(c) f ordp(d) will be called unbalanced for c and d.
Example b a a b Suppose  = and  = c (2)(52)(75)(113)(132) d (32)(53)(73)(113)(132) are reduced. Adding these fractions, we obtain
where u = (32)(5) and v = (2)(72). Notice that 11 and 13 are balanced primes for the denominators while 2, 3, 5, and 7 are unbalanced priine factors of the denominators. We malte the following observations in this example: u and v are relatively prime; the balanced primes 11 and 13 divide neither u nor v;
Reducing the Sum ofTwo Fractions
the unbalanced prime factors 3 and 5 divide u but not b (because bld is reduced); the unbalanced prime factors 2 and 7 divide v but not a (beca~isea/c is reduced). Generalizing from this example provides an understanding of Lemmas 1 and 2. Throughout what follows, we will always use m = cu = dv to mean the least common multiple of c and d.
Lemma l. u and v are relativelyprime. Lemma 2. Suppose that a/c and b/d are reduced. Ifp is un unbalanced prime factor of c or d, then p divides u and not b, o r p divides v and not a. Ifp is a balancedprime for c and d, then it does not divide u, y, a or b. Lemma 3. Suppose that a/c and b/d are reduced. Ifp is un unbalancedprime factor for c or d, then p does not divide au + bv. ProoJ: By Lemma 2, eitherp divides u and not b, o r p divides v and not a. Without loss of generality, supposep divides u and not b. Since u and v are relatively prime, p does not divide v. Therefore, p does not divide bv. Since p divides u, and therefore au, and since p does not divide bv, it follows from Fact 1 thatp does not divide au + bv.
Theorem l. There exist natural numbers a and b for which a/c and b/d are reduced and (au + bv)lm is not reduced ifand only ifc and d have a balancedprime factov: ProoJ: Assume that a/c and bld are reduced and write
By Lemma 3, an unbalanced prime factor of c or d cannot be a divisor of au + bv. So, if there exist natural numbers a and b for which a/c and bld are reduced and (au + bv)lm can be reduced, then c and d must have a balanced prime factor. Notice that if (au + bv)lm can be reduced, the only possible common prime factors of the numerator and denominator are the balanced prime factors of c and d. Conversely, suppose c and d have a balanced prime factor. If P denotes the product of al1 the balanced primes for c and d, then P is a divisor of m. Since u and v are relatively prime, u2 and v2 are relatively prime. So, by Fact 2, there exist integers x and y such that
Pxu2 + pyv2 = P and (Pxu  v + gPuv2)u + (Pyv + u + gPvu2)v = P(1 + 2 g ~ 2 v 2 ) ,
20
Part 1:Arithmetic
where g is a natural number large enough that Pxu  v + gpuv2 and Pyv + u + gPvu2 are both positive. If we define a = Pxu  v + gpuv2 and b = Pyv + u + gpvu2, then the fraction (au + bv)lm can be reduced by P, since P is a divisor of au + bv = P(l + 2guZv2)and of m. Also, it turns out that a is relatively prime to c and b is relatively prime to d. Here's why : To see that a and c are relatively prime, take any prime divisor q of c. If q is a balanced prime, then q divides P so it divides Pxu + gpuv2 but not v so it does not divide a. If q is an unbalanced priine factor of c or d, then q divides u or v but not both. So q divides v + g ~ u v but 2 not Pxu so q does not divide a, or q divides Pxu + gpuv2 but not v so q does not divide a. So a and c are relatively prime. We may show that b and d are relatively prime in the sarne way. Let us look at two of our earlier examples in the context of Theorein 1. We saw that when we add 4/21 + 7115, the sum 691105 can be reduced. Since the denoininators 2 1 and 15 have a balanced prime factor, namely 3, the theorem assures us that this was no accident and that there do exist natural numbers a and b for which al21 and b115 are reduced and (5a + 7b)/105is not reduced. It also seemed that each time we added al10 + bl12, for any pair of integers a and b, where each of the two addends is in lowest terms, the resulting sum having denominator equal to 60 (the least common denominator) could not be reduced. Since the denominators 10 and 12 do not have a balanced prime factor, the theorem assures us that what seemed to be true is indeed true. In the proof of Theorem 1, under the assumption that c and d have a balanced prime factor, we constructed a sum a/c + bld tliat could be reduced by the product P of al1 the balanced priines for c and d. This is suminarized by the following. Corolllary. If c and d have at least one balanced prime factoq then there exist natural numbers a and b for which a/c and b/d are reduced and au + bv is divisible by eveíy balancedprime factor of c and d. Theorem 2. Let c and d be given natural numbers. Thefraction
can be reducedfor al1 natural numbers a and b where a/c and b/d are reduced ifand only i f 2 is a balancedprirne factor for c and d. ProoJ: If 2 is a balanced prime for c and d, then u and v are both odd. If a and b are natural numbers for which a/c and bld are reduced, then a and b are odd. Therefore, au + bv is even and, a +=b aufbv c d m consequently, can be reduced. Conversely, suppose 2 is not a balanced prime of c and d. We shall show that there exists a and b for which alc, bld, and (au + bv)lm are al1 reduced. If there are no balanced prime factors of c and d, then by Theorem 1 , (au + bv)lm is always reduced when a/c and bld are reduced and we are done. So assume c and d have at least one balanced prime. By the Corollary, there exist natural numbers, A and B, for which Alc and Bld are reduced and Au + Bv is divisible by every balanced prime factor of c and d.
Reducing the Sum ofTwo Fractions
21
Let g be the maximum of al1 prime factors of c and d and define q to be the product of al1 odd primes less than or equal to g. Then q + 2 has no prime factors less than or equal to g. So, c + q + 2 is relatively prime to c. Let a = (c + q + 2)A and b = B to get:
Suppose (c + q + 1)Au + (Au + Bv) and m have a common prime factor p. By Lemma 3, p must be a balanced prime for c and d. Therefore, p is odd andp divides c. Also, since Au + Bv is divisible by every balanced prime factor of c and d, p divides Au + Bv as well. Recall that A and c, and u and c are relatively prime. Then p divides neither A nor u, since p divides c. Also, since p divides c and p divides q, p does not divide c + q.+ 1. Therefore, p does not divide (c + q + 1)Au. Consequently, by Fact 1, p does not divide (c + q + 1)Au + (Au + Bv), contradicting our assumption. Therefore, a/c, bld, and (au + bv)lm are al1 reduced. Let us look at an earlier example in the context of Theorem 2. We observed that for every choice of a and b, when you add al20 + bl12 using the least common denominator 60, where each of the two addends is reduced, the resulting sum can be reduced and we wondered if this is always m e . Since 2 is a balanced prime for the denominators 20 and 12, the theorem does in fact assure us that this is always true.
Rational Functions The questions we have examined also arise in the addition of ratios of polynomials, called rational functions. For example, the'sum
where a and b are nonzero numbers, cannot be reduced. To verie this, observe that there do not exist nonzero numbers a and b such that (a + b)x + 2a  3b is a constant multiple of either x  3 or x + 2. Likewise, we can show that if
where a and b are nonzero numbers, is to be written as a single fraction having denominator (X 3)(x + 1)(x)(2x 5)(x + 3), this rational expression cannot be reduced. However, there do exist nonzero constants a and b such that the sum
can be reduced. For example, let a = 3 and b = 1, then
In this last example, the factor x  2 appears with multiplicity 1 in each denominator. It appears to play a role analogous to that of a balanced prime factor in our previous
22
Part 1:Arithmetic
work. There is much known about the way that polynomials factor and divide each other and even the way some of them behave like primes. It would be interesting to know how much of the facts about reducing numerical fractions carry over to the class of rational functions.
1. Burton, David M. Elementary Number Theoy, Fourth Edition. New York: McGrawHill, 1998.
Editor's Notes: Harris Shultz and Ray Shiflett provide yet another example of "mathematics for teaching:" mathematical investigations connected to the teaching professionthe question "When can you reduce the sum of two fractions?" is certainly more likely to come up in the teachers' lounge than in an engineering firm. And, while Shultz and Shiflett carry out the investigation for its own sake, the results (Theorems 1 and 2) will be quite useful to teachers as they design activities and problem sets around rational number arithmetic. We suspect that more than a few areas of mathematics were inspired by mathematical problems teachers face as they design activities for their students. One that we recently encountered is how to devise two linear equations in two unknowns with small integer coefficients so that students will not be able to get exact coordinates for the intersection of the graphs simply by zooming with their calculators. Shultz and Shiflett end the article with an intriguing question: How much of their result carries over to rational functions in, say, one variable with rational coefficients. This is again a question closely related to our profession, because two basic algebraic systems of precollege mathematicsthe integers and polynomials in one variablehave deep stmctural similarities that allow many results (and proofs) in one system to be transported to the other with only minor modification. For example, Fact 2 (and the more general result about greatest common divisor) holds for polynomials, too, and for the same reasons. This is responsible for the fact that both systems have a "fundamental theorem of arithmetic:" the unique prime decomposition property that is used throughout this article.
Originally appeared as: Shultz, Harris S. and Ray C. Shiflett. "Reducing the Sum of Two Fractions." Mathematics Teacher. vol. 98, no. 7 (March 2005): pp. 486490.
A Postmodern View of Fractions and the Reciprocals of Fermat Primes Rafe jones ond jan Peorce
I / t O l base 40
1/101 base 50
1/83 base 27
Foretaste The story of this article began with a surprise visit of a highschool aged student and his mother to Dr. Jan Pearce's outer office at Berea college: Rafe Jones appeared with Dr. Libby Jones to inquire about Rafe doing a summer research project with Dr. Pearce. Caught a bit off guard by the apparition of a colleague and her son, and not iinmediately sold on doing research with so young a student, Dr. Pearce stalled for time, aslting Rafe what he might lilte to work on. His quick reply: "Anything but number theory1 know nothing about number theory." Dr. Pearce came round on doing the research project, and tried to accommodate Rafe's request. The work began with computer experiments in dynamical systems, but al1 roads seemed to lead to number theory. Soon the project required tools lilte the Euler totient function, and one of the main results involved Fermat primes. Steadily that old "queen of mathematics" (in the phrase of Gauss) wore down Rafe's defenses, and soon a hint of love was in the air. It blossomed into a Ph.D. in number theory at Brown University. Today Dr. Jones is an Assistant Professor at Holy Cross, working on both number theory and dynamics. Dr. Pearce continues to embrace unexpected opportunities at Berea.
Part 1:Arithmetic
Introduction and preliminaries In Ainerica's visually01iented, quaiititatively illi terate ciilture, i inages llave a great deal of power, so if a picturt: is today wortli a thousand words, it inust be wortli iit least a billioii nuinbers. This powei OS the iinage is a hallinarlc of tlie postinodern era, in wliicli tbe critica1 role of tlie observes has coine to be recognized, and aii uiiderstancling OS tlie viewpoiiit lias becoine iiiseyarable iroin tliat of tlie object. 111 soine ways, the blossoining of cliaos theoiy inarked tlie arrival of inatheinatical postinoderi~isin.Not so loiig ago, inatlieinatical ideas were virtually uiiseeii in Ainerican popular culture, and it took the eiitliralling fractal iniages of cliaos theoiy to chaiige that: tlie studies of cliaos ancl fractals becaine soriie of tlie ii~ostwidely discussed inatlieinatical topics ever, and pictures OS fractal iinages sucll as tlie
FIGURE I Graplzical analysis of 1/37 base 35.
Mandelbrot set begnii cropping up on Tshirts aiid posters selling in Americaii inalls. The power of aii iinage is diffificiilt to underestiiiiate, particularly wh,eii it comes to creatiiig iiiterest iii a topic widely regarded. as blaiid. Perliaps we could fue1 a greater excitemeiit iii traditionally iinderappreciated areas of inatbematics if oiily we could preseiit tliein iii a Rasliier grapliical fasbiori. Tale fractioiis, for iiistaiice, wliicli to inaiiy people aypear to be rnerely seas of nuiiibers; after all, infinitely inany fractioiis llave iiifiiiitely long strings of digits as tlieir deciinal expaiisioiis. Wouldn't it be nice if we could see coinplicated fractions, lilce & base 35, LIS simple iinages? Wouldn't i,t be even nicer if, as for the Mandelbrot set, tliose giapliical iinages exposed soinetlUiig aboot tlie i.nlieseiit inatliematicd stiucture that t11e concise algebraic exyressioii oiily iinplied? In diis piiper, we apply to the stucly of certain fmtioiis tlie saine grapliical techniyues used to tr~~iisforin the Mandelbrot set from algebra to iinage. This will
Part 1: Arithmetic
26
deciiiial expcpüiision tliat is i places to tlre nglit of tlie deciinal poiiit, tlien iii tliis exainple d i cl,,, = '3 f'or al1 i. Tliese syiniiietries, as we shdl see, Iiave inore tliaii a iiuiiierical sigiiificaiice. Before iiioving on to grapliical topics, it will seive iis well to discuss tlie tliree I 1 and b E X (mod n), 1 is syiiiinetric iii base b. Tlierefore n is perfectly syiiiiiietric. i Curi4entlytliere are only five kiiown Fermat priiiies: 3, 5, 17, 257, aiid 65537. Tlius, only six lznown perfectly syininetric nuinbers lurk ainong al1 tlie positive iiitegers greater thaii one, suggesting tliat perfect syiiimetiy is ainong tlie more uiiusual properties a nuinber can have. However, precisely Iiow inany perfectly syiriinetiic nuinbers exist reinai~isan open question.
Questions and conclucions Our discussion oí' tlie nui~iberof syniinetiyyroducing bases Tor various fractioiis raises hvo questions about certaiii luiids of piiiiie nuiiibers: Question 1. Does there exist, for each positive integw 71, a nnhrrnl i~ul~aber k si~ch
t h ~ 2t "(2 k 11
+ 1) + 1 is y rime?
If so, theii for any positive iiiteger t2 one can find a priiiie p such tliat 2 divides  1 exactly n tinies. Tliis would niean tliat for any yositive iiiteger u , priines exist
tliat ase syininetric in
%'S of tlie considered bases.
Question 2. How ninny Feiinnt prdmes ave there?
No one Iias any idea; we know only tliat tliere are at least five. P i e i ~ ede Ferinat tliouglit that al1 riuinbers of tlie forin 2" 1 were priine, but histoiy Iias proveii otlienvise: Al1 tlie iiiiinbers generated usiiig k = 5 , . . . , 11 liave turned out to be coinposite, as well as selected otliers, including tlie inonstrous z''~'~' 1. Tliere reinaiii, however, irifiriitely iniuiy iiiore asyetundeter~niiiedpossibilities. An answer to this questioii would also te11 6ow inaiiy perfectly syininetric nuinbers exist. Tlius ends our exploratioii of fractioiis m d syiiimetiy. Postinoderiiisin Iias tauglit us tliat al1 ways of looking at a prol>lein are not equivalent: different perspectives Iiighliglit differeiit properties. Adopting our society's penchaiit for iinages led us to exainiiie inore closely tlie syininetries of ceitain fractioiis, and opened our eyes to unexpected visioiis.
+
+
Note on the computer program During tlie course oí' this project, we wrote a siinple coinputer prograin that graphically aiialyzes aiiy fraction in any base. We found inany of tlie iinages quite stnkilig and beautiful, aiid were soriy not to be able to iiiclude al1 of thein iii tliis article. For those of you who would like to generate soine of tliese images yourselves, our prograin is in an electroiiic suppleinent at http : // www .maa.org/pubs/mm_supplements/ lndex.html . Acknawlcclgments. We woulcl like to thank Dr. Mask ITariiscl~fbr liis Iielp with MATLAB, Di. Jaizies 1,yiicli for his iriterest ancl eizcotirageiuent, tlle Revsreiid Kent Gilbert fos ii~oralsupport ailcl occasioilal entertaiiiment, ancl Dr. Lihby Jones for tjinely susteilance.
Part 1:Arithmetic
REFERENCES .l. K. I.1. Beclcer aild M. Doifler, Dyticr~ir.ical:S!lstcíms crticl Il;rncto/.~,Cari~biiclgc Univcrsity Press, Cainbridge, UK, 1969. 2. K, Devmey, Clznos, FInctnl's,rltzd Dytwr17#c.v,AddisoiiWesley, Reading, MA, 1990. 3. J. Silverinan, A F.tie,zdly Introcli~ctio/zd o Ntaiibet Tlieor!y,PseilticeHall, Upper Saclclle River, NJ, 1997.
Originally appeared as: Jones, Rafe and Jan Pearce. "A Postmodern View of Fractions and Reciprocals of Fermat Primes." Mathematics Magazine. vol. 73, no. 2 (April2000): pp. 8397.
Visible Structures in Number Theory Peter Borwein and Loki jorgenson
l. INTRODUCTION. 1 see a confused mass.
Jacques Hadamard (18651963)
These are the words the great French mathernatician used to describe his initial thoughts when he proved that there is a prime nurnber greater than 11 [ l l , p. 761. His final mental image he described as ". , .a place somehere between the confused mass and the first point". In commeiltjng on this in his fascinating but quirky monograph, he asks "What may be the use of such a strange and cloudy imagery?". Hadamard was of the opinion that mathematical thought is visual and that words only interfered, And when he inquired into the thought processes of his most distinguished midcentury colleaugues, he discovered that most of them, in some measure, agreed (a notable exception being George Pólya). For the nonprofessional, the idea that mathematicians "see" their ideas rnay be surprising. However the history of mathematics is marked by many notable developments grounded in the visual. Descartes' introduction of "cartesian" coordinates, for example, is arguably the most iinportant advance in mathematics in the last millenium. It fundamentally reshaped the way mathematicians thought about mathematics, precisely because it allowed them to "see" better mathernatically. Indeed, mathematicians have long been aware of the significance of visualization and made great effort to exploit it, Carl Friedrich Gauss lamented, in a letter to IIeinrich Chnstian Schumacher, how hard it was to draw the pictures required for making accurate conjectures. Gauss, whom many consider the greatest mathematician of al1 time, in reference to a diagram that accompstnies his first proof of the fundamental theorem of algebra, wrote It still remains tme that, with negative theoreins such as this, transforming personal convictions into objective ones reqiiires deterringly detailed work. To visuatize the whole variety of cases, one would have to display a large numbes of equcitions by curves; each curve would have to be drawn by its points, and determining a single point alone requires lengthy coxnputations. You do nat see from Fig. 4 in iny first paper of 1799, how much work was required for a proper drawing of that curve. Carl Friediich Gauss (17771 855)
The kind of pictures Gauss was looking for woiild now take seconds to generate on a computer screen. Newer computational environments have greatly increased the scope for visualizing mathematics. Compinter graphics offers magnitudes of improvement in resolution and through color, animaspeed over handdrawn images and provides increased ~~tility tion, image processing, and user interactivity, And, to sorne degree, mathernatics has evolved to exploit these new tools and technicpes. We explore some subtle uses of interactive graphical tools that help us 'kee" the mathematics more clearly. In particular, we focus on cases where the right picture suggests the "right theorem", or where it indicates stmcture where none was expected, or where there is the possibility of "visual proof" .
Part 1:Arithmetic
40
For al1 of our exarnples, we have developed Internetaccessible interfaces. They allow readers to interact and explore the mathematics and possibly even discover new results of their ownvisit www.cecm,sfu.ca/projects/numbers/.
2. IN PURSUIT OF PATTERNS. Computers make it easier to do a lot of things, but inost of the things they make it easier to do Andy Rooney don't need to be done.
Mathematics can be described as the science of patterns, relationships, generalized descriptions, and recognizable structure in space, numbers, and other abstracted entities. This view is borne out in numerous examples such as [16] and [15]. Lynn Steen has observed [19]: Mathematical theories explain the relations arnong patterns; functions and maps, operators and inorphisrns bind one type of pattern to another to yield lasting mathernatical stmctures. Application of inathematics use these patterns to "explain" and predict natural phenomena that fit the patterns. Pítten~ssuggest otller patterns, often yielding patterns of patterns,
This description conjures ~ i images p of cycloids, Sierpinski gaskets, "cowboy hat" surfaces, and multicolored graphs. However it isn't immediately apparent that this patently visual reference to patterns applies throughout mathematics. Many of the higher order relationships in fields such as number theory defy pictorial representation or, at least, they don't immediately lend themselves intuitively to a graphic treatment. Much of what is "'pattern" in the knowledge of mathematics is instead encoded in a linear textual fomat bom out of the logical formalist practices that now dorninate mathernatics. Within number theory, many problems offer large amounts of "data" that the human mind has dlficulty assimilating directly. These include classes of numbers that satisfy certain criteria (e.g., primes), distributions of digits in expansions, finite and infinite series and summations, solutions to variable expressions (e.g., zeroes of polynomials), and other unmanageable masses of raw inforrnation. Typically, real insight into such problerns has come directly from the mlnd of the mathematician who ferrets out their essence from formalized representations rather than from the data. Now computers make it possible to "enhance" the human perceptual/cognitive systems through many different kinds of visualization and patterns of a new sort emerge in the morass o% numbers. However the epistemological role of computational visualization in mathematics is still not clear, certainly not any clearer than the role of intuition where mental visualization takes place. Wowever, it serves severa1 usefiil functions in current practice. These include inspiration and discovery, informal comunication and demonstration, and teaching and learning, Lately though, the area of experimental mathematics has expanded to include exploration and experimentation and, perhaps controversially, formal exposition and proof. Some carefully crafted questions have been posed about how experiment might contribute to mathematics [S]. Yet answers have been slow to come, due in part to general resistance and, in some cases, alarrn [ l l ] within the mathematical community. Moreover, experimental mathematics finds only conditional support from those who address the issues formally [7], 191. The value of visualization hardly seems to be in question. The real issue seems to be what it can be used for. Can it contribute directly to the body of mathematical knowledge? Can an image act as a form of "visual proof"? Strong cases can be made to the affimative [7], [3] (including in number theory), with examples typically in
Visible Structures in Number Theory
Figure 1. A simple "visual prooí?' of xEi(f)2n =
4
the form of simplified, heuristic diagrams such as Figure 1. These carefully crafted examples cal1 into questioa the epistemological criteria of an acceptable proof. Establishing adequate criteria for mathematical proof is outside the scope of this paper; interested readers can visit [20], a repository for information related to reasoning with visual representations. Its authors suggest that tl~reenecessary, but perhaps not sufficient, conditions may be:
reliability:the underlying means of arriving at the proof are reliable and the result is unvarying with each inspection consistency: the means and end of the proof are consistent with other known facts, beliefs, and proofs repeatibility: the proof may be confirmed by or demonstrated to others Each requirernent is difficult to satisfy in a single, static visual representation. Most criticisms of images as mathematical knowledge or tools make this clear [a], [13]. Traditional exposition differs significantly from that of the visual. In the logical formal mode, proof is provided in linearly connected sentences composed of words that are carefully selected to convey unambiguous meaning. Each sentence foilows the previous, specifying an unalterable path through the sequence of statements. Although error and misconception are still possible, the tolerances are extremely demanding and follow the strict conventions of deductivist presentation [12]. In graphical representations, the same facts and relationships are often presented in multiple modes and dimensions. For example, the path through the information is usually indeterminate, leaving the viewer to establish what is important (and what is not) and in what order the dependencies should be assessed. Further, unintended information and relationships may be perceived, either due to the unanticipated interaction of the complex array of details or due to the viewer's own perceptual and cognitive processes.
Part 1:Arithmetic
42
As a consequence, successful visual representations tend to be spartan in their detail. And the few examples of visual proof that withstand close inspection are limited in their scope and generalizability. The effort to bring images closer to conforrnity with the prevailing logical modes of proof has resulted in a loss of the richness that is intrinsic to the visual.
3. IN SUPPORT OF PROOF. Computers are useless. They can only give you smswers.
Pablo Picasso (18811973)
In order to offer the reliability, consistency, and repeatability of the written word and still provide the potential inherent in the medium, visualization needs to offer more than just the static image. Xt too must guide, define, and relate the information presented. The logical fomalist conventions for mathematics have evolved over inany decades, resulting in a mode of discourse that is precise in its delivery. The order of presentation of ideas is critical, with definitions preceding their usage, proofs separated from the general flow of the argument for modularity, and references to foundational material listed at the end. To do the same, visualization inust include additional mechanisins or conventions beyond the base image. Zt isn't appropriate simply to ape the logical conventions and find some visual metaphor or mapping that works sirnilarly (this approach is what limits existing successful visual proofs to very sirnple diagrams). Instead, an effective visualization needs to offer severa1 key features
e
dynamic: the representation should vary through some parameter(s) to demonstrate a range of behaviours (instead of the single instance of the static case) guidance: to lead the viewer througli the appropriate steps in the correct order, the representation should offer a "path" through the information that builds the case for the proof flexibility: it should support the viewer's own exploration of the ideas presented, including the search for counterexamples or incompleteness openness: the underlying algorithms, libraries, and details of the prograrnming languages and hardware should be available for inspection and confirmation
With these capabilities available in an interactive representation, the viewer could then follow the argument being made visually, explore al1 the ramifications, check for counterexarnples, special cases, and incompleteness, and even confirm the correctness of the implementation. In fact, the viewer should be able to inspect a visual representation and a traditional logical formal proof with tlie same rigor. Although current practice does not yet offer any conclusions as to how images and computational tools may impact mathematical niethodologies or the underlying epistemology, it does indicate the direction that subsequent work may take. Examples offer some insight into how emerging technologies may eventually provide an unambiguous role for visualization in mathematics,
4. TWE STRUCTURE OF NUMBERS. Numbers may be generated by a myriad of means and techniques. Each offers a very small piece of an infinitely large puzzle. Number theory identifies pattems of relationship between numbers, sifting for the subtle suggestions of an underlying fundamental structure. The regularity of observable features belies the seerning abstractness of numbers.
Visible Structures in Number Theory
Figure 2. The first 1600 decimal digits of 7t mod 2.
Binary Expansions. In the 17th century, Gottfried Wilhelm Leibniz asked in a letter to one of the Bernoulli brothers if there might be a pattem in the binary expansion of n. Three hundred years later, his question remains unanswered. The numbers in the expansion appear to be completely random. In fact, the most that can now be said of any of the classical mathematical constants is that they are largely nonperiodic. With traditional analysis revealing no patterns of interest, generating images from the expansions offers intriguing altematives. Figures 2 and 3 show 1600 decimal digits of n and 22/7 respectively, both talcen mod 2. The light pixels are the even digits and the dark ones are the odd. The digits read from left to right, top to bottom, like words in a book. What does one see? The even and odd digits of n in Figure 2 seem to be distributed randomly. And the fact that 22/7 (a widely used approximation for n) is rational appears clearly in Figure 3. Visually representing randomness i s not a new idea; Pickover [la] and Voelcker 11221 have previously examined the possibility of "seeing randomness", Rather, the intention here is to identify patterns where none has so far been seen, in this case in the expansions of irrational nurnbers. These are simple examples but many numbers have stmctures that are hidden both from simple inspection of the digits and even from standard statistical analysis. Figure 4 shows the rational number 1/65537, this time as a binary expansion, with a period of 65536. Unless graphically represented with sufficient resolution, the presence of a regularity might otherwise be missed in the unending string of O's and 1's. Figures 5 a) and b) are based on similar calculations using 1600 terms of the simple continued fractions of n and e respectively. Continued fractions have the form
Part 1:Arithmetic
m Figure 3. The first lGOO decimal digits of 22/7 mod 2.
Figure 4. The first rnillion binary digits of 1/65537 reveal Lhe subtle diagonal st~vcturefrom the periodicity.
Visible Structures in NumberTheory
b) Figure 5. The first 1600 valucs of tbe continued fraction for a) 7c and b) e, both mod 4
Part 1: Arithmetic
46
In these images, the decimal values have been taken rnod 4, Again the distribution of the ai of n appears random though now, as one would expect, there are more odds than evens. However for e, the pattern appears highly structured. This is no surprise on closer examination, as the continued fraction for e is
and, if taken as a sequence of digits, is a rational number rnod 4. It is apparent from the images that the natures of the various distributions are quite distinct and recognizable. In contrast no such simple pattern exists for exp(3) rnod 4. Presumably this particular visual representation offers a qualitative characterization of the numbers. It tags them in an instantly distinguishable fashion that would be almost impossible to do otherwise.
Sequences of Polynomials. Few things are l~arderto put up with than the annoyance of a good example. Mark Twain (18351910)
In a similar vein, structures are found in the coefficients of sequences of polynomials. The first example in Figure 6 shows the binomial coefficients (:) rnod 3, or equivalently Pascal's Triangle rnod 3. For the sake of what follows, it is convenient to think of the ith row as the coefficients of the polynomial (1 x)' taken rnod three. This apparently fractal pattern has been the object of much careful study [lo]. Figure 7 shows the coefficients of the first eighty Chebyshev polynornials rnod 3 laid out like the binomial coefficients of Figure 6. Recall that the nth Chebyshev polynomial T,,,defined by T, (x) := cos(n arccos x), has the explicit representation
+
and satisfies the recursion
Figure 6. Eighty rows of Pascai's Triangle mod 3
Visible Structures in NumberTheory m
Figure 7, Eighty Chebyshev Polynomials mod 3
The expression for T. ( x ) resembles the (i form )of the binomial coefficients and its recursion relation is similar to that for the Pascal's Triangle. Figure 8 shows the Stirling numbers of the second kind mod 3, again organized as a triangle. They are defined by
and give the number of ways of partitioning a set of rr elements into m nonempty subsets. Once again the f o m of ):( appears in its expression. The wellhown forms of the polynomials appear distinct. Yet it is apparent that the polynomials are graphically related to each other. In fact, the surnmations are variants of the binomial coefficient expression. It is possible to find similar sorts of structure in virtually aoy sequence of polynomials: Legendre polynomials; Euler polynomials; sequences of Padé denominators to the exponential or to (1  x)" with a rational. Then, selecting any inodulus, a distinct
Figure 8. Eighty rows of Stirling Numbers of the second kind mod 3
Part 1:Arithmetic
48
pattern emerges. These images indicate an underlying structure within the polynomials themselves and demand some explanation. While conjectures exist for their origin, proofs for the theorems suggested by these pictures do not yet exist. And when there finally is a proof, rnight it be offered in some visual form?
QuasiRationals. For every problem, there is one solution which is simple, neat, and wrong. II.L. Mencken (18801956)
Having established a visual character for irrationals and their expansions, it is interesting to note the existence of "quasirational" numbers. These are certain wellknown irrational numbers whose images appear suspiciously rational. The sequences pictured in Figures 9 and 10 are {in}:" mod 2 and {ie};" mod 2, respectively. One way of thinking about these sequences is as binary expansions of the numbers
where a is, respectively, 7t or s. The resulting images are very regular. And yet these are transcendental numbers; having observed this phenomenon, we were subsequently able to explain this behavior rigorously from the study of
Figure 9. Integer part of { i n ) ~ $ mod ~O 2; note the slight irregularities in the ppsedoperiodic pattern.
Visible Structures in NumberTheory
Figure 10. Integer part of (ie]f"
mod 2; note the sliglit irreguiarities in the pseudoperiodic pattem.
which is trascendental for al1 irrational a. This follows from the remarkable continued fraction expansion of Bohmer [4]
Here (q,) is the sequence of denominators in the simple continued fraction expansion of a. Careful examination of Figures 9 and 10 show that they are only pseudoperiodic; slight irregularities appear in the pattern. Rationallike behaviour follows from the very good rational approximations evidenced by the expansions. Or put another way, there are very large terms in the continued fraction expansion. For example, the expansion of
[O, 1,2,42,638816050508714029100700827905,1,126,. . .], with a similar phenomenon for e. This behaviour makes it clear that there is subtlety in the nature of these numbers. Indeed, while we were able to establish these results rigorously, many related phenomena exist whose proofs are not yet in hand. For exarnple, there is no proof or
Part 1:Arithmetic
explanation for the visuaI representation of
Proofs for these graphic results might well offer further refinements to their representations, leading to yet another critica1graphic characterization.
Complex Zeros. Polynomials with constrained coefficients have been much studied [2], [17], [ti]. They relate to the Littlewood conjecture and many other problems. Littlewood notes that "these raise fascinating questions" [14]. Certain of these polynomials demonstrate suprising complexity when their zeros are plotted appropriately. Figure 11 shows the complex zeros of al1 polynomials P. (z) = a0
+ aiz + azz2 +  + anzn
of degree n 5 18, where ai = (1, +1). This image, rerniniscent of pictures for polynomials with al1 coefficients in the set (0,$1) 1171, does raise many questions: 1s the set fractal and what is its boundary? Are there holes at infinite degree? How do the holes vary with the degree? What is the relationship between these zeros and those of polynomials with real coefficients in the neighbourhood of ( 1, +1)? Some, but definitely not all, of these questions have found some analytic answer 1171, 161. Others have been shown to relate subtly to standing problems of some significance in number theory. For example, the nature of the holes involves a old problem known as Lehrner's conjecture [l].It is not yet clear how these images contribute to a solution to such problems. However they are provoking rnathematicians to look at numbers in new ways.
Figure 11. Roots of Litrlewood Polynomials of degree at most 18 for coefficients f l .
Visible Structures in Number Theory
5, CONCLUSION, Visualization extends the natural capacity of the mathematician . to envision his subject, to see the entities and objects that are part of his work with the aid of software and liardware. Since graphic representations are firmly rooted in verifiable algorithms and machines, the images and interfaces may also provide new foms of exposition and possibly even proof. Most important of all, like spacecraft, diving bells, and electron microscopes, visualization of mathematical structures takes the human mind to places it has never been and shows the mind's eye images frorn a realm previously unseen. Readers are encouraged to review this paper in full color online [Zl],
ACKNOWLEDGEMENTS. This work has been supported in part by the NCE for Mathematics of Information Technology and Cornplex Systems (MITACS), and in part by research and equipment grants from the Natural Sciences and Engineering Reseach Council of Canada (NSERC). We thank the Centre for Experimental & Constmctive Mathernatics.
REFERENCES 1. F. Beaucoup, P. Borwein, D. Boyd, and C. Pinner, Multiple roots of 11, 11 power series. Gndon Math. SOC.57 (1998) 135147. 2. A.T. BhanichaReid and M. Sainbandham, Random Polynomials, Academic Press, Orland~,FL,1986. 3. Alex Bogomolny, http:/lwww.cuttheknot.com/ctMpww.htd 4. J. Borwein and P. Borwein, On the generating function of the integer part: [na y ] , J, Number Theory 43 (1993) 293318. 5. J,M. Borwein, P.B, Borwein, R. Girgensohn, and S. Parnes, Making sense of experimentalmathematics, www.cecm.sfu.ca/organics/vault/expmath/ 6. P. Borwein and C. Pinner, Polynomials with (O, f 1, 1) coefficients and a root close to a given point, Canadiaiz J. Math. 49 (1997) 887915. 7. J.R. Brown, Proofs and pictures, Brit. J. Phil. Sci. 48 ( 1 997) 161180. 8. T. Eisenberg and T. Dreyfuss, On the reluctante to visualize in mathematics, in Visualizationin Teaching and Learning Mathematics, Mathematical Association of America, Washington, DC, 1991, pp. 2537. 9. Marcus Giaquinto, Epistemology of visual thinking in elernentary real analysis, Brit. J, Phil. Sci. 45 (1994) 78981 3. 10. A. Granville, The arithmetic properties of binomial coefficients, in Proceedings of the Organic Mathematics Workshop, Dec. 1214, h~tp://www.cec~n.sfu.ca/organics/, 1995, IMpress, Sirnon Fraser University, Burnaby, BC. 11. John Horgan, The death of proof, Scientgc American October, 1993, pp. 92103. 12. Irme Lakatos, Proofs ancl refitations: the logic of mathematical discovery, Cambridge University Press, Carnbridge, 1976. 13. Bmno Latour, Drawing things together, in Representation in Scient@c P~ractice,Michael Lych and Steve Woolgar, eds,, MIT Press, Cambridge, MA, 1990, pp. 2537. 14. J.E, Littlewood, Some problems in real and co~nplexanalysis, in Heath Mathematical Monographs, D.C. Heath, Lexington, MA, 1968. 15, Roger A. Nelson, Proofs Without WordsII, More Exercises in Visual Thinking, Mathematical Association of America, Washington, DC, 2000. 16. Roger A. Nelson, Proofs Without Words: Exercises En Visual Thinking, Mathematical Association of America, Washington, DC, 1993. 17. A. Odlyzko and B. Poonen, Zeros of polynomials with 0,l coefficients, Enseign. Math. 39 (1993) 317348, 18. C. Pickover, Picturing randomness on a graphics supercomputer, IBM J. Res. Datelop. 35 (1991) 227230. 19. Lynn Arthur Steen, The science of patterns, Science 240 (1988) 611616. 20. http://www.hcrc.ed.ac.uMgal/Diagrams/biblio.htrnl 21. http:/lwww.cecm.sfu.ca/pborweinl 22. J. Voelcker, Picturing randoxnness, IEEE Spectrum 8 (1988) 1316.
+
52
Part 1: Arithmetic
PETER BORWEIN is a Professor of Mathen~aticsat Simon Fraser University, Vancouver, British Coliimbia His Ph.D. is from the University of British Columbia under the supemision of David Boyd. After a postdoc. toral year in Oxford and a dozen years at Dalhousie University in Halifax, Nova Scotia, he took up his curren position. He has authored five books and over a hundred research articles. His research interests span diophan. tine and computational number theory, classical analysis, and symbolic computation. He is corecipient of tht Cauvenet Prize and the Hasse Prize, both for exposition in mathematics. CECM*Sitnon Fraser University,Burizaby, BC, Canada VSA l S 6 pborwein@bb,cecm.sfu.ca
LOKI JORGENSON is an Adjunct Professor of Mathematics at Simon Fraser University, Vancouver, Britisl Columbia. Previously the Research Manager for the Centre for Experimental and Constmctive Mathematics he is a senior scientist at Jaalam Research. He maintains his involvement in mathematics as the digital edito for the Canadian Mathematical Society. His Ph.D. is in computational physics from McGill University, ant he has been active in visualization, simiilation, and conlpiitation for over 15 years. His research has includec forays into philosophy, graphics, educational techxiologies, high performance computing, statistical mechanic5 high energy physics, logic, and number theory. CECM, Slmon Fraser Unlversity,Bunaaby, BC, Canada V5A lS6 [emailprotected]
Originally appeared as: Bonvein, Peter and Lolti Jorgenson. 'Visible Structures in Number Theory." American Mathematical Monthly. vol. 108, no. 10 (December 2001): pp. 897910.
Visual Gems of Number Theory Roger B. Nelsen
While looking through some elementary number theory texts recently, 1 was struck by how few illustrations most of them have. A number can represent the cardinality of a set, the length of a line segment, or the area of a plane region, and such representations naturally lead to a variety of visual arguments for topics in elementary number theory. Since a course in number theory usually begiiis with properties of the integers, specifically the positive integers, the texts should have more pictures. In the next few pages 1'11 present some "visual gems" illustrating onetoone correspondence, congruente, Pythagorean triples, perfect numbers, and the irrationality of the square root of two. We begin withjgurate nurnbers, positive integers that can be represented by geometric patterns. The simplest examples are the triangular numbers tn (= 1 + 2 + 3 + + n) and square numbers n2. In Figure l(a) are the familiar patterns for t4 and 42. The computational formula for t,, is n(n + 1)/2, which is easily derived from Figure l(b) by seeing that 2tn = n(n + 1).
e e . .e . * . e
(a)
O000
(b)@0000
me000 me.00 o .*
0000 0000 0000
Figure 1. Triangular and Square Numbers. You may have noticed that each triangular number is also a binomial coefficient:
One explanation for this is that each is equal to n(n + 1)/2, but this answer sheds no light on why the relationship holds. A better explanation is the following: there exists a one to one correspondence between a set of tn = 1 + 2 + 3 + + n objects and the set of twoelement subsets of a set with n + 1 objects. In Figure 2, we have a visual proof of this correspondence. S  .
+ + ..+ n = [":'l.
Figure 2. A visual proof that 1 2
Part 1:Arithmetic
54
There are many lovely relatioiiships between triangular and square numbers. One is hidden in the following theorem, which appears in nearly every elementary number theory text as an example or exercise: if n is odd, then n2 = l(inod 8). In Figure 3, we have a visual proof that every odd square is one more than eight times a triangular number, which proves the result. But it does moreit is an essential part of an induction proof that there are infinitely many numbers that are simultaneously square and triangular! First note that t , = 1 = 12.Then observe that
so that if tk is a square, so is tgt For example, t8 = 62, t288= 2042, etc. But not al1 square k'
triangular numbers are generated this way: t49= 3s2, t168L = 11892, etc. Challenge: Can you find a visual argument to use in the proof for odd triangular numbers?
0 . 0 0 . * . . 0 0 0 0 . 0 0 . . 0 0 . 0 0 . 0 . . 0 0 0 . 0 . .
....e
e.. .e.
@.e.
0.00000 0 0 . . 0 0 0 0 0. 0 0 0 . . . 0 0 0 . 0 0 . . 0 0 . 0
Figure 3. A visual proof that n odd implies n2 = l(mod 8). Congruente results involving triangular numbers can be illustrated in a similar manner. In Figure 4, we "see" that t,, I O (mod 3).
Exercise: Find visual arguments to show that t3,= O (mod 3) and t3n+1 1(mod 3).
ooo
000 0000
00000 000000 0000000 . . O O .....OOOO ......OOOO . . . . . . . 0 0 0 0 Figure 4. A visual proof that t3,  1 = O (mod 3).
Visible Gems of Number Theory
Discussing triangles and squares in geometry always brings to mind the Pythagorean theorem. In number theory it brings to inind Pythagorean triples. A primitive Pythagorean triple (PPT) is a triple (a, b, c) of positive integers with no common factors satiseing a2 + b2 = c2. Familiar examples are (3,4, 5), (5, 12, 13) and (8, 15, 17). Indeed, there are infinitely many PPTs, and in Figure 5 we have a visual proof that n2 odd (Le. n2 = 2k+l) implies that n2 + k2 = (k + 1)2, or equivalently, that (n, k, k +1) is a PPT. In Figure 5, the n2 = 2k +1 gray dots are first arranged into an "L" then k2 white dots are drawn, for a total of (k + 1)2dots. Exercise: In the proof, we've actually shown that tliere are infinitely many PPTs in which one leg and the hypotenuse are consecutive integers. Find a visual proof that there are infinitely many PPTs in which the hypotenuse and one leg differ by two.
Figure 5. There are infinitely many PPTs.
A classical result characterizing PPTs is the following theorem: (a, b, c) is a PPT if and only if there are relatively prime integers m > n > 0, one even and the other odd, such that (a, b, c) [or (6, a, c)] = (2mn, m2  n2, m2 + n2). Figure 6 uses the double angle formulas from trigonoinetry to illustrate this result.
cose
M
m
Yil2
2
Figure 6. A characterization of PPTs. Another less welllcnown characterization is the following: there exists a onetoone correspondence between PPTs and factorizations of even squares of the form n2 = 2pq
Part 1:Arithmetic
withp and q relatively prime. Figure 7 illustrates this result.
Figure 7. Another characterization of PPTs. The PPT (3, 4, 5) is the only such triple where the sum of two consecutive squares is the next square. But what about sums of three consecutive squares? Four consecutive squares? Observe: 32 + 42 = 52 lo2 + 112+ 122= 132+ 142 212 + 222 + 232 + 242 = 252 + 262 +272 What's the pattern? A little reflection yields the observation that each square immediately to the left of the equals sign is the square of four times a triangular number, Le., 4 = 4(1), 12 = 4(1 + 2), 24 = 4(1 + 2 + 3), etc., which leads to the identity (4tn n)2 + .
+ (4tJ2 = (4tn + 1)2+ . + (4tn + n)2.
While it is not difficult to veri@ this by induction, the illustration (for the n = 3 case, using 4t3 = 4(1 + 2 + 3) of these "Pythagorean nins" in Figure 8 may better explain why the relationship holds.
Figure 8. Pythagorean runs.
Visible Gems of Number Theory
57
The ancient Greeks called positive integers like 6 and 28 perfect, because in each case the number is equal to the sum of its proper divisors (e.g., 28 = 1 + 2 + 4 + 7 + 14). In Book IX of the Elements, Euclid gives a formula for generating even perfect numbers: If p = 2*l 1 is a prime number, then N = 2"p is perfect. We can illustrate this result very nicely in Figure 9 by letting N be the area of a rectangle of dimensions 2" x p, and noting that the rectangle can be partitioned into a unioii of smaller rectangles (and one square) whose areas are precisely the proper divisors of N.
Figure 9. Euclid's formula for even perfect numbers. We conclude with one more example from the Greeks. The Pythagoreans were probably the first to demonstrate that & is irrational, that is, to show that lengths of a side and the diagonal of a square are incommensurable. Here is a modern version of that classical Greek proof. From the Pythagorean theorem, an isosceles triangle of edgelength . If is rational, then some multiple of this triangle must have three 1 has hypotenuse sides with integer lengths, and hence there must be a smallest isosceles right triangle with this property. But the difference of two segments of integer length is a segment of integer r e inside any isosceles right triangle whose three length and so, as illustrated i n ' ~ i ~ u 10, sides have integer lengths we can always construct a smaller one with the same property! Hence & must be irrational.
Exercise: Prove that & and & are irrational in a similar manner,
Figure 10. The irrationality of &.
Part 1:Arithmetic
Further Reading For more visual proofs with triangular numbers, see James Tanton's "Triangular Numbers" in the November 2005 issue of Math Horizons. For visual proofs in combinatorics, see Jennifer Quinn and Arthur Benjamin's Proofs That Really Count: The Art of Combinatorial Proof (MAA, 2003). For an introduction to creating visual proofs, see Claudi Alsina and Roger Nelsen's Math Mude Visual: Creating Images for Understanding Matkematics (MAA, 2006). Some of the proofs in the article originally carne from: 1,. T. Apostol, "The irrationality of the square root of twoa geometric proof," Amer: Math. Monthly, 107 (2000), 841842. 2. M. Boardman, "Proof without words: Pythagorean runs," Math. Mag., 73 (2000), 59. 3. D. Goldberg, personal communication. 4. J. Gomez, "Proof without words: Pythagorean triples and factorizations of even squares," Math. Mag., 78 (2005), 14. 5.
L. Larson, "A discrete look at 1 + 2 + 382.
+ n,"
College Math. J., 16 (1985), 369
6. C. Vanden Eynden, Elementary Number Theory, Random House, 1987.
Originally appeared as: Nelsen, Roger B. "Visual Gems of Number Theory." Math Horizons. vol. 15, no. 3 (February 2008): pp.79,3 1.
Part II: Primes
The prime numbers are the building blocks of the integers, thaiiks to the Fundamental Theorem ofArithmetic that every natural number has a unique prime factorization. We open this chapter with "A new proof of Euclid's theorem," that there are infinitely many primes, given by Filip Saidak (Amev: Math. Monthly, vol. 113, no. 10 (December 2006), pp. 937938). We won7tsay too much about it (since the proof is only four senteiices long), but it is a constructive proof based on nothing more than the observation that consecutive numbers are relatively prime. The article references books that provide many other elegant proofs of Euclid's theorem. One of these proofs is "On the inñnitude of primes" by Harry Furstenberg (Amer. Math. Monthly, vol. 62, no. 5 (May, 1955), p. 353). This paper is the only item in this book that requires more than a first course in number theory, since it is based on elementary ideas fiom topology. But the paper is a classic and is just one paragraph long, so we felt it was worth the space. In a similarly brief paper, "On the series of prime reciprocals" (Proc. Amev: Math. Soc., vol. 17, no. 2 (April 1966), p. 541), James Clarkson proves a stronger theorem. Using little more than the divergence of the harmonic series, he proves that 71 also diverges. Any collection of articles on prime numbers ought to have at least one article by Paul Erdds, the most prolific mathematician of the twentieth century, and a wandering minstrel of mathematics. A perfect number is a number n whose proper divisors sum to n. We say n is pseudoperfect if some of its proper divisors sum to n. If the sum of the divisors of n exceeds n, but n is not pseudoperfect, then n is called weird. The number 70 is weird (in fact it7sthe smallest weird number) since its proper divisors 1, 2, 5, 7, 10, 14, 35 have a sum of 74, but there is no way to obtain a sum of 70 using some of these numbers at most once. In this paper "On weird and pseudoperfect numbers" (Mathematics of Computation, vol. 28, no. 126 (April, 1974), pp. 617623), Stan Benltoski and Erdds prove and conjecture properties of weird, pseudoperfect, and related numbers. For instance weird numbers are not too rarethey have a positive density among the integers. Although maybe only the first half of the paper is suitable for undergraduates, we have kept the paper in its entirety. The proof of the first theorem is elementary and requires an integral best evaluated by using infinite series. After the proof, Erdds offers a $300 reward for the proof of a related conjecture. Although ErdOs died in 1996, the problem remains open and the reward is still claimable. Here are some famous theorems about primes that have names attached to them. Given a prime p , we have: Fermat's Little Theorem: Ifa is un integei; then ap a (modp). Wilson's Theorem: ( p  l)! 1 (modp). Cauchy's Theorem: If G is a Jinite group whose order is a multiple of p, then G contains an element of order p .
E,,,
Part 11: Primes
60
Lucas's Theorem: Ifn and r are written in basep, say n = no+ nlp + r = r, + r,p + + rkpk,where O i ni, r j2
for j > 100.
Let 1 a, < . < aj2be the firstj2 of the si's. By (7), aj25 2" l. Consider now the integers (5) for 1 5 r S j2, a, < ak S 2 "jt l. By (7), a,. < 2" l. Thus, by (6), the integers (5) are al1 less than
Now, observe that there are at least
Part 11: Primes
72
integers of the form (5); they are al1 distinct and are al1 less than 2 n ~2. Thus, fiom (8), (61, and (71, 29 for j > 100. < 10(10) j2 00 Now, (10) and (3) immediately imply the uniforrn boundedness of C l l a , . It is perhaps not quite easy to get the best possible value of C. It seems certainithat C < 10. Unfortunately, we obtain no information about pseudoperfect numbers by these methods. It is known that the density of integers having property P exists and that the same holds for P1(see [2]). Denote by u, < u, < ,respectively vl v2 < ,the integers which do not have property P, respectively P', but al1 of whose proper divisors have property P, respectively P'. We expect that 11ui and 11vi, both converge and, in fact, that +
for every k but have not been able to find a proof. For primitive abundant numbers, the analogous results and much more is true [4]. Now, consider weird and pseudoperfect nuinbers. An integer is primitive pseudoperfect if it is pseudoperfect but al1 its proper divisors are not pseudoperfect. It seems certain that the number of primitive pseudoperfect numbers not exceeding x is O(xl(1og x),) and, hence, the sum of their reciprocals converges. This we could not prove, but the fact that the density of the pseudoperfect numbers exists follows by the methods of [2]. It is easy to prove that there are infinitely many primitive abundant numbers which are pseudoperfect and, therefore, primitive pseudoperfect. The integers 2 9 , with p a prime such that 2k< p < 2,' l, are easily seen to be primitive abundant and pseudoperfect. In fact, they are practica1 numbers of Grinivasan, Le., every m 5 42%) is the distinct sum of divisors of 2kp. We leave the simple proof to the reader. It is slightly less trivial to prove that there are infinitely many primitive abundant numbers al1 of whose prime factors are large and which are pseudoperfect. We only outline the proof. For every k, let f(k) be the smallest index for which (p, < p2< are the consecutive prime nurnbers) o@, . pAk))2 2pk pAk).
Theorem 3. There exists apositive integer kosuch that, for k > k, the integers
are both primitive pseudoperfect. Note that Bl = 70 which is not pseudoperfect. It appears that this is the only value of k for which Theorem 3 fails, but to prove this might be difficult and would certainly require long computations for Bk and perhaps a new idea for A, We need two lemmas.
Lemma 1. There is an absolute constant c such that every integer m > cp, is the distinct sum of primes not less than p, The lemma is probably well known and, in any case, easily follows by Brun's method.
On Weird and Pseudoperfect Numbers
Lemma 2. There exists un integer ko such that, for every k > koJ
implies that m is the distinct sum of divisors ofAk The same result holdsfor Bt Lemma 2 follows easily from Lemma 1 and from the fact that, for pk 5 x < $ x < Ak, the interval (x, $ x) always contains a divisor of Ak and Bk. (To prove this last statement, we only need that, for E > O, there exists an integer iO(&)such that pi < (1 + &)pifor i > iO(&).) Lemma 2 implies Theorem 3 if we can show +
(12)
O(Bk) 2Bk > Cpk and o(Ak) 2Ak> Cp,.
Statement (12) follows immediately for Blcby a very simple computation if we observe that there is an integer 1, such that, for 1> lo, (1 + l k l +
+
llP1+2)>1 +312pl,
We do not have such a simple proof of (12) for A,. Observe that
where (a, b) denotes the greatest common divisor of a and b. Now, (13) implies (12) if we can show that (o(Ak),A 3 has, for k > ko, at least two prime factors. In fact, we shall prove that ( ~ ( n denotes ) the number of prime factors of n) lim w((o(Ak), Ak)) = co .
kioo
To prove (14), we first observe that, for E > O, there is an integer k0(&)such that, for k > k0(&), (15)
Pf(k) > P:'
This is of course well known and follows fiom the theorems of Mertens. The following theorem now implies (14).
Theorem 4. Denote by g(x) the number of indices ll for which there is un 1, satisfiing
We then have lim,,, g(x) = co . Theorem 4 follows easily from the proof of Motohashi's theorem [5]. It does not follow fiom the theorem of Motohashi but it is easy to deduce by the same proof. Motohashi uses some deep results of Bombieri. Thus, (14) and Theorem 3 are proved. It seems likely that there are infinitely many primitive abundant numbers which are weird but this we cannot prove. We can, however, show that the density of weird numbers is positive.
Part II:Primes
74
It is clear that the weird numbers have a density since both the abundant numbers and the pseudoperfect numbers have a density. (A weird number is abundant and not pseudoperfect.) Hence, we need only show that the density of weird numbers cannot be O. This follows from the following simple lemina.
Lemma. Ifn is weird, then there is an E , > O such that nt is weird if
ProoJ: First define (x)' by
Put
where, in E', d runs over al1 subsets of the divisors greater than 1 of n. If n is deficient or weird, then 6, > 0. If nt is not weird, then there is a set of divisors, greater than 1, of nt for which
From (16) and (17),
which proves the lemma for cn = nd ,/ o ( n ) .
Theorem 5. The density of weird numbers is positive. Now, by the lemmas, ift is an integer and o(t)lt < 1 + E,, then nt is weird. Eut the density of the integers t with o(t)/t < 1 + E , ispositive for any E ~ 0. > Proof: If n is weird, then let E , be as in the proof of the lemma. Now, by the lemma, if t is an integer and a(t)lt 4 1 + E, is positive for any E , > 0. Actually, we proved a slightly stronger result. If n is weird, then the density of (m; n 1 m and m is weirdf is positive. It is easy to see that if n is weird andp is a prime greater than o(n), thenpn is also weird. More generally, the following result holds. Let n be an integer which is not pseudoperfect, i.e., n is deficient or weird. The integer pn is pseudoperfect if and only if there is a set A of proper divisors of n and a set B of divisors of n where no b E E is a multiple ofp, such that
We leave that simple proof to the reader.
On Weird and Pseudoperfect Numbers
75
Finally, we state without proof the following result: Let t 2 O be an integer. The density of integers n for which n + t is the distinct sum of proper divisors of n is positive. On the other hand, the density of the integers n, for which n  t (t > O) is the sum of distinct divisors of n, is O.
References 1. S. J. Benkoski, "Elementary Problem and Solution E2308," Amev: Math Monthly, v. 79, 1972, p. 774. 2. P. Erdds, "Some Extrema1 Problems in Combinatorial Number Theory," Mathematical Essays Dedicated to A. J. Macintyre, Ohio Univ. Press, Athens, Ohio, 1970, pp. 123133. MR 43 #1942. 3. P. Erdds , "Remarks on Number Theory. 111," Mat. Lapok, v. 13, 1962, pp. 2838. (Hungarian) MR 26 #24 12. 4. P. Erdds , "On Primitive Abundant Numbers," J. London Math. Soc., v. 10, 1935, pp. 4958. 5. Y. Motohashi, "A Note on the Least Prime in an Arithmetic Progression with a Prime Difference," Acta Arith., v. 17, 1970, pp. 283285. MR 42 #3030. 6. W. Sierpinski, "Sur Les Nombres Pseudoparfaits," Mat. Vesnik, v. 2(17), 1965, pp. 212213. MR 33 #7296. 7. A. & E. Zachariou, "Perfect, Semiperfect and Ore Numbers," Bull. Soc. Math. Grece, V. 13. 1972, PP. 1222. Originally appeared as: Benkoski, S. J. and P. Erdds. "On Weird and Pseudoperfect Numbers" Mathematics of Computation. vol. 28, no. 126 (April 1974): pp. 617623.
Second Helping: My paper with ~ r d o s The story of how this article came to be is very interesting. 1 had a summer job in the summer of 1969 in San Diego as 1 prepared to go to graduate school at Penn State. 1 was hired to develop software to convert analog data into digital forrn. However, the data did not arrive until the day before 1 left for Penn State. (As you may have guessed, this was a govemment job.) Rather than just sit at my desk and read, 1 decided to try to get a head start on a possible thesis topic. 1 selected three possible problems. They were the Riemann Hypothesis, Femat's last theorem, and perfect numbers. While just fooling around with perfect numbers and related ideas, 1 coined the name weird for a positive integer that was abundant but not pseudoperfect. (To this day, 1 am amazed that this was not defined centuries ago.) 1 investigated these weird numbers and used my programming skills and a
Part II:Primes
76
government computer to find al1 weird numbers less than 100,000. At the end of the summer, 1 left for Penn State and began my studies. The results for weird numbers were in a folder in my files. In late 1970, 1 came across that folder and decided weird numbers should see the light of day. So, 1 sent in a problem to the American Mathernatical MonthZy. It stated the definitions of abundant and pseudoperfect numbers and then posed two questions: Are there any abundant numbers that are not pseudoperfect? (*)Are there any odd abundant numbers that are not pseudoperfect? A couple of months after 1 sent it in, 1 reread the problem and decided that it was a really bad problem. The first question can be answered with paper and pencil in about 15 minutes and 1 did not know the answer to the second part. So, 1 sent a letter to the MonthZy withdrawing the problem. They wrote back and told me they were planning to use the problem and asked me not to withdraw it. The problem appeared in the summer of 1971 without the asterisk. (An asterisk indicates an open problem.) In October, 1 received a letter from Erdds. (Of course, 1 still have that letter.) He said that he and Ernst Strauss had been working on the second question and wanted to know if 1 had found an odd weird number or could prove one did not exist. 1 was chagrined that the asterisk was left off because that implied that 1had the answer. However, Erdds and Strauss missed the fact that 70 was the smallest weird number. 1 wrote back to Erd6s and told him almost al1 1 knew about weird numbers. We sent about 4 or 5 letters. Most of my letters were telling him 1 did not know the answers to the questions he sent. The correspondence ended in the Spring of 1972. In the Fa11 of 1972, Erdds was scheduled to give a colloquium at Penn State. 1 was, of course, planning to attend but assumed he was not interested in weird numbers any more. When 1 arrived at the Math Department, my fellow students told me that the Department Chair was calling every 15 minutes. As soon as Erd6s arrived, he asked to talk to me and kept asking the Chair where 1 was. 1 was assigned to be his "escort" for the next morning. 1 was to arrive at his room by 8:00 and "entertain" him until 10:OO. When 1 arrived, he was still in his pajamas. 1 helped him get dressed. We went to breakfast and talked for over an hour. Most of the time, he asked me math questions related to weird numbers that 1 could not answer. He also asked me about my family and other personal things. He seemed genuinely interested in me. Erdds asked me if 1would like to write a joint paper. Easy question to answer. He also gave me a list of things to accomplish that 1 would do before we published.
1 generated the first draft and sent it to him. 1 put his name as the first author, but he returned it with my name first. 1 submitted the paper to Mathematics of Computation. 1 have published other articles in my career, but this was the only time that the galley proofs were the first thing 1 received from the publisher. Stan
Benkoski, Los Gatos, California
A Heuristic for the Prime Number Theorem Hugh L Montgomery and Ston Wagon
Why does e play such a centzal role in the distribution of prime nurizbers? Siinply citing the Prime Nunlber Theorem (PNT), whiclz asserts that n(x) x/ lnx, is iiot very illuminating. Here ('N'' mealzs "is asyrriptotic to" aizd n(2) is the riirmber of prirries less tlzan or equal tjo x. So wlzy do natural logs appea,r, as opposed to another flavor of logarithm? The problem with an attenipt at a, lzeuristic explanation is that the sieve of Eratostlzexies does not behave as orie niight guess from pure probabilistic consideratioizs. Oize might think that sievirxg oiit, the corriposites under x using prinies up Lo fiwould lead to xIT,,& (1 as an asyniptotic estirnate of the courit of numbers reinsining (the primes up to x; p alcvays represents a prime). But this quantity turns out to be not asymptotic to x/ lizx. For F. Mertens proved in 1874 that tlie product is actiially asymptotic to 2 e?/ ln z, or aboiit 1.121lnx. Thus the sieve is 11% (from 1/ l . 12) more efñcient at eliminating com posites than one miglzt expect . Cornmenting oii t his pheilomenon, which one might cal1 the Mertens Paradox, Hardy arid Wright [5: p. 3721 said: "Considerations of this l\riiicl explain why tlze usiial "robability' ;trgumeiits lead to tbe wrong asymptotic value for ~ ( x ) . "For riiore on this theorern of Merteris and related resiilts in prinie couxiting aee [3; 5; 6, exer. 8.27; 131. Yet there ouglit to be a way to expIa,in,using 01113r eleilzentary rizetliods, why nak~arallogarithuris play a, central role in the distributiori of primes. A good startiizg place is two old theorerris of Chebyshev (1849). N
i)
Chebyshev's First Theorem. Por any x 2 2,0.922/ lnx < n(x) < 1.7x/lnx. Chebyshev's Second Theorern. If n(x)
N
x /log, z, then c = e.
A complete proof of Clzebyshev's First Tlieorem (with sliglitly weaker constarlts) is izot difñcinlt aiid tlie reader is eincoiiraged to reacl the beautiful article by Don Zagier [9]  thc vcry first article evcr publishcd iri tliis journal (see also [l,54.11). The first theoreni tells us that x /lag, x is a reasonable rough approxirna.tion to thc growth of n(x), but it does not distinguish e from other bases. The second theorerri can be given a coniplete proof ixsing orily eleruientary calculus [8].The result is certainly a partial heuristic for the centrality of e since it slzows that, if any logaritlzrn works, then tlie base niust be e. Elarther, onc cari see tlze exact pla,cc iri the proof whcre e ariscs ( S l / z dx = ln x ) . But the lnypothesis for the second theorerri is a strong one; here we will show, by a relatively simplc pr'oof, that tlie samc conclixsion follows from a much weaker hypothesis. Of course, the PNT eliizzinates tlie need for any hypothesis at all, but its proof requires either aii understanding of cornplex analysis or the willingness
78
.

Part 11: Primes
to read the sophisticatetl "eleruieritary poof." The first sirch was found by Erdos aild Selberg; a modern approach appcars i11 [7]. Our presentation liere was inspired by a discussion in Courant and Robbias [2]. We show how their heuristic approacli can be transforrned into a proof of a strong result. So even tliough our original goal w a just ~ to inotivate the PNT, and quite a simple we end up witli a proved tlieoreix thah has a,simple ~ta~teinent proof.
Figure 1: A graph of x/?i(s) shows that the furiction is not pirrely increasing. The upper convex hull of the graph is an increasirig piecewise linear function that is a good approxirriation to x/T(x).
Theorern. If x/?i(x) is asymptotic to an increasing function, then ~ ( x ) x:/ lnx.
N
Figure 1 shows that X/T(X)is assuredly not increasing. Yet it does appear to be asymptotic to the piecewise linear function that is the upper part of the convex huI1 of the graph. Indeed, if we take the c o m x lrlrall of the full infiiiite graph, then the piecewise linear function L ( x ) corresponding to the part of the hull above the graph is increasing (see last section). If one could prove thrtt x/?i(x) L (x)t hen, by the t heorem, the PNT would follow. In fact , using PNT it is not too hard to prove that L(x) is indeed asymptotic to x/?i(x) (such proof is given at tlie encl of this paper). In any case, the hypothesis of tlie theorem is certainly believable, if not so easy to prove, and so the theorem serves as a heuistic explanation of the PNT. Nowadays we can look quite far into the prime realm. Zagier's article of 26 years ago was called The Fzrst Fijty Million Prime Numbers. Now we can look at the first 700 quintillion prime numtters. Not one at a time, perhaps, but the exact value of T (10" is now known for i up to 22; the most recent value is due to Gourdon and Sabeh [4] and is T (4 = 783964159847056303858. Figure 2 is a, loglog plot tliat shows the error when these strakospheric 7i: values are compared to x/ lnz and also the much better logarithmic integral estimate li(x) (which is 1/ lnt dt). N
A Heuristic for the Prime NumberTheorem
Figinre 2: Tlie large dots are tlie absolute vslue of the error when x/ liix is usecl to approxiiriate ?i(x),for x = loX.The smaller dots iise li(z) as the appsoximant.
The proof requires two lern~rias.Tlie first is a consecyuencc;of Chebyshev's First Theorenl, bint ci2~~ be giveri a short and elernentary proof; it states tliat almost al1 nurribers are composite.
Proof. First use an idea, of Cliebyshev to get ~ ( 2 r t ) ~ ( n< ) 2n/ l n n for integers n. Take logbaserh of both sicles of the following to get the rieeded ineqiiality.
This meass that n(2n)  n(n) 5 (1n4)n/ lnn,. Suppose n is a power of 2, say 2" theil suniniing over 2 5 iE K , wliere K is chosen so tliat zK (: n < 2K+', gives
O, wc take n to be the first power of 2 past x, and theil ?i(x)/x 5 27r(n)/n, concluding the proof. By keeping caxefril track of the constarits, tlie preceding proof c:an be used to show that n(x) 8 . 2 ~ lnx, 1 yielding one half of Chebyshev's first tlzeorem, albeit witlz a weaker constant. The seconcl lenirna is a type of Tauberian result, and the proof goes just sliglitly beyoild elemeritary calculus. This lemma is where iiatural logs coine up, well, naturally. For consider the liypothesis witli log, in place of 1x1. Then tlie constniit ln c will cancel, so tlie conclusion will be uncliaiiged!
1. For fiuse a right triangle with legs of lengths 1 and n. For dn2  1 use a right triangle with hypotenuse n and one leg of length l. Originally appeared as: Apostol, Tom M. "Irrationality of the Square Root of TwoA Geometric Proof." American Mathematical Monthly. vol. 107, no. 9 (November 2000): pp. 841842.
Math Bite: lrrationality of J;ñ Harley Flonders
A receiit Gazette article [3] reininded me of Theodor Esterinann's proof of tlie irrationality of As liis proof is not well known, I take the liberty of publicizing it with a slight "generalizatioii." Tlie really iiiteresting thing about this proof is tliat it doesn't use divisibility, just inathematical induction in its "his wellordered forin.
J2.
THEOREM. Suppose m is not a perfeect squnre. l'izen
\im is irrationnl.
Proo . Let n be the integer with n < b < n + l. It suffices to prove tliat  fz ir irrational. Suppose iiot. As 0 < ir < 1, r e have o p / q where O < p < q. We may assuine tliat q is m small as possible (Esterinann's liey idea). Then ir

J;I:
Thus
¿u
is a fraction wit1.i even sinaller denominator, a contradiction.
REFERENCES 1. T. Esterlnann, Tlie irratíonality of fi,Mnth. Gnzette S9 (1975), 110. 2. K. Roth and R. C. Vaugbn, Obituaiy of Theodor Estemann, Bzcll. London Mnth, Soc. 26 (1994), 593606. 3. M.K. Siu, Esterinann and Pythagoras, Mnth. Gnzette 82 (19981, 9293.
Originally appeared as: Flanders, Harley. "Math Bite: Irrationality of &? ." Mathematics Magazine. vol. 72, no. 3 (June 1999): p. 235
A Simple Proof that n is Irrational lvan Niven
Let %=@lb, t;be quatient of positive integers, VVF? define the polynornials
the positive integer n being specified later. Since nlf(z) has integral. coeffcients and terms ía x of degree not fess than n, f ( x ) and Its derivatives f cfi(x) have integral values for x = O; also for $==a a/b, sime =;F(lt/bx)* By elementary calculus we have

fo
tE
 { F ( z )sin  F(z) cos z ) = Fn(z) sin x +F(z) s i n z = f ( ~ sin ) x SE% x
(1)
í(2)
sin zdz =
[F'(2) sin 2
 F(z) cos $1;
= P(w)
+P(0).
+
Naw fin) F(O) is an Znteger, sincefj'(n) anrlftfi(0) are integers, But far O 1 and so after a double flip we see 1 1 a=a,+= a , + , l/ao a, + a, where a, = [l/a,] and a, is the fractional part o f l / a O . Since a is irrational, we can repeat this game forever and discover that 1 @=a,+ 1
where a11 the a,'s are integers and a, > O for al1 n > O. Such an expansion is the continued fraction expansion for a , which we write simply as a = [a,, a,, a,, . . .] so as to allow players to print their expansions on the back of their team jerseys. We often hear fans yell out "partial quotients!" whenever the a,'s make their appearance. If we decide to cal1 a timeout during the continued fraction game, then our halted process would produce the rational number [ao,a,, . . . ,a,], which we denote by p,/q, (where p, and q, are relatively prime). Those who are true number theory mathletes refer to p,/q, as the nth conuergent of a. Lagrange, in 1770, thrilled the fans when he showed that for n > 0, the qn7sappearing "down
124
Part 111: lrrationality and Continued Fractions
under" in the convergents meet al1 the requirements to be named the world charnpion sequence for a. In fact, the denominators q, form the entire team of world champions for a ; for the playbyplay details, see [3] or [S]. By letting some 2 x 2 matrices enter into the arena, we can get a better feel for how the qn's interact with each other, In particular, using induction and some simple linear algebra gymnastics, we can verify the fact that for al1 n 2 0,
If we lob determinants back and forth, we see that pnq,&, pnl q, = ifi 1 and hence we conclude that q,%,and q, must always be relatively prime. Although consecutive players do not like to share common factors, the matrix product does reveal that any three consecutive members of the team can play together in the sense that These two observations are crucial as sequences prepare for the Olympic Games, 3, TRAINING TO BE THE BEST: HOW TO SHED UNWANTED TERMS. Let's
now tackle our question: Within every increasing sequence of integers, is there a subsequence that has what it takes to be the complete team of world champions for some irrational number? Sadly, the answer is "no": There is no subsequence of 2,4,6,8,10,12, . . . that can be a world champion sequence since, as we9veseen at the end of the previous section, consecutive members froin a team of world champions must be relatively prime. Thus there can never be a world champion sequence in any sequence of integers for which, from some point onward, al1 the terms share a common factor. Plainly we should not bother to consider such pathetic sequences that cannot make even the first cut. Unfortunately, there also are 'nontrivial' sequences that never can make it to the Olympic Games, Consider, for example, the sorry sequence beginning with The terms in this sequence were carefully recruited so as to satisfy an ever growing list of anonymous congruences (sponsors who wish not to be mentioned here). Notice that in the first ten terms, there does not exist a triple r < s < t such that t = as + r for any positive integer a. Thus in view of the lineup from (2.21, we see that the first ten terms in (3.1) do not contain even three players from a world champion team. By our secret recruiting process, this pattern continues for the entire roster of terms in the listah, the agony of defeat. We now bring on some sequences that are better known by the fans. First, let's have sequences generated by polynomial functions take the field. Theorem 3. Let f( x ) be a nonconstant polynornial with integer coefiients whose leading coejjicient is positive. Then there exists a sequence of integers n,, n2,n,, . . . such that f (n,), f (n,), f (n,), .. . is a complete world champion sequence for some irrational number if and only if there exist integers n, and n, such that

Proof: If for al1 i r 1, f(ni) = qi represents a team of world champions of some irrational number, then, as qo = 1,we must have O < q1 < q2 and q, = a2qr+ l. Thus we see that O < f(n,) < f(n,) and f (n,) 1 mod f(n,).
125
Diophantine Olympics and World Champions
1 mod f(n,). We set Conversely, suppose that O < f(n,) < f(n,) and f(n,) a, = f(nl) and let a, be the positive integer such that f(n,) = a, f(n,) + 1. Let's now assume that n,, n,, . . . , n, have been defined, are warmed up, and are ready to play, where I L 2. From the benches, we now select a positive integer c,,, that is so large that if n,,, is defined by n,,, = c,, f(n,) + n,, ,then f(n,) < f(n,+, 1. Such integers c,,, exist since f ( x ) tends to infinity as x pumps up. Notice that
,
f(nr+,) = f(c,+,f(n,) + nr1)  f ( n r  1 ) mod f ( n 1 ) . Therefore there exists a positive integer, say a,,,, such that f(n,+1) = ar+,f(nr) +f(n,,> Thus if we let qi = f(ni) for al1 i 2 1, then the qi9s are the team of world champions for the irrational number [O, a,, a,, a,, . . .] and we've won the game. m As an immediate consequence of Theorem 3, we see that there are irrational numbers whose world champion sequences contain only perfect squares; there are other irrationals whose world champion sequences contain only cubes, or for that matter, any power. Coxzsider, for exarnple, the number cx = O ,75994513286162937685173771612208505499708539223856599896303745553., . = [O, 1,3,6,29,739,538810,290287122557,84266613096281243920895,. .l. The first few world champions for a! are given in Table 2.
It is immediately apparent to any calculator that al1 the entries in the right column are indeed perfect squaresthus those " . . "S can be replaced by real, redblooded digits to produce an a! that has only perfect square world champions! Another potentially arnusing example can be found if we take on the polynomial f ( x ) = Ax 1, for some integer A > O. Selecting n, = 1 and n, = A 1, we immediately conclude that there exist real numbers a! such that each element q, 1 rnod A. Thus there are complete of its world champion sequence satisfies q, teams of world champions agile enough to dodge having a particular factor. In this spirit of dodging factors, we now describe a winning strategy for a similar game involving the ever popular and timeless team of prime nurnbers.
.
+
+
Theorem 4. There exist irrational numbers a that haue only prime numbers as their world champions.
P~oo$ As always, we set qo = 1. Next, we set q, = 2 and q, = 3, so a, = 2 and a, = 1. Suppose now that the primes q, < q, < < q, have al1 been defined for I 2 2. We now consider the arithmetic progression (Aq, + qInl: A = 1,2, . . 1, and a * .
Part III: lrrationality and Continued Fractions
126
apply another important result of Dirichlet, which states that if r and s are relatively prime positive integers, then the arithmetic progression r + S,2r S,3r + S,. . . contains infinitely many primes (see [4] for an instant replay of this major AP upset). Thus we know that there exists a positive integer A, cal1 it a,,,, such that a,, q, + q,, is a prime, let's name it q,,, . Therefore if we let a = [O, a,, a,, a,, . . .1, then its world charnpion sequence consists solely of prime ¤ numbersthis places us right in the middle of the winner's circle. As an illustration, we now introduce the number
+
,
a = 0+38547782732324065153134100625493772881752720832373553581742207176582. .. =
[0,2,1,1,2,6,2,10,18,20,16 ,...]
and its first ten world champions:
One doesn't really require Olympiclike factorization skills to verify that the champions in Table 3 are al1 prime numbers. Finally we remark that in the proofs of Theorems 3 and 4 we are able, without the use of steroids, to make the world champions grow as fast as we wish. This observation in turn implies that the partial quotients, a,, in the continued fraction expansion for the associated irrational a can grow at record breaking speeds (in fact we saw this particular event live during our perfect square example). It turns out that if there is a subsequence of un's that grow amazingly fast, then the associated number a must, in fact, be .a transcendental number. This remarkable fact follows from a record setting 1844 result due to Liouville, who showed that algebraic numbers cannot be approximated too well by rational numbers whose sizes "down under" are modest; see rJ] or [S] for flashbacks to this historymaking score. Thus we close our games with the commentary that we may find transcendental numbers that accomplish al1 that is demanded of them in both Theorems 3 and 4. In fact, the a debuting just after Theorem 3 is transcendental. 4. THE 2004 OLYMPICS: CAN OUR FAVOMT'E CHAMPS ARISE FROM THE BAD? With any pursuitathletic or intellectualwe should always look ahead toward challenges for future thrillseekers. Thus in our closing ceremonies we look ahead to the next Olympic Games and hope to inspire others to go for the gold. The a's that are able to give birth to interesting world champions as described in Theorems 3 and 4 can have arbitrarily large a, values in their continued fraction expansions. 1s it possible to find an a that satisfies either theorem and for which al1 its partial quotients are bounded? Numbers a having bounded partial quotients are known as badly approximable numbers. This title has been awarded since it can
Diophantine Olympics and World Champions
127
be shown that a number cr has bounded partial quotients if and only if (2.2) cannot be improved in the sense that there exists a constant c = c ( a ) > O such that 24 < llaqll for all integers q; see [3] or [S]for the proof of why these numbers deserve the name bad. A cornpletely new game plan would be required if one wanted to attempt to show that there are badly approximable numbers whose world champions satisfy Theorems 3 or 4. In the proof of Theorem 3, the partial quotients are born and bred to race off at record speeds to infinity. 1s there another training technique that prevents the partial quotients from running away? To adopt the strategy of the proof of Theorem 4, one would, at the very least, need to know that there exists a constant C such that each arithmetic progression of the form {Ar s : A = 1,2,. . .}, where gcdfr, S ) = 1, contains a prime p S Cr. Such an assertion appears to be ridiculously optimistic as the world recordholder in this direction is HeathBrown [2] who in 1992 nearly caused a riot among fans when he produced the startling result that every arithmetic progression {Ar + s : A = 1,2,. ..) with gcd(r, S) = 1 contains a. prime p S CrSS. The previous world champion exponent was a whopping 13.5, found by Chen and Liu [l] back in 1989. The exponent on r is known as Linnik's constant. These closing remarks may invite both the number theory athlete and fan to train and take on the challenge of showing that there do not exist badly approximable numbers whose world champions are al1 perfect squares or are al1 primestwo potentially difficult goals, but certainly in the true tradition of the Olympic spirit.
+
Figure 2. The author overlooking Sydneythe site of the 2000 Olympic Games, where he was inspired to consider turning sequences into world charnpions.
128
Part III: lrrationality and Continued Fractions
ACKNOWLEDGMENTS, The remarks and observations made here were inspired while the author was a Visiting Fellow at Macquarie University, "down under" in Sydney, Australia. He thanks the Mathematics Department for its warm hospitality. REFERENCES 1. J. R. Chen and J. M Liu, On the least prime in an arithmetical progression. IV, Sci. China Ser. A 32 (1989) 792807. 2. D. R. HeathBrown, Zerofree regions for Dirichlet Lfunctions, and the least prime in an arithmetic progression, Proc. London Math. Soc. (3) 64 (1992) 265338. 3. E. B. Burger, Exploring the Number Jz~ngle:An Interactiue Joumey into Diophantine Analysis, AMS Student Mathernatical Library Series, Providence, 2000. 4. 1. Niven, H. Zuckerman, and H. Montgomery, An Iiztroduction to the Theory of Numbers (5th Ed.), Wiley, New York, 1991. 5. W. M. Schrnidt, Diophantine Approximation, Springer Lecture Notes in Mathematics 785, Springer, New York, 1980.
Originally appeared as: Burger, Edward B. "Diophantine Olympics and World Champions: Polynomials and Primes Down Under." American Mathematical Monthly. vol. 107, no. 9 (November 2000): pp. 822842.
An Elementary Proof of the Wallis Product Formula for Pi johan Wastlund
1. THE VVALLIS PRODUCT FORMULA. In 1655, Johii Wallis wrote down the celebrated forrn~~la
Most textbook proofs of (1) rely 011 evaluation of some definite integral like 11j2
(sin i) 1. This is true if b  x  y  z >  4, or, equivalently, if x + y + z < b + 4. The maximum value of x + y + z subject to the constraint and the inequality 3a < b2 + 2b + 4 implies that n + y + z 5 (3) is < b + 4. This proves the lemma. Theorem l. Let m 2 3 and n 2 120m. Then n is the sum of m i1 polygonal numbers of order m + 2, at most four of which are differentfrom O or l. Proof: Let b, and b2 be consecutive odd integers. The set of numbers of the form b + r, where b E (b,, b2} and r E {O, 1, .. ., m  31, contains a complete set of residue classes modulo m, and so n b + r (mod m) for some b E {bl,b2) and r E {O, 1, ..., m  3). Define
Then a is an odd integer, and
4
If O < b < $ +
and so b2 < 4a. Similarly, if b > of the interval
,then the quadratic formula implies that
4+, J
then 3a < b2 + 26 + 4. Since the length
is greater than 4, it follows that I contains two consecutive odd positive integers b, and 6,. Thus, there exist odd positive integers a and b that satis@ (5) and the inequalities b2 < 4a and 3a < b2 + 2b + 4. Cauchy's Lemma implies that there exist S , t, u, v satisQing (1) and (2), and so
This completes the proof. Note that this result is slightly stronger than Cauchy's theorem. Legendre [6] proved that every sufficiently large integer is the sum of five polygonal numbers of order m + 2, one of which is either O or 1. This can also be easily proved. Theorem 2. Let m 2 3. I f m is odd, then every suflciently large integer is the surn offour polygonal nurnbers of order m + 2. Ifrn is even, then every suflciently large integer is the surn offivepolygonal numbers of order m + 2, one of which is either O or 1. Proof: There is an absolute constant c such that if n > cm3, then the length of the
A Short Proof of Cauchy's Polygonal NumberTheorem
151
interval I defined in (6) is greater than 2m, and so 1 contains at least m consecutive odd integers. If m is odd, these form a complete set of residues inodulo m, and so n b (inod m) for some odd number b E 1. Let r = O. Define a by formula (4). If m is even and n > cm3, then n b + r (inod m) for some odd integer b E I and r E {O, 1). Define a by (4). In both cases, the theorem follows immediately from Cauchy's Leinina.
References 1. A. Cauchy, "Démonstration du théoreme général de Fermat sur les nombres polygones," Mém. Sci. Math. Phys. Inst. France (1) 14 (181315), 177220
=
Oeuvres (2), vol. 6, 320353. 2.
L. E. Dicltson, "Al1 positive integers are sums of values of a quadratic function of x," Bull. Amev: Math. Soc. 33 (1927), 713720.
3. P. Fermat, quoted in T. L. Heath, Diophantus ofAlexandria, Dover New Yorlt, 1964, p. 188. 4.
C. F. Gauss, Disquisitiones Arithrneticae, Yale Univ. Press, New Haven, Conn., and London, 1966.
5. J. L. Lagrange, "Démonstration d'un théorkme d'arithmetique," Nouveaux Memoires de L'Acad. Royale des Sci. et BellesL. de Berlin, 1770, pp. 123133
=
Oeuvres,
vol. 3, pp. 189201. 6. A. M. Legendre, Théorie des Nombres, 3rd ed., vol. 2, 1830, pp. 33 1356. 7.
G. Pall, "Large positive integers are sums of four or five values of a quadratic function," Amev: J. Math. 54 (1932), 6678.
8. T. Pepin, "Démonstration du théorkme de Fermat sur les nombres polygones," Atti Accad. Pont. Nuovi Lincei 46 (189293), 1191 3 1. 9. J. V Uspensly and M. A. Heaslet, Elementary Number Theory, McGrawHill, New York and London, 1939. 10. A. Weil, Number Theory, An Approach Through History from Hammurabi to Legendre, Birlchauser, Boston, Mass., 1983.
Originally appeared as: Nathanson, Melvyn B. "A Short Proof of Cauchy's Polygonal Nuinber Theorem." Proceedings of the AMS. vol. 99, no. 1 (January 1987), pp. 2224.
Genealogy of Pythagorea'nTriads A. Hall
The infinite set of primitive Pythagorean triads may be shown to form a symmetrically organised family,,inwhich each triad has three offspring, the progenitor being (3,4,5). The first three generations are shown below. The offspring of any triad (x, y, z) are, in the order shown,
If x = m2 n2,y = 2mn, z = m2 + n2, the triad thus derived fiom (m, n) gives rise to triads derived from (2m  n, m), (2m + n, m) and (m + 2n, n). If m and n are coprime and of unlilte pariS) then these pairs are also coprime and of unlike parity. This ensures that every triad in the family is a primitive triad.
Part IV:Sums of Squares and Polygonal Numbers
154
It remains to be shown that if M and N are coprime and of unlilte parity, with M > N, then the triad derived from (M, N)has its place in the family. There are three possibilities: (a) N < M < 2 N (b) 2N< M < 3 N (c) 3N < M
Letm=N, n=2NM, then M=2mn, N = m. Letm=N, n=M2N; thenM=2m+n, N = m . Letm=M2N, n = N ; thenM=m+2n, N = n .
In every case, m > n, m and n are coprime and of unlilte parity, and m + n < M + N. In every case, Mand N fit the formulae for offspring of (m, n). This process may be repeated indefinitely, with the surn of m and n diininished each time, leading back inevitably to (2, 1). The family tree is therefore a complete representation of the infinite set of primitive Pythagorean triads. It is interesting to trace certain important lines of descent. The central line contains al1 triads in which x and y are consecutive integers. These were discussed in Classroom Note 147. The extreme top line contains al1 triads in which y and z are consecutive integers, while the extreme lower line contains al1 in which x and z are consecutive odd nuinbers. Further sequences may be traced by alternating branches up, across and down (U, A and D) : UA UA ... and A UA U . .. contain triads for which m and n are in the Fibonacci sequence 1, 1,2,3,5,8, 13, .... In these triads, x and z are alternately members of the same sequence. The smaller acute angle tends alternately towards tan' and sin' DUDU ... gives the other sequence of triads mentioned in Classroom Note 147, representing triangles in which the hypotenuse and twice the shortest side are consecutive integers, thus tending to f o m half an equilateral triangle. UDUD ... tends to produce the same type of triangle. DADA ... and ADAD ... tend to produce triangles similar to those produced by UA UA ... and AUAU ..., and this symmetrical tendency in lines of descent seems to apply generally. The difference between x and y in any triad is equal to either the difference or the sum ofx andy in the "parent triad." For this reason, the difference between the two shorter sides of any primitive Pythagorean triangle must be either 1 (the difference of 3 and 4) or the sum of the shorter sides in another primitive Pythagorean triangle. The possible differences are therefore: 1, 7, 17, 23, 3 1, 41, 47, 49, .... It was the investigation of these, possible differences, suggested by Mr. P. 1. Wyndham, which led to the results in this note.
3.
Originally appeared as: Hall, A. "Genealogy of Pythagorean Triads." Mathernatical Gazette. vol. 54, no. 390 (December 1970), pp. 377379.
Part V: Fibonacci Numbers
One of the joys of studyiiig number theory is investigating the properties of special numbers that possess almost rnagical qualities. Perhaps no numbers have been subjected to greater scrutiny, and deservedly so, than the Fibonacci numbers: 1, 1, 2, 3, 5, 8, 13,21,.... Numerous books have been written about these beautiful numbers and there even exists a research journal, The Fibonacci Quarterly, that is devoted to exploring their special properties. In the first article in this chapter, "A dozen questions about Fibonacci numbers" (Math Horizons, vol. 12, no. 3 (Februaiy 2005) pp. 59), James Tanton presents more than a dozen questions (somewhere between 13 and 2 1) whose answers are Fibonacci numbers. Many of the questions are combinatorial, but some involve probability, "Fibodecimals," divisibility patterns, and a simple derivation of Binet's formula that expreses Fibonacci numbers in terms of an irrationallooking formula involving & and the golden ratio. In "The Fibonacci numbersexposed" (Math. Magazine, vol. 76, no. 3 (June 2003), pp. 167181), Dan Icalman and Robert Mena convincingly argue that the Fibonacci numbers are not al1 that special. Because they belong to a class of sequences, nainely those satis@ing a second order linear recurrente with constant coefficients, nearly al1 of the beautiful formulas and identities satisfied by the Fibonacci and Lucas numbers are special cases of equally beautiful formulas satisfied by al1 sequences in the class. In addition to the Fibonacci and Lucas numbers, this class contains al1 constant sequences, al1 arithmetic progressions, the Fermat sequence, the Mersenne sequence, the repuiiit nuinbers, and more. Using difference operators acting on the real vector space of real sequences, matrix algebra, and Binetlike formulas, they establish generalizations of Fibonacci formulas lilte
and gcd(Fn, Fm) = Fgcd(n, m), to name a few. In a companion article, "The Fibonacci numbersexposed more discretely" (Math. Magazine, vol. 76, no. 3 (June 2003), pp. 1821 92), Arthur Benjamin and Jennifer Quinn show how al1 of the generalized identities can also be obtained by elementary counting arguments. Specifically, Fibonacci numbers count the ways to tile strips of a given length with squares and dominoes. To obtain the generalized versions, one needs only to add a splash of color to these combinatorial arguments.
A Dozen Questions about Fibonacci Numbers
In his famous 1202 text Liber Abaci the great Leonardo of Pisa, a.k.a. Fibonacci, poses, and solves the following rabbit breeding problem: Find the number of rabbitpairs present in any month, iJJ starting from a single pail; each pairs of rabbits born one month produces another pair of rabbits for each month after the next. The count of rabbit pairs from monthtomonth gives the famous Fibonacci sequence 1, 1,2,3,5,8, 13,21,34,55,89, .... If Fn denotes the nth Fibonacci number, then we have Fn = Fn  + F,  with Fl = F2 = 1. (Surprisingly it was 17th century Dutch mathematician Albert Girard who first wrote down this recurrente relation, not Fibonacci.) Any problem whose "nth case" solution is the sum of the two previous case solutions gives rise to the Fibonacci (or at least a Fibonaccilike) sequence. For instance, the number of rabbit pairs in any month equals the number of rabbits present the previous month, plus the offspring of al1 the rabbit pairs that were present two months before. The number of ways to climb a set of stairs one or two steps at a time is a Fibonacci number as is seen by considering separately the possibilities of starting with a single step or with a doublestep. The Fibonacci numbers possess astounding mathematical properties and new results about them are still being discovered today. Like many a scholar, 1 have become intrigued by the mathematical delights of the Fibonacci numbers. Here, for your amusem*nt, is a collection of some of my favorite Fibonacci tidbits, some classic, some new. 1 hope you enjoy thinking about them as much as 1 did.
Figure l. The three ways to tile a 1 x 3 strip using squares and dominoes.
Question 1: A Tiling Classic Using only 1 x 1 square tiles and 1 x 2 dominoes one can tile a 1 x 3 strip of squares three different ways, as in Figure 1. In how many different ways can one tile a 1 x 15 strip of squares using only square tiles and dominoes? How many of these tilings have a single domino covering the 6th and 7th cells of the strip? How many don't?
Part V: Fibonacci Numbers
Question 2: Honeycomb Walk A bee, starting in cell one of the simple honeycomb design shown in Figure 2, wishes to stroll to cell number eleven via a path of connected cells. Each step of the journey must head to the right (that is, the bee can only move from one cell to a iieighboring cell of a higher number). In how many different ways could the bee travel from cell one to cell eleven? In general, how many different paths are there fiom cell one to cell N?
Figure 2. How many ways can a bee walk from cell one to cell n?
Question 3: Brdered Partitions a) Apartition of a number N is any collection of positive integers that suin to N. If the order of the terms in a sum is considered important, then we say that we have an ordered partition of N. For example, there are four ordered partitions of the number 3, namely, 1 + 1 + 1, 1 + 2 , 2 + 1, and 3 itself. How many ordered partitions are there for the number 5? Find a formula for the number of ordered partitions of a positive integer N. b) Sally is particularly fond of the number one and liltes to use either a blue crayon or a black crayon to write this nuinber. (Al1 other numbers she writes in black pen.) Sally noticed that with two different types of one there are now thirteen different ordered partitions of the number 3 :
Find the number of ordered partitions of the number 5 with two different types of one. How many such partitions are there of a number N?
Question 4: "ABABA" The language of "ABABA" uses only two letters: A and B. No word in this language contains two consecutive Bs, but any string of letters avoiding two neighboring Bs is indeed a word. For example, "AABAAAAB" and "BAA" are both words, but "ABBA" is not. How many 10lettered words are there in this language? How many Nlettered words does ABABA possess?
Question 5: '"ABEEBA" Another language, called "ABEEBA," uses three letters of the alphabet: A, B, and E. No word in this language contains an "A" immediately followed by an "E," but al1 other
A Dozen Questions about Fibonacci Numbers
159
combinations of letters avoiding this situation do indeed form words in this language. For instance, "ABBBEAA" is a word, but "BBAEA" is not. Count how many 1, 2, and 3lettered words this language possesses. What do you notice? How many Nlettered words are there in this language?
Question 6: Restricted Permutations There are tlwee ways to rearrange the letters ABC so that each letter, if it moves, shifts at most one place to the left or at most one place to the right. These permutations are: ABC, ACB, and BAC. (Notice, in "CAB" for instance, the letter C has moved two places to the left.) Let's cal1 a rearrangement of letters satisQing this rule a "restricted perrnutation." How many restricted pemutations are there of a string of N letters?
Question 7: Avoiding Heads If 1toss a coin ten times, what is the probably that 1won't see two heads in a row?
Question 8: "Fibodecimals" Consider the decimal 0.11235955056 ... obtained by adding the Fibonacci numbers expressed as the nonzero parts of smaller and smaller decimals:
Notice that in calculating this infinite sum, one must "carry digits" an infinite number of times. Prove, that once al1 the digits have been carried, the resulting decimal is a repeating decimal.
Question 9: Divisibility Patterns? Three is a factor of six, and F3 = 2 is a factor of F6 = 8. Seven is a factor of twentyone, and F, = 13 is a factor of FZ1 = 10,946. Fourteen is a factor of fiftysix and, lo and behold, F,, = 377 is a factor of FS6= 225,85 1,433,717. 1s this a coincidence, or is it always the case that if a divides b then Fa divides Fb?
Part V: Fibonacci Numbers
Question 10: Foul ABABA Any word in the language of ABABA (Question 4) that begins and ends with an A is actually a swear word in the language. For instance, "A," "AA," and "ABA" are al1 swear words, as is the name of the language itself. How many Nlettered swear words are there? How many of these Nletter swear words possess precisely k Bs? Use foul ABABA to prove:
(Interpret the binomial coefficient
(2) = as equal to zero if a < b.)
Question 11: The Joy of Subsets a) How many subsets of {1,2,3,..., N) contain no two consecutive numbers? b) How many subsets (1, 2, 3,. . ., N) consist only of pairs of consecutive numbers? (By this, we mean that the elements of the subsets can be subdivided into disjoint pairs, with each pair containing consecutive numbers. For example, {1,2,4,5,8,9) is such a subset of {1,2,3,..., lo}, but (4, 5,6, 8,9) isnot.)
(c) If S is a subset of { 1,2,3,...,N), let "S+ 1" denote the correspondingset with "1" added to each of the elements of S. For instance, if, S= {1,4,5,8),then S+ 1 = (2,5,6,9). How many subsetsSof(1,2,3,..., N)havethepropertythatSU(S+l)={1,2,3 ,..., N , N + l ) ? (For example,therearefivesuchsubsetsof(1,2,3,4,5),namely,{1,3,4,5), {1,3,5), {1,2,4,5), {1,2,3, S ) , and (1,2,3,4,5) itself.)
Question 12: A Fibonacci Power Sequence a) Show that there are two distinct numbers x and y with the property that the corresponding sequences of powers 1, x, x2,x3,x4,... and 1,y, y2,y3,y4,... each behave like the Fibonacci sequence (namely, that each term in the sequence, except the first and the second, is the sum of the two preceding terms). b) Use this to find a formula for the nth Fibonacci number!
Answers, Comments, and Further Questions 1. Consider the general situation first. Set T(N) to be the number of ways to tile a 1x N strip of squares using only square tiles and dominoes. Clearly, T(l) = 1 and T(2) = 2. We have also seenthat T(3) = 3. Considernow the challengeoftiling a 1 x N strip for N > 3. There are two ways to start. Using a square tile first leaves the challenge of tiling N  1 spaces with more square tiles and dominoesthere are T(N  1) ways to do thiswhereas starting with a domino first leaves N  2 spaces to tile, which can be done in T(N  2) different ways. Thus a 1XN strip can be tiled in T(N) = T(N  1) + T(N  2) different ways.
A Dozen Questionsabout Fibonacci Numbers
161
As this sequence of tiling numbers starts as the sequence of Fiboiiacci numbers (with index shifted by one), and satisfies the same recursive relation as the Fiboiiacci nuinbers, then it must be the case that the sequence continues to match the Fibonacci numbers. We have then that T(n) In particular, T(15) = F16= 987. Placing a domino in the 6th and 7th squares of a 1 x 15 strip divides the strip into two pieces, one five cells long, and the second eight cells long. These can be tiled, respectively, F6 = S and F, = 34 different ways, yielding 8 x 34 = 272 tilings in al1 for the 1 x 15 strip with a domino in that position. Any tiling that lacks a domino in this position has a "break" between the 6th aiid 7th positions and so can be regarded as a tiling of a 1x 6 strip adjoined with a tiling of a 1 X 9 strip. There are F7 X Flo = 13 X 55 = 715 such tilings.
= O, Ak+l = uAk bAkz, so p is a divisor of Ak,. By induction, p divides both A. and Al, and therefore A,, for al1 n > 0. OBSERVATION 4. rpositive integers h and k are relatively prime, then so are FI, and Fk.
Proqf: If p is a prime divisor of F,? and Fk, then by Observation 2, p is not a divisor of b. Since h and k are relatively prime, there exist integers r and s such that r h sk = 1. Clearly r and s must differ in sign. Without loss of generality, we assume that r < 0, and define t = r. Thus, sk  t h = 1 . Now by Observation 1, Fskis divisible by Fk, and hence by p. Similarly, FtI, is divisible by FI,, and hence, also by p. But FtI,and Fskare consecutive terms of F , so by Observation 3, p is a divisor of al1 F,. That is a contradiction, and shows that FI,and Fkcan have no common prime divisor.
+
OBSERVATIQN 5. I f a' = ~ prime.
f 'und " b' = (b)k, then a' and b' are relatively
ProoJ: Suppose, to the contrary, that p is a comrnon prime divisor of a' and bi. Then clearly p is a divisor of b, and also a divisor of L:'"', which equals b~i?:' F$:) by (5). This makes p a divisor of FE:', which contradicts Observation 2.
+
Wlth these observations, we now can prove the
. The gcd qf F,, and F, is Fk, where k is the gcd of m and n. THEOREM Proqfi Let s = m/ k and t = n / k, and observe that s and t are relatively prime. We consider A = F = Fo,Fk, FZk,. . AS discussed earlier, A can also be expressed as Fk where a' = Lk and b' = (b)k. Moreover, by Observation 5 , a' and b' are relatively prime. As in Observation 1, we see at once that every A is a multiple of Fk, so in particular, Fk is a divisor of A, = Fks= F,?, and A, = Fkr= F,, . On the other hand, Fn,/Fk= F,'U'.~') and F,/Fk = F:~'*~",are relatively prime by Observation 4. m Thus, Fk1s the gcd of F,, and F,,. ~ ( " 3 " '
Severa1 remarks about this result are ín order, First, in Michael [18], the corresponding result is established for Lhe traditional Fibonacci numbers. That proof depends on the R(1, 1) instances of (19), Observation 1, and Observation 3, and extends to a proof for R ( a , b) in a natural way. Second, Holzsager [lo] has described an easy construction of other sequences A, for which gcd(A,,, A,,) = Agcd(m,n). First, for the prirnes ~ k define , A,, = qk where the qk are relatively prime. Then, extend A to the rest of the integers rnultiplicatively. That is, if n = pr' then A, = q,:' . Such a sequence defines a mapping on the positive integers that carries the prime factorization of any subscript into a corresponding factorization involving the qs. This mapping apparently will commute with the ' ) relatively prime, but since F2 = a and gcd. By Observation 4, the terms F ~ T are F4 = a3 2ab, the F mapping is not generally multiplicative. Thus, Holzsager's constmction does not lead to exarnples of the form F ( ' * ~ ) . Finally, we note that there is similar result for the ( a , 0)Lucas numbers, which we omit jn the interest of brevity. Both that result and the preceding Theorem also appear in Hilton and Pedersen [S]. Also, the general gcd result for F was known to Lucas, and we may conjecture that he knew the result for L as well.
n
+
n
The Fibonacci NumbersExposed
In particular and in general We have tried to show in this paper that rnuch of the rnystique of the Fibonacci numbers is misplaced. Rather than viewing F as a unique sequence with an amazing host of algebraic, combinatorial, and number theoretic properties, we ought to recognize that it is simply one example of a lalge class of sequences with such properties. In so arguing, we have implicitly highlighted the tension within rnathernatics between the pasticular and the general, Both have their attractions and pitfalls. On the one hand, by focusing too narrowly on a specific amazing example, we rnay Iose sight of more general priilciples at work. But there is a countervailing risk that generalization may add nothing new to our understanding, and result in rneaningless abstraction. In the case at hand, the role of the skip operator should be emphasized. The proof of the gcd result, in particular, was siinplified by the observation that the skip rnaps one R ( a , b) to another. This observation offers a new, simple insight about the terms OS Fibonacci sequencesan insight impossible to formulate without adopting the general f'ramework of twoterm 1ecursences. Xt is not our goal here to malign the Fibonacci nutnbers. They constitute a fascinating example, rich with opportunities for discovery and exploration. But how much more fascinating it is that an entire world of such sequences exists. This worid of the super sequences should not be overlooked.
KEFERENCES 82 ( 1980). 277787. 1. Wiili¿iiti Woirlger. Pythugor;t+Meeks Fihoi~ncci.ildotllr~iirtitic IPr~rrr+lrt~/ 7. Ciil.1 H. I3oy~t;/1 NI\IO/.Sof'n/lrrfhc>/il~tr(.,\, It~tli* 0, I;,,= .f;,l rout~tstlzcí 1 ~ ~ ~ 1ofb ~*oloi*cd or (H  1)lilings (of a 1 x (n  1 ) hourd) wiill syu(rrcJ,rar~ddoxninoe,~~~lzert. ihore are a colovs f o r squarc.,sand 6 colop:~ ,for donzirloes. Using Theorcm 1, equations (2) through (6) can be derived and apprcciatcd combinatorially. In most of these, our combinatorial proof will simply ask a question and answer it two different ways. For instante, if we apply Theorem 1 to equation (2) and reindex by replacing n by n 1 and m by m 1, we obtain
+
+
IDENTITY l..
For 0 5 m
( a,
f n
= finfnm
+ hj;lr~JJ;zmi
Question: How many ways can a board of length n be tiled with colored squales and dominoes? Answer 1: By Theorem 1, there are ,j;, colored ntilings. Answer 2: Here we count how many colored ntilings are bweakable at the mth cell and how many are not. To be breakable, our tiling consists of a colored mtiling followed by a colored (n  nz)tiling, and there are f,, f,,, such tilings. To be unbreakable at the mth cell, our tiling consists of a colored (m  1)tiling followed by a colored domino on cells m and m 1, followed by a colsuch tilings. Altogether, there are ored (n  m  1)tiling; there are bf,, j;,,nl fnl fawln b*f,l .f,,,~ colored ntilings.
+
+
Since our logic was impeccable for both answers, they must be the same. The advantage of this proof is that it makes the identity memorable and visualizable. See FIGURE1 for arn illustration of the last proof.
The Fibonacci NumbersExposed More Discretely
ntilui~sbreakable at oell m:
ntilings unbreakable at cell tn:
Figure 1 A colored ntiling is either breakable or unbreakable at cell m
Equation (3) can be rewritten as the following identity.
Question: How many colored ntilings exist, excluding the tiling consisting of al1 white squares? Answer 1: By definition, f ; ,  1. (Notice how our question and answer become shorter with experience!) Answer 2: Here we partition our tilings according to the last tile that is not a white square, Suppose the last tile that is not a white square begins on cell k. If k rz, that tile is a square and there are a  1 choices for its color. There are fn1 colored tilings that can precede it for a total of (a  1).fi,, tilings ending in a nonwhite square. If 1 5 k 5 n  1, the tile covering cell k can be a nonwhite square or a domino covering cells k and k 1. There are a b  1 ways to pick this tile and the previous cells can be tiled .fk, ways, Altogether, there are (a +. b  1)f k W 1 colored ntilings, as desired. (a  l)f,,,

+
+
+
Notice how easily the argument generalizes if we partition according to the last tile that is not a square of color 1 or 2 or . . . or c. Then the same reasoning gives us for any Iscca,
Likewise, by partitioning according to the last tile that is not a black domino, we get a slightly different identity, depending on whether the length of the tiling is odd or even:
After applying Theorem 1 to equation (4) and reindexing (n + n IDENTITY3. For n 3 0,
+ 1) we have
Part V: Fibonacci Numbers
186
Question: In how many ways can we create a colored ntiling and a colored (n 1)tiling? Answer 1: fn fn+, . Answer 2: For this answer, we ask for O 5 k 5 n, how maily colored tiling
+
pairs exist where cell lc is the last cell for which both tilings are breakable? (Equivalently, this counts the tiling pairs where the last square occurs 011 cell k 1 in exactly one tiling.) We claim this can be done a f 2 b n  h a y s , since to coilstruct such a tiling pair, cells 1 through k of the tiling pair can be tiled ways, the colored square on cell k 1 can be choscn o ways (it is in the ntiling if and only if iz  k is odd), and the remaining 217  2k cells are covered 2. Altogether, there are with n  k colored dominoes in b"k ways. See FIGURE  f ? b "  ~tilings, ~ as desired. Lr
+ fl
+
Figure 2 A tilinf: pair where the last m ~ ~ ~ t r abrealplicatiorzsto the divisor prohleni c?f Dirichlet and Piltz, Proc. London Math. Soc. [2] 21 (1922), 3974. [20] G. H. Hardy and J. E. Littlewood, The al~l~roxir~~ate~fi~nc'tional equatioíw,for ((S) aízd r2(s), Proc. London Math. Soc. [2] 29 (1929), 8 187. 1211 D. R. HeatliBrown, The afi,~irth poki1eriizoment qf tl~eRierilaniz zeta ,fiu~ctioiz,Proc, London Math. Soc. 131 38 (1979), 385422. [22] A. E. Ingham, Proc. London Math. Soc. [2] 22 (1923), xxix, (Records for April26, 1923). [23] A. E. Inghain, Mean value theore~~ls in tlze tlzeory qf'the Rieinarm zeta~fi~izctiorz, Proc. London Math. Soc. [2] 27 (1 926), 273300. 1241 A. Ivié, Lecturc:s orz tilean values cftho Riernaiin zcítaji~nctiorz,Tata Instittite OS Fundainental Research Lectures on Matheniatics and Physics 82, Sp~irigerVerlag, Berlin, 1991. [25] J. P. Keating and N. C. Snaith, Rantik,rn matrix theory and ((112 214 (2000), 5789.
+ it), Comin. Math. Phys,
[26] E. Lindeloí', Quelques re~nurquessur Ia croisscrnc.e de lu ,function {(S), Bull. Sci, Math., 32 (1908), 341356. [27] J. E, Littlewood, Researclae,~ in tlze tlzeory oj'tl~eRiemanrz (~finction,Proc, Londoii Math. Soc. [21 20 (1921), xxiixxviii, (Records for Fcb 10, 1921). [28] F. Mezzadri and N, C. Siiaith, eds., Recent Peltspectives in Rartclon~A4atri.r Tlzeory and Ncimher Theory, Cambridge Univcrsity Prcss, Cambsidgc, 2005. [29] H. L. Montgornery, The puir correlatiori of zeros of tlie zeta.firzction, Analytic Nurnber Theory, Proceedings OSSymposia in Puse Mathematics 24 (1973), 181193. 1301 Y. Motohashi, Spectral Thcoiy of the Riemann ZctaFuiiction, Ccirnhridge Univ. Press, Cambridge, 1997. [31] A. Odlyzko, Tlw lo2'th zero of the Riemann zeta .fikitction and 175 r?zi/liorz c?f it&~ neighbous, unpublished; http://www.dtc .umn.edu/  odlyzko/unpublished/index. html;(accessed Masch 21,2008). [32] "Prime Suspecl" (N~lriz$3rs),CBS (airdate Februaiy 18,2005). [33] "Prime Suspect" Overview (Numl>3rs:Prime Suspect  TV.con1); http : //www .tv.com/ numb3rs/primesuspect/episode/383244/summary. html; (accessed Marcli 21,2008). [34] G. F. B. Rieinann, Ueber die Anzalzl der Prirnz(thlert unter eirter gegehener?Grtjsse, Monatsberichte der Berliner Altademic (1859), 67 1680. [35] C. L. Siegel, Ueber Riemanns Nuchlass zur Analj~ti,sc*lzen Zuliknt/leorie, Quellen und Studien zur Geschichlc dcr Math. Asts. Phys. 2 (1932), 4580. Rcprintecl in C. L. Siegcl, Gesammelte Ahhandlungerz, vol, 1, Spiingei; 1966, PP. 2753 10. [36] K, Soundai.amjan, Mourlents of the Riernann zeta,fit~zction,asXiv:inath.NT/0612106 (2006). [371 E. C. Titchmarsli, The meanixrlueoj'the zetafunction oi? tlie critica1line, Pioc. London Müth. SOC.121 27 (1 926), 1371 50. [38] C.J. de la Valléc Poussin, Recherches nnalytiques sur Ea thkorie des nonlbres (premierepartie), Ann. Soc. Sci, Bruxelles [I] 20 ( 1 896), 183256.
The Collatz Chameleon Marc Chamberland
lntroduction The 3x + 1 Problem is today's inost easilystated unsolved mathematical problem. The origin of the problem is murky but it is largely credited to Lothar Collatz, hence it is sometimes called the Collatz Problem. Collatz considered the fiinction
[3x + 1,
x= 1 (mod 2), x r O (mod 2).
The conjecture states that any positive integer eventually iterates under this map to the number one. Note that an odd number m iterates to 3m + 1 which then iterates to (3m + 1)/2. One may therefore "compress" the dynamics by considering the map
Im, L
T(x) =
x

1 (mod 2),
x O (mod 2).
For example, one has the trivial cycle consisting of (1, 2). Most researchers work with the map T instead of C. Despite its powerless looks, the Collatz problem has enticed many bounty hunters to pursue it with little to show at the end of the day. The famous mathematician Paul Erdds was correct when he stated, "Mathematics is not ready for such problems." The structure of the positive integers forces any number to iterate under T to one of the following: the trivial cycle (1,2), a nontrivial cycle, or infinity (the orbit is divergent). The 3x + 1 Problem claims that the first option occurs in al1 cases. Published results claim that this has been verified for al1 integers less than 100 x 250= 1.12 x 1017. This computationcompleted in April 2000was accomplished with two 133MHz and two 266MHz DEC Alpha computers and used 14.4 CPU years. An ongoing distributedcomputer project by Eric Roosendaal (www.ericr.nl/wondrous) claims to have improved this to 195 x 250 = 2.19 x 1017. For those who believe the second option, the existence of a nontrivial cycle, it should be mentioned that any such cycle must have a length of at least 252,000,000. Lilte severa1 mathematical conundrums, the 3x + 1 Problem may be rephrased as other problems which bear little if any resemblance to the original. What follows are various conjectures which are equivalent to the Collatz Problem. These different "shades" of the Collatz chameleon appeal to various temperaments; share with a friend the shade which they will find the most enticing. 2 '
[. 
The "Stopping Time" Shade There is a nat~ral~algorithm for checking that al1 numbers up to some N iterate to one. First, check that every positive integer up to N 1 iterates to one, then consider the iterates of N.
(,
/*/*sf'\
,flx3

,
,
', .
, ¡a,
= S  T. Hence, by Euler's criterion, n a=
na.n a Z4q[q]! = (:) +
[%]!.A
A
(modp).
~ E T a€@
aeS
On the other hand, because
where we have used Wilson's theorem: ( p  l)!
whence A metry.
ES
( 1)9($1(mod p). The other statement in Lemma 1 follows by symH
From Lernma 1 it follows immediately that ( 1) A 5 1 or l(rnod pq).
Lemma 2. A
 1(mod p). We infer that
E
1 or  1(mod pq) ifarzd only If p
($) = ( 1)
9(V) if and only if
= q E 1(mod 4),
ProoJ We set d = pq. By the Chinese Remainder Theorern, the congruence x2 E 1 (mod d) has precisely four solutions, say X EE 1,  1, N, N(rnod d). The congmerice x2=  1(mod d) has a solution X E I (mod d) if and only if p z q ZE 1(mod 4), in which case there are precisely four solutions, namely, X EZ 1, 1, NI,  N I (rnod d) Now for each a in there exist unique a' in @ and 6, in { 1, 1) such that a a' EE S, (mod d). (The correspondence a H a' is a permutation of (9.) Writing = {a E
: a = a r ) = {a E @ : a2 r
f 1 (modd)},
we rernark that
If p
q
f (mod 4), we have
n a  f ( l . N . I . I N )  f ( ~ ~ . ~ ~ (modd), )=t~l a@
whereas othenvise it is the case that
An Elementary Proof of the Quadratic Reciprocity Law
n a
i(1.N)
+ f1 (modd).
ac'P
The lemma follows immediately. Proof of theorern. Combining Lemmas 1 and 2, we conclude that
(119
(%)
=(1)q
(9)
ifandonlyif
prqrl(mod4).
The theorem now follows by considering the four cases (p, q) 3 (1, l ) , (1,  l), ( 1, 1), ( 1,  1) (mod 4). Or, in formulas, since p q = 1(rnod 4) if and only if (  1 ) P  F = 1:
But
+I
+l
showing that  (  1 ) + (  1 ) ~ (  1 ) ~ ~ = (1)qG.
m
REFERENCES 1. D. M. Burton, Elementary Number Theory, 5th ed., McGrawHill, New York, 2002. 2. C. F. Gauss, Disqur'sitionesArithmeticae (trans. A. A. Ciarke), Yale IJniversity Press, New Haven, 1966. 3, F. Lemmemeyer, Reciprocity iutvs, SpringerVeriag, Berlin, 2000.
Department of Mathematics & Statistics, McMaster University, Ontario L8S 4K1,Canadn kimsey@ mcmaste~ca
Originally appeared as: Kim, Sey Y. "An Elementary Proof of the Quadratic Reciprocity Law." American Mathernatical MonthZy. vol. 111, no. 1 (January 2004), pp. 4850.
Part VII: Elliptic Curves, Cubes and Fermat's Last Theorem
The ancient Greeks had no trouble with squares, but cubes were another matter. They sought compassandstraightedge methods of duplicating cubes and trisecting angles, but what they sought was impossible. Why? Well, the short answer is that the roots of the polynomials x3  2 and 8x3  6x + 1 do not lie in any field that is made by successively adjoining a finite nuinber of square roots to the rational numbers. (The long answer is Galois theory.) At any rate, this was the origin of mathematicians' fascination with cubes and higher powers, and our final chapter contains five Biscuits dealing with powers higher than two. We begin with a Proof Without Words. It has been known for over 2000 years that the sum l 3 + 23 + + n3 of the first n cubes is equal to (1 + 2 + + n)2,the square of the sum of the first n integers. Proving this is a routine exercise in mathematical induction. This chapter's first Biscuit is J. Barry Love's Proof Without Words: cubes and squares (Math. Magazine, vol. 50, no. 2 (March 1977), 74; see also p. 85 of vol. 1 of Nelsen's book), in which he shows us a very nice pictorial proof of this old but still lively chestnut. Our next Biscuit has its origin in a famous comment by Srinivasan Ramanujan. Replying to Hardy's comment about his taxicab's boring license number 1729, Ramanujan said that on the contrary, 1729 is the srnallest positive integer that can be written as a sum of two cubes in two different ways. Joseph Silverman begins with Ramanujan's statement and taltes us through quite an enjoyable journey in his Lester Ford Awardwinning "Taxicabs and sums of two cubes" (Amer. Math. Monthly, vol. 100, no. 4 (April1993), pp. 331340). Included is a "Hall of Fame" of smallest positive integers of various types that can be written as sums of cubes in at least two distinct ways. As a bonus, Silverinan has written a "second helping" with updates on the Hall of Fame and soine remarks on the rank (as a finitely generated abelian group) of curves x3 + y3 = a, concluding with a short table of such curves. Joseph Silverman's curves x3 + y3 = a are cubics in two variables that have a welldefined tangent at each point. Such curves are called elliptic curves, and they are the subject of our next Biscuit, Ezra Brown's Pólya Awardwinning "Three Fermat trails to elliptic curves" (College Math. Journal, vol. 31, no. 3 (May 2000), pp. 162172). It so happens that Diophantus posed a problem in his Arithmetica that contained the firstever appearance of elliptic curves. Brown traces the history of three problems, each associated with Fermat and each having its resolution in the world of elliptic curves. The first is to determine which positive integers n are the areas of rationalsided right trianglesthe socalled Congruent Numbers Problem. The second is to determine for which values of d the equation x4 + dx2y2+ y4 = z2has nontrivial integer solutions. The third is Fermat's Last Theorem, which brings us to our final two Biscuits. In or about 1637, Pierre de Fermat wrote the mathematical world's most famous marginal note, effectively saying that if n is an integer greater than two, then the equation
256
'
Part Vil: Elliptic Curves, Cubes and Fermat's Last Theorem
xn + yn = zn has no integer solutions in which xyz # O. Then he wrote, "1 have discovered a tmly marvelous proof of this fact, but this margin is not big enough to contain it," This "fact" is Fermat's Last Theorem (FLT), until recently the most famous unsolved problem in mathematics. Our nexttolast Biscuit is Willard Van Orman Quine's "Femat's Last Theorem in combinatorial forin" (Amer. Math. MonthZy, vol. 95, no. 7. (AugustSeptember 1988), p. 636), a diabolically clever restatement of FLT as a theorem about placing rocks in boxes. Read this short but delightful piece and marvel. We conclude with Fernando Q. G O U V ~Lester ~ ' S Ford Awardwinning "A Marvelous Proof' (Amer. Math. Monthly, vol. 101, no. 3 (March 1994), pp. 203222). This is an erninently readable guide to the mathematics underlying Andrew Wiles' proof of FLT. Gouvea begins with a brief history of the problem fiom Femat's time to the early 1980s. He introduces us to "the inain characters in the drama", namely padic numbers, elliptic curves, modular forms and Galois representations. He presents the TaniyamaShimuraWeil Conjecture, namely that every elliptic curve is modular, and explains the link between elliptic curves and Wiles' approach to the proof of FLT. The paper ends with the status of Wiles' proof up in the air, but Gouvea adds a "second helping" and brings us up to date about how Wiles brought in Richard Taylor and how the two of them finished the proof.
Proof Without Words: Cubes and Squares J. Borry Love
Originally appeared as: Love, J. Barry. "Proof Without Words: Cubes and Squares." Mathematics Magazine. vol. SO, no. 2 (March 1977), p. 74.
Taxicabs and Sums of Two Cubes joseph H Silverman
Our story begins in 1913, when the distinguished British mathematician G. H. Hardy received a bulky envelope from India full of page after page of equations. Every famous mathematician periodically receives letters from cranks who clalm to have proven the most wonderous results. Sometimes the proofs, incorrect or incoherent, are included. At other times the writer solicits a reward in return for revealing his discoveries. Now this letter to Hardy, which was from a poor clerk in Madras by the name of Ramanujan, was filled with equations, al1 given without any sort of proof. Some of the formulas were wellknown, mere exercises; while many of the others looked preposterous to Hardy's trained eye. Who would have blamed Hardy if he had returned this missive to the sender, unread? And in fact, Ramanujan had previously sent his results to two other British mathematicians, each of whom had done just that! But instead Wardy gave sorne thought tu these '"ild theorems. Theorems such as he had never seen before, nor imagined."' And together, he and J. E. Littlewood, another eminent mathematician with whom Hardy often worked, succeeded in proving sorne of Ramanujan's amazing identities. At this point Hardy realized that this letter was fmm a true mathematicítl genius, and he became determined that Ramanujan should come to England to pursue his mathernatical researches. Using travel money provided by Hardy's college, Ramanujan arrived in 1914. Over the next severa1 years he continued to produce and publish highly original material, and he also collaborated with Hardy un a number of outstanding papers. In 1918, at the age of 30, Ramanujan was elected a Fellow of the Roya1 Society and also of Trinity College, bath signal honors which he richly desemed. Unfortunately, in the colder climate of England he contracted tuberculosis. He returned to his native Madras and died, in 1920, at the age of 33. During al1 of Ramanujan" life, he considered numbers to be his personal friends. To illustrate, Hardy tells the story of how one day he visited Rarnanujan in the hospital. At a loss for something to say, Hardy remarked that he had arrived at the hospital in taxicab number 1729, '"t seemed to me," he continued, "a rsather dull number." To which Ramanujan replied '"o, Wardy! It is a very interesting number, It is the smallest number expressible as a sum of two cubes in two different ways:"
*This article is an expanded version of talks given al: M.I.T. ~ n Brown d University '[lo], pase 32 2[101, pase 37
Part VII: Elliptic Curves, Cubes and Fermatls Last Theorem
260
Hardy then asked for the smallest number which is a sum of two fourth powers in two different ways, but Ramanujan did not happen to k n ~ w . ~ Rather than studying sums of higher powers, we will instead concern ourselves with another question that Hardy could just as easily have asked, namely for the smallest number which is a sum of two cubes in three (or more) distinct ways. In this case the answer is given in [3],
although if one is willing to allow both positive and negative integers there is the much smaller solution
In this note we will be taking a leisurely numbertheoretic stroll centered around the problem of writing numbers as sums of two cubes, specifically the search for integers with many such representations. It will be some time before we actually return to this specific question, but along the way we will view some beautiful mathematics which illustrates some of the interplay that can occur between geometry, algebra, and number theory. We will thus be looking at solutions of the equation
What can be said about such solutions? First we have the elementary result that if A is a nonzero integer, then there are only finitely many solutions in integers X and Y. Of course, if X and Y are restricted to be positive integers, then this is obvious. But in any case we can use the factorization
to see that A rnust factor as A
= BC
B = X + Y and
in such a way that
c=x~xY+Y~.
Now there are only finitely many ways of factoring A as A = BC, and for each such factorization we substitute the first equation (i.e. Y = B  X) into the second to obtain
Thus each factorization of A yields at most two values for X, each of which gives one value for Y = B  X. Therefore there are only finitely many integer solutions (X, [Aside: This proof that the equation X3 + y 3 = A has only finitely many solutions in integers depends heavily on the factorization of the polynomial x3+ Y 3. It is similarly true, but quite di.fficult to prove, that an equation like X3 + 2Y3 = A has only finitely many integer solutions. This was first proven by A. Thue in 1909 [ll].By way of contrast, note that the equation x 2 2 Y 2 = 1 has infinitely many solutions,] 3 ~ h answer, e 635,318,657 = 5g4 + 15g4 = 1 3 3 ~i 1 3 4 ~appears ~ to have been discovered by Euier. And it does not seem to be known if there are any numbers which are a sum of two fifth powers in two different ways. '~xercise: Show that any solution in integers satisfies max{lXI, IYI} S 2\1m.
Taxicabs and Sums of Two Cubes
26 1
As is generally the case in rnathernatics, when a person wants to work on a difficult mathematical problern, it is nearly always best to start with a related easier problem. Then, step by step, one approaches the original goal. In our case we are confronted with the equation and a natural first question is to ask for the solutions in real numbers. In other words, what does the graph of this curve look like? Since dY/dX = (x/Y)~, the graph is always falling. Further, it is syrnrnetric about the line Y = X and has the line Y = X as an asymptote. With this information it is easy to sketch the graph, which is illustrated in Figure 1. We will denote the resulting curve by C.
Figure 1, The curve C:
x3+ y 3 = A
If (X, Y) is a point on this curve C, then so is the reflected point (Y, X). But there is another, less obvious, way to produce new points on the curve C which will be very important for the sequel. Thus suppose that P = ( X , , Y,) and Q = (X,, Y,) are two (distinct) points on C, and let L be the line connecting P to Q. Then L will (usually) intersect C at exactly one other point. To see this, suppose that L is given by the equation Y = mX + b. Then substituting the equation of L into the equation of C gives the cubic equation
By assurnption, this equation already has the solutions X, and X,, since P and Q lie on the intersection C n L, so the cubic equation has exactly one other solution X,. (We run into a problem if m =  1, but we'll deal with that later.) Then letting Y, = mX, + b, we have produced a new point R = (X,, Y,) on C. Further, even if P = Q, the same procedure will work provided we take L to be the tangent line to C at P. Thus given any two points P and Q on C, we have produced a third point R. Finally we define an "addition law" on C by setting P
+ Q = (reflection of R about the line Y = X) .
+
In other words, if R = (X,, Y,), then P Q = (Y,, X,). (See Figure 2.) The reason we define P + Q with this reflection will soon become clear, but first we have to deal with the pesky problem that sometirnes our procedure fails to yield a third point.
Part VII: Elliptic Curves, Cubes and FermatrsLast Theorem
262
Figure 2. The addition 1aw on the curve C: x3+ y3 = A
This problern arises whenever the line connecting P and Q has slope  1, and thus is parallel to the asyrnptote Y = X. We solve the problem in cavalier fashion; since there is no actual third intersection point we create one by fiat. To be precise, we take the XYplane and add an extra point, which we will denote by 8,This point has the property that the lines going through @ are exactly the lines with slope  1. Further, if P is a point in the XYplane, then the unique line through P and 8 is the line through P having slope  1. Having done this, we are now in the happy position of being able to assert that given any two points P and Q on C, the above procedure will yield a unique third point R on C, so we are able to define P Q for any P and Q. (By definition, we set @+ @= 8.) [Aside. Sorne readers will doubtless recognize that what we have done is start the construction of the real projective plane. The projective plane consists of the usual XYplane together with one point for each direction. In our case, we only needed the direction with slope  1. The projective plane has the agreeable property that any two lines, even "parallel" ones, intersect at exactly one point. This is true because if two lines are parallel, then they intersect at the point corresponding to their cornrnon direction.] The justification for our use of the symbol " + " is now this:
+
The addition law P group .
+ Q described above makes the points of C into an abelian
To be more precise, if P = ( X ,Y) is a point on C, we define its inverse to be its reflection, P = (Y, X). Then for al1 points P, Q, R on C we have P+@=@+P=P P+(P)= @
(identity)
(inverse)
P+Q=Q+P
(cornmutativity)
(P+Q)+R=P+(Q+R)
(associativity).
Al1 of these properties are quite easy to check except for the associativity, which we will return to in a rnoment.
Taxicabs and Sums ofTwo Cubes
263
Note that the addition procedure outlined above is entirely mechanical, We can write down explicit formulas for the sum of two points, although there are a number of special cases. For example, if P = (X, Y), then
The formula for the sum of two distinct points P, = (X,, Y;) and P2 = (X2,Y,) is somewhat more complicated:
And now that we are in possession of these formulas, verification of the associative Xaw is a tedious, but straightforward, task. Let us now look at an example, and what better choice than Ramanujan's equation
We already know two interesting points on this cuwe, namely
P = (1,12) and & = (9,lO). Using the addition law, we can easily compute some more points, such as
As the discerning reader will notice, the nurnbers produced seem to grow with frightening rapidity, But of far more importance is the fact that although we have not produced any new integer solutions, al1 of the new solutions are at least in rational numbers. This is a consequence of the fact that the addition Iaw on C is given by rational functions. That is, the coordinates of P & are given by quotients of polynomials in the coordinates of P and &. Thus if the cooñdinates of P and f2 are rational numbers, then so are the coordinates of P t &. (If this is not clear, look for examgle at the formula for 2 P given above, 1Cf A, X, and Y are al1 rational nurnbers, then the formula shows that the coordinates of 2P are also rational.) Let us define
+
C(Q)
=
(( X, Y) : X and Y are rational numbers and X3 + Y
= A) U
( 8).
Here Q is the usual symbol for the field of rational numbers. Then the remarks given above provide a proof of the following fact, first noted by Poincaré around 1900 [ó]:
The set C(Q) is a subgroup of C. In other words, C(Q) suplllied with the additwn law from C becomes a group in its own right.
Part VII: Elliptic Curves, Cubes and Fermat's Last Theorem
264
The sum of two eubes "Hall of Fame" The following materia! givcs thc smallest intcger 1 knaw with thc indicatcd property, It has bcen collected from various sourccs, including [3] and [12]. Notc that we are counting X 3 + Y' and Y.' + X%S bcing thc samc represcntation. Positive integers, 2 reprcscntations, cubcfrec 1729 = 1% 12' = 9% 10" 7 113 19 Any integers, 3 representatiuns, nat cuhcfrec 4104 =z 16% 22" = 15% 9C)" = ( 12)R + 18" = 2" 33" 1') Any integers, 3 reprcsentations, cubcfrce 3,242,197 = 141" + 76" 138% 85' = (  171)' + 202' = 7 31 67 223 Pasitive integers, 3 reprcscntations, not cubcfrcc 87,539,319 = 43h3 + 167? = 4233 + 228' = 414' + 255' = 3" 7 31 * 67 223 Positive integers, 3 rcprcscntaticrns, cubcfrce 15,170,835,645 = 517' + 24M3 = 709' 245fi3 = 1733" + 2132' = 32 5 7 + 3 1. 3 7 199. 211 Any integers, 4 represcntatic~ns,not cubefrcc 42,549,416 = 348% 74" 2 2 +~2723 ~ = (  2662)" 22bh43 = (  475)' 531' = 2" 7 13 ,211 277 Positive intcgers, 4 rcprescntations, not cubcfrcc 26,059,452,84l7(IO0= 29620' + 4170" 28$103 + 129003 28423" 14577" 24940% 2 2130" = 2" 5.' * 31 . 43" 97 100 Any integers, 4 represcntstions, cubcfrcc Unknown! Any intcgers, 5 rcprescntations, not cubeSree 1,148,834,232 = 1044% 222' = 920% 718' = 846% 316" 1 7986)" 77992" (  1425)" + 1503" = 2" 3' 7 13 21 1 277
+
+

+
We have come a long way in our study of the solutions of the equation
x3+ y3 = A. What we have found is that the set of solutions in rational numbers becornes, in a very natural way, an abelian group. So if we can say something significant about this group, then we might feel that at last we have some understanding about this set of rational solutions. An answer to this problexn is provided by one of the most celebrated theorerns of the twentieth century. Aside from its intrinsic interest, this result has been the starting point for much of the study of Diophantine equations over the past 70 years. The theorem, as we state it, was first proven by L. J. Mordell ín 1922 [S]. It was subsequently vastly generalized
265
Taxica bs and Sums of Two Cubes
by A. Weil in his 1928 thesis, and so is usually called the MordellWeil Theorern: Them exists a finite set of points P,, . . . , P,. in C(Q) so that euery point in C(Q) can be obtained fvorn P,, . . . , Pr by addition and subtraction. In fancier Zanguage, the group C(Q) is Pnitely generated. The points P,, . . . , Pr are called generators for C(Q). This seems fairly satisfactory. Even though our equation may have infinitely many rational solutions, they can al1 be obtained by starting with some finite subset and applying a completely mechanical procedure. For example, on the cuwe
x3+ Y3 = 7, every rational point is a multiple of the single generating point (2,  1). Similarly, it is probably true that every rational point on Ramanujan's curve has the form nP rnQ, where P = (1,12), & = (9, 10)' and n and m are allowed to range over al1 integers, although 1 am not aware that anyone has verified this probable fact, It rnay come' as a surprise, then, to learn that the MordellWeil Theorem is far less satisfactory than it appears, This is due to the fact that it is not effectiue. What this rncans is that currently we do not have an algorithm which will determine, for every value of A, a set of generators P,, . . . , Pr for C(Q). In fact, there is not even a procedure for determining exactly how many generators are needed, although it is possible to give a rather coarse upper bound. This problem of making the MordellWeil Theorem effective is one of the major outstanding problems in the subject. Another open problem concerns the number of generators needed. As mentioned above, the curve X' y3= 7 requires only one generator, while Ramanujan's curve x3+ y 3= 1729 needs at least two. The question is whether there are curves which require a Iarge number of generators. More precisely, is it true that for every integer r there is some value of A so that the rational points on the curve X 3 y3 = A require at least r generators? We now return to our original problem, namely the study of integer solutions to the equation x 3+ y3 = A . Specifically, we seek values of A for which this equation has many solutions. We have observed that the equation
+
+
+
X3
+ y3= 7
has the solution P = (2,  l), and by taking multiples of P we can produce a sequence of points
Further, it is true (but rnoderately difficult to prove) that this sequence of points P , 2P, 3P,. . . never repeats. Each point in the sequence has rational coordinates, so we can write nP in the form
where a,, b,, and d , are integers. We are going to take the first N of rational solutions and multiply our original equation by a large integer so as clear the denominators of al1 of them. Thus let
B = d,d,
d,.
266
Part VII: Elliptic Curves, Cubes and Fermat's Last Theorem
Then the equation
x3+ y 3 = 7~~ has at least N solutions in integers, namely
(Actually 2 N solutions, since we can always switch X and Y, but for simplicity we will generally count pairs of solutions ( X , Y ) and (Y, X ) . ) We have thus found the following answer to our original problem:
Given any integer N, the1.e exists a positiue integer A for which the equation X3 + Y3 = A has at least N solutions in integers. Of course, Ramanujan and Hardy were probably talking about solutions in positive integers; but with a bit more work one can show that infinitely rnany of the points P, 2P, 3P, . . . have positive coordinates, so we even get positive solutions. Naturally, it is of some interest to make this result quantitative, that is, to describe how large A must be for a given value of N. The following estimate is essentially due to K. Mahler [4], with the improved exponent appearing in [S]:
There is a constant c > O such that for ififinitely many positive Integers A, &e number of positive integer solutions to the equation X3 + Y3 = A exceeds
C " J ~ .
1n sorne sense we have now answered our original question, There are indeed integers which are expressible as a surn of two cubes in many different ways, But a nagging disquiet remains, We have not really produced a large number of intrinsically integral solutions. Rather, we have cleared the denominators from a lot of rational solutions. In the solutions produced above, the X and Y coordinates will generally have a large common factor whose cube will divide A. What happens if we rule out this situation? The simplest way to do so is tu restrict attention to integers A that are cubefree;that is, A should not be divisible by the cube of any integer greater than 1. This is a reasonable restriction since if D3 divides A, then an integer solution (X, Y) to x3+ Y3 = A really arises frorn the rational solution (X/D, Y / D ) to the "smaller" equation x3+ Y = A / D ~ . Notice Ramanujan's example is cubefree. But the example with three representations given earlier, is not cubefree. As far as E have been able to determine, the smallest cubefree integer which can be expressed as a surn of two positive cubes in three distinct ways was unearthed by P. Vojta in 1983 1121: = 3 2 75
7 31 37 199 211, And now our problem has become so difficult that Vojta7s number holds the current record! There is no cubefree number known today which can be written as a sum of two positive cubes in four or more distinct ways.
Taxicabs and Sums of Two Cubes
267
We are going to conclude by describing a relationship between the two problems that we have been studying. The first problem was that of expressing a number as a sum of two rational cubes, and in that case we saw that al1 solutions arise from a finite generating set and speculated as to how large this generating set might be. The second problem was that of writing a cubefree number as a sum of two integral cubes, and here we saw that there are only finitely many solutions and we wondered how many solutions there could be. It is n0t.a priori clear that these two problems are related, beyond the obvious fact that an integral solution is also a rational solution. In 1974 V. A. Dem7janenko stated that if there are a large number of integer solutions, then any generating set for the group of rational points must also be large, but his proof was incomplete. (See [2, page 1401 for Lang's commentary on and generalization of Dem'janenko's conjecture.) The following more precise version of the conjecture was proven in 1982 [8]: For each integer A, let N(A) be the number of solutions in integers to the equation x3+ Y = A, and let r(A) be the minimal number of rational points on this curve needed to generate the complete group of rational points (as in the MordellWeil Theorem). There is a constant c > 1 such that for euery cubefree integer A,
Note that the requirement that A be cubefree is essential. For as we saw above, we can make N(7B3) as large as we want by choosing an appropriate value of B. On the other hand, r ( 7 ~ =~ r(7) ) for every value of B, so an inequality of the form N(A) S c ' ( ~ )cannot be true if we allow arbitrary values of A. (To see that r(7B3) = r(7), note that the groups of rational points on the curves x3 y3 = 7 and X 3 + Y = 7~~ are the same via the map (X, Y) + (BX, BY).) Final Rernark. The cubic curve X 3 + Y = A is an example of what is called an elliptic curue. Those readers interested in learning more about the geometry, algebra, and number theory of elliptic curves might begin with [9] and continue with the references listed there. Elliptic curves and the related theory of elliptic functions appear frequently in areas as diverse as number theory, physics, computer science, and cryptography.
+
ACKNOWLEDGMENTS. 1 wouid like to thank Jeff Achter and Greg C a l for their helpful suggestions.
REFERENCES
1. Demyjanenko,V. A.: On Tate height and the representation of a number by binary forms, Muth. USSR Isu. 8, 463476 (1974). 2. Lang, S.: Elliptic Curues: Diophuntine Analysis. Berlin: SpringerVerlag, 1978 3, Leech, J.: Some solutions of Diophantine equations. Proc. Camb. Philos. Soc. 53,778780 (1957). 4. Mahler, IC.: On the lattice points on curves of genus 1, Proc, London Math. Soc, 39, 431466 (1935). 5. Mordell, L. J.: On the rational solutions of the indeterminate equation of the third and fourth degree. Proc. Camb. Math. Soc. 21, 431466 (1922). 6. Poincaré, H.: Sur les propriétés arithmétiques des courbes algébriques, J. de Liouuille 7, 161233 (1901). 7. Silverman, J. H.: Integer points and the rank of Thue elliptic curves. Inuent. Math. 66, 395404 (1982). 8. Silverman, J. H.: Integer paints on curves of genus 1. J. London Math. Soc. 28, 17 (1983).
268
Part VII: Elliptic Curves, Cubes and Fermat's Last Theorem
9. Silverman, J. H., Tare, J.: Rational Points un Efliptic Curues. New York: SpringerVerlag, 1992. 10. Snow, C. P., Foreword to: A Mathernatician's Apology. by G. H. Hardy (1940), Cambridge: Cambridge,UniversityPress, 1967. 11. Thue, A.: Uber Annaherungswerte algebraischer Zahlen. J. reine ang. Math. 135, 284305 (1909), 12. Vojra, P.: private communication, 1983.
Added in proof: Richard Guy has pointed out to the author that Rosenstiel, Dardis and Rosenstiel have recently found the noncubefree example
6963472309248 = 24213 t 19083" 54363 t 18948~= 1020O3+ 18072~ = 13322~+ 166303 which is smaller than the example ín the above table, and which is in fact the smallest such example. See Bull. hzst . Math. Appl. 27(1991), 155157. Mathematics Depa rtment Brawn Uiziuerdy Providence, RI 02912 USA [emailprotected]. browvl.edu,
Originally appeared as: Silverman, Joseph H. "Taxicabs and Sums of Two Cubes." American Mathematical MonthZy. vol. 100, no. 4 (April 1993), pp. 33 1340.
Taxicabs and Sums of Two Cubes
Second Helping joseph H Silverman
The nthTaxzcab Nurnber, denoted Taxicab(n) is the siiiallest nurnber tliat can be expressecl as a siim of two positive culses in at least n ways (where X" YY" aiid Y" XX"count as a single represerltatiori). Our "clearing denominators" trick shows that Taxicab(n) exists, biit even thc most efñcicnt search rrletliod l 2, tlieii 1'11 use it to constiuct the following elliptic curve:
+
Now if f is a polynomial of degree k and if discriniinant A( f ) of f is defined by
7p1,
rZ,. . . , 12 ase al1 of its roots, tlien the
If f is monic with integer coefficients, it turns out tliat A( f ) is an integer. Tlie three roots of the polynomial g ( x ) on thc rigl.ithand side of tlie Frey cuive are O, a", and  bn; using the fact that a"  ( b n )= a" 6" = c n and a little algebra, we find that A(g) = (abcl2 Frey said that an elliptic curve with suck a discriniinant inust be really strange. In particular, such a curve cannot possibly be what is called modular (never inind what that rneans). Now here's a thouglit, said he; what if you could iiianage to prove two things: first, that a large class of elliptic ctilves i s modular, and second, tliat tlie Frey curve is always a nieniber of that class of cuives?Wlzy, you'd liave a conti*adiction fronl wliich you could conclude that there is no sucli cuive. Tliat is, tlzere is no such solution to the Feriiiat equatioii. . . tliat there is no counterexainple to Femat's Last Theorein, . . and so Ferniat's Last Theorein is true. And that is exactly what Andrew Wilcs [17]with a lastrninute assist from Kichard Taylor [15]did.
+
' " .
7
x'%
d x 2y 2 + y4 = z2 and Elliptic Curves
A solution of
with x, y, and x nonnegative integers is called trivial eitlier if xy = O 01 if d = n2 2 and x = y = 1. Tlie first mention of this equation was made by Fermat, who proved that if d = O, tlien (3) has oiily trivial solutions. His proof appeared in yes1637 as a marginal note in his copy ofyou guessed itBachet's edition
Part VII: Elliptic Curves, Cubes and Fermat's Last Theorem
282
of Diophantus' Arlthmetica. Over the years, inany inathernaticians tackled this problem, including Leibniz, who sliowed that tlie case d = 6 has only trivial solutions, and Euler, who gave severa1 elegant inethods for generating nontrivial solutions of (3). As a result of reading a review in Mathel?zaticak Reviews, 1 got interested in tliis problem. In particular, it seemed curious that there were 23 values of d between O and 100 about which it was unknown whether nontrivial solutions to (3) exist. 1 was able to show tliat in 22 of these cases, tliese are indeed only trivial solutions to (3). The exceptional case is d = 85apparently a solution Euler inissed, since it is a solution he might liave found, naiiiely
1 wrote up what I'd done and sent it off to a journal, only to receive tlie aforementioned bad news that the entire problein coulct be transforined into a problem about elliptic curves, whose solution, 1 was assured by tlie referee, was routine. Here's how the transformation works. Suppose that X4 d x 2y 2 y 4 = .Z2; if we inultiply both sides of this equation by x2/Y ", we are led to
+
+
If we now let y = .Zx3/y3 and x = ( x / Y ) ~ ,we obtain
+
since the roots of the right hand side are distinct if d f 2, (4) is the equation of an elliptic cttrve. Hence, if there is a nontrivial solution to (3), then the elliptic cuive (4) will liave a rational point ( x , y) such that x is a perfect square. If this sounds familiar, it should; it's almost the same thing that liappens wlien the Congruent Numbers problein is transformed to the world of elliptic cuives. To take anotlier example, since (25,245) is a rational point on tlie elliptic cuive y 2 = x3 71 x 2 x in whicli the xcoordinate is a perfect square, it follows that X' 7 1 x 2y 2 Y" .Z2 has a nontrivial solutionnainely, (x, Y, 2 ) = (5,1,49). Resolving the problein at band, Izowever, wbile not neaily as hard or deep as the i.esolution of tlie Congruent Nuliibers problem, is still not entirely as routine as al1 that; furthermore, at tlie time, my knowledge of elliptic cuives was practically nil. Then 1 got an idea. 1 sent the paper off to a different journal, explaining in the cover letter that my approach to the problem was conipletely eleinentaiy and avoided the coiiiplicated rnachineiy of elliptic cuives. Tliey accepted tlie paper [l].
+
+
+
+
8 Now What?
The future looks bright for the woild of elliptic cutves. Research in the area is booming, and there are inany old problems in nurnber theory that have been around for a long time and just might yield to the elliptic curve approach. In fact, . . . oh, yes, of course you have questions,
+ +
You've said that elliptic curves are cubics of the f o m y 2 = " x ax2 bx c, in u~hicbtbe cubic polynomial in x bus distinct roots. What do .you get zf the
Three Fermat TraiIs t o Elliptic Curves
283
+
polynomial has repeated roots, such as x3 or x3 x2?Those cusves are called singular cubics, aild they aren't studied as rnuck as elliptic curves are, inainly because they don't have anything comparable to the chordandtangent addition of points on an elliptic curve. 1s tbere a special name ,for cuwes that involve poEyno~.rzialsof degree greater than 3? For some of them, yes. In Section 3, we saw that an equation of the form y2= f(x) with f a polynomial of degree 4 can be transfosmed into an elliptic cusve, provided f has distinct soots. Curves of the form y2 = g ( x ) , with g a polynomial of clegree 2 5, are called hyperelliptic curmes, and a goodly bit is known about them, But that's another story. Maybe sorne other tin~e. * You said something back in Section 4 about addition ofpoints on a n ell@tic cuwe being dejined in a peculiar way for a particular ?vason. Wbat's tlbe reason? Now tlbat7sa story I'd love to tellbut the inargin of this ,paper is not large enough to coiltain it, As iny gl.~indxnotherused to say, "Te11 you to~norsow!"
References 1. Ezra Brown, x6 k dx2y Z f = zL: Sotne cases witli only trivial solutionsand a solution Eiiler niissed, Glasgow Math. J. 31 (1989), 297307. 2. David A. Cox, Introduction to Fermat's Last Thearem, Amer. Muth, Moiiíthly 101 (1994), 314. 3. Gerllard Frey, Links between stalile elliptic cutves and certain Diopllantine equations, Aiziiz. Ufziu. Samuiensls, Series Matheinaticae 1 (1986), 140. 4, Shafi Golctwüsser and J Kilian, Alrnost a11 prinles can be qiiickly cestified, Proc. 18th Aiiz~~~icil ACM Syn?posiui?zoolz l%eo?lyof Computirzg (19861, 316329. 5. 'Thoinas L. Iieatl?, Diophalzt~~s oj'Alcxa~zdria,Cainbridge TJniversity l'ress, 1910. 6, Anthony W. Knapp, EIIiptic Cwrue.7, Princeton University Psess, 1972. 7. Neal Kol~litz,Iiztroductiorz to EIl@licCuiives a ~ z dh"d~11arFou~~s, SpringerVerlag, 1984. 8, Neal Koblitz, Elliptic cuive cryptosystems, M~rlh.Conp. 48 (19871, 203209. 9. Hendrik W. Lenstra, Füctoring integers with elliptic ciiives, Aiz/znls oj' Mutl~cnzatics126 (1987), 649673. 10. Victor S. Miller, Use of elliptic cuives in ciyptography, A ~ ~ / L E i?z ~ z C?:yptologyCKYPTO c~s '85, Lecnire Notes in Coinputer Science 218 (17861, 417426, 11. Josepll H. Silverman and John Tate, Rational Poirzts on Ell@tic CLIIL)~. 4 one can have only a finite number of nontrivial solutions. Once
"A Marvelous Proof"
289
again, this is an impressive result, but its impact on FLT itself turns out to be minor because we have not yet found a way to actually determine how many solutions should exist. For an introduction to Faltings' work, check [CS86], which contains an English translation of the original paper. Wiles' attack on the problem turns on another such linkage, also developed in the early 1980s by G. Frey, J.P. Serre, and K. A. Ribet. This one connects FLT with the theory of elliptic cuwes, which has been much studied during al1 of this century, and thereby to al1 the machinery of modular forms and Galois representations that is the central theme of Wiles' work. The main goal of this paper is to describe this connection and then to explain how Wiles attempts to use it to prove FLT. Notation. We will use the usual symbols Q for the rational numbers and Z for the integers. The integers modulo m will be written' as H/mH; we will most often need them when m is a power of a prime number p. If p is prime, then Z/pZ is a field, and we commemorate that fact by using an alternative notation: ffp = H/pH. 2 THE ACTORS. We begin by introducing the main actors in the drama. First, we briefly (and very infomally) introduce the padic numbers. These are not so much actors in the play as they are part of the stage set: tools to allow the actors to do their job. Then we give brief and impressionistic outlines of the theories of Elliptic Curves, Modular Forms, and Galois Representations.
2.1 padic Numbers. The padic numbers are an extension of the field of rational numbers which are, in many ways, analogous to the real numbers. Like the real numbers, they can be obtained by defining a notion of distance between rational numbers, and then passing to the completion with respect to that distance. For our purposes, we do not really need to know much about them. The crucial facts are: 1. For each prime number p there exists a field Q, which is complete with respect to a certain notion of distance and contains the rational numbers as a dense subfield. 2. Proximity in the padic metric is closely related to congruence properties modulo p ~ w e r sof p. For example, two integers whose difference is divisible by p" are "close" in the padic world (the bigger the n, the closer they are). 3. As a consequence, one can think of the padics as encoding congruence information: whenever one knows something modulo pn for every n, one can translate this into padic information, and viceversa. 4. The field QP, contains a subring H,, which is called the ring of padic integers. (In fact, Z, is the closure of Z in Qp.) There is, of course, a lot more to say, and the reader will find it said in many references, such as [Kob84], [Cas86], [Ami75], and even [Gou93]. The padic nurnbers were introduced by K. Hensel (a student of Kummer), and many of the basic ideas seem to appear, in veiled form, in Kummer's work; since then, they have become a fundamental toa1 in number theory.
' ~ a elementary n ~ texts like to use ir, as the notation for the integers modulo m; for us (and for serious number theory in general), this notation is inconvenient because it collides with the notation for the padic integers described below.
Part VII: Elliptic Curves, Cubes and Fermat's Last Theorem
290
2.2 Elliptic Curves. Elliptic curves are a special kind2 of algebraic curves which have a very rich arithrnetical structure. There are several fancy ways of defining them, but for our purposes we can just define them as the set of points satisfying a polynomial equation of a certain form. To be specific, consider an equation of the form y2 alny a,y = x3 a 2 x 2 a,x a,, where the ai are integers (there is a reason for the strange choice of indices on the a,, but we won't go into it here). We want to consider the set of points (x, y) which satisfy this equation. Since we are doing number theory, we don7t want to tie ourselves down too seriously as to what sort of numbers x and y are: it makes sense to take them in the real numbers, in the complex nurnbers, in the rational numbers, and even, for any prime number p, in FP (in which case we think of the equation as a congruence modulo p). We will describe the situation by saying that there is an underlying object which we call the curve E and, for each one of the possible fields of definition for points (x, y), we call the set of possible solutions the "points of E" over that field. So, if we consider al1 possible complex solutions, we get the set E(C) of the complex points of E. Similarly, we can consider the real points E(!%),the rational points E(@, and even the FPpoints E(ffp). We haven't yet said when it is that such equations define elliptic curves. The condition is simply that the curve be smooth. If we consider the real or complex points, this means exactly what one would expect: the set of points cantains no "singular" points, that is, at every point there is a welldefined tangent line. We know, from elementary analysis, that an equation f(x, y) = O defines a smooth curve exactly when there are no points on the curve at which both partial derivatives of f vanish. In other words, the curve will be smooth if there are no common solutions of the equations
+
+
+
+
+
Notice, though, that this condition is really algebraic (the derivatives are dcrivatives of polynornials, and hence can be taken forrnally). In fact, we can boil it down to a (complicated) polynornial condition in the a,. There is a polynomial A(E) = A(al, a2, a,, a,, a,) in the a, such that E is smooth if and only if A(E) + O. This gives us tfie means to give a completely formal definition (which makes sense even over FP). The number A(E) is called the discriminant of the curve E. Definitiou 1. Let K be a field. An elliptic curve over K i.v an algebraic curve determined by an equation of the form Y 2 + alxy a,y = x3 + a2x2 + a4x a,, where each of the ai belongs to K and such that A(a,, a,, a,, a,, a,) # 0.
+
+
Specialists would want to rephrase that definition to allow other equations, provided that a wellchosen change of variables could transform them into equations of this form. '~erhaps it's best to dispel the obvious confusion right up front: ellipses are not elliptic curves. In fact, the connection between elliptic curves and ellipses is a rather subtie one. What happens is that elliptic curves (aver the complex numbers) are the "natural habitat" of the elliptic integrals which arise, among other places, when one attempts to compute the arc length of an ellipse. For US,this connection will be of very little irnportance.
"A Marvelous Proof"
29 1
It's about time to give some examples. To make things easier, let us focus on the special case in which the equation is of the form y2 = g(x), with g(x) a cubic polynomial (in other words, we're assuming a, = a, = O). In this case, it's very easy to determine when there can be singular points, and even what sort of singular points they will be. If we put f(x, y) = y2  g(x), then we have
af
af
(x, Y ) = gf(x) and (x, dx ay and the condition for a point to be "bad" becomes
y)
=
2y,
which boils down to y = g(x) = gf(x) = 0. In other words, a point will be bad exactly when its ycoordinate is zero and its xcoordinate is a double rmt of the polynomial g(x). Since g(x) is of degree 3, this gives us only three possibilities: g(x) has no multiple roots, and the equation defines an elliptic curve; g(x) has a double root; g(x) has a triple root. Let's look at one example of each case, and graph the real points of the corresponding curve. For the first case, consider the curve given by Y 2 = x3  X. Its graph is in figure 1 (a) (to be precise, this is the graph of its real points). A different example of the same case is given by y 2 = x3 + x; see figure l(b). (The reason these look so
(c) y 2 = x 3 + x 2 : a node
(d) y2 = x 3 : a cusp
292
Part VII: Elliptic Curves, Cubes and Fermat's Last Theorem
different is that we are only looking at the real points of the curve; in fact, over the complex numbers these two curves are isomorphic.) When there are "bad" points, what has happened is that either two roots of g(x) have "come together" or al1 three roots have done so. In the first case, we get a loop. At the crossing point, which is usually called a "node," the curve has two different tangent lines. See Figure l(c), where we have the graph of the equation y = x3 + x2 (double root at zero). In the final case, not only have al1 three roots of g(x) come together, but also the two tangents in the node have come together to form a sort of "double tangent" (this can be made precise with some easy algebra of polynomials, but it's more fun to think of it geometrically). The graph now looks like Figure l(d), and we cal1 this kind of singular point a "cusp". How does a11 this relate to the discrirninant A we mentioned above? Well, if r,, r2 and r, are the roots of the polynomial g(x), the discriminant for the equation y 2 = g(x) turns out to be where K is a constant. This does just what we want: if two of the roots are equal, it is zero, and if not, not, Furthermore, it is not too hard to see that A is actually a polynomial in the coefficients of g(x), which is what we claimed. In other words, al1 that the discriminant is doing for us is giving a direct algebraic procedure for determining whether there are singular points. While this analysis applies specifically to curves of the form y 2 = g(x), it actually extends to al1 equations of the sort we are considering: there is at most one singular point, and it is either a node or a cusp. One final geometric point: as one can see from the graphs, these curves are not closed. It is often convenient to "close them up," This is done by adding one more point to the curve, usually referred to as "the point at infinity." This can be done in a precise way by embedding the curve into the projective plane, and then taking the closure. For us, however, the only important thing is to remember that we actually have one extra point on our curves. (One should imagine it to be "infinitely far up the yaxis," but keep in mind that there is gnly one '"oint at infinity" on the yaxis, so that it is also "infinitely far down.") With some examples in hand, we can proceed to deeper waters. In order to understand the connection we are going to establish between elliptic curves and FLT, we need to review quite a large portion of what is known about the rich arithmetic structure of these curves. The first thing to note is that one can define an operation on the set of points of an elliptic curve that makes it, in a natural way, an abelian group. The operation is usually referred to as "addition." The identity element of this group turns out to be the point at infinity (it wouId be more honest to say that we choose the point at infinity for this role). Vire won't enter into the details of how one adds points on an elliptic curve. In fact, there are several equivalent definitions, each of which has its advantages! The reader should see the references for more details of how it is done (and the proof that one does get a group). The rnain thing to know about the definition, for now, is that it preserves the field of definition of the points: adding two rational points gives a rational point, and so on. What this means is that for every choice of a base field, we can get a group of points on the curve with coordinates in that field, so that in fact an elliptic curve gives us a whole bunch of groups, which are, of course, al1 related (though
"A Marvelous Proof"
293
sometimes related in a mysterious way). SO, given an E, we can look at the complex points E(G), which form a complex Lie group which is topologically a torus, or we can look at the real Lie group E(IW), which turns out to be either isomorphic to the circle S' or to the direct product Z/2Z X S'. ( h o k back at the examples above; can you see which is which?) From an arithmetical point of view, however, the most interesting of these groups is the group of rational points, E(Q). A point P E E(Q) gives a solution in rational numbers of our cubic equation, and looking for such solutions is, of course, an example of solving a diophantine equation, a sort of problem that is quite important in number theory. What is especially nice about E(0) is the fact, proved by L. Mordell (and extended by A. Weil) in the 1920s, that it is a finitely generated abelian group. What this means is just the following: there is a finite list of rational points on the curve (or, if one prefers, of rational solutions to the equation) such that every other rational solution is obtained by combining (using the addition law) these points with one another. These points are called the generators of the group E(@, which is usually called the MordellWeil group of E. The curves we considered earlier have very simple MordellWeil groups. For the curve given by y2 = x 3  x (figure la), it has four points; and for y2 = x 3 + x (figure lb) it has two. It is easy, though, to give more interesting examples. Here is one, chosen at random from [Cre92]: if E is the curve defined by y 2 + y = x 3  x2  2 x 2, the MordellWeil group E(Q) is an infinite cyclic group, generated by the point (2,l). Of course, knowing that we have a finitely generated group raises the obvious question of estimating or computing the number of generators needed and of how one might go about actually finding these generating points. Both of these questions are still open, even though there are rather precise conjectures about what their answers should be. For many specific curves, both the number and the generators themselves have been completely worked out (see, for example, the tables in [Cre92]), but the general problem still seems quite difficult. A fundamental component of the conjectural plan for determining the generators is considering, for each prime number p, the reduction of our curve modulo p. The basic idea is quite simple: since our equation has integer coefficients, we can reduce it modulo p" and look for solutions in the field iF, of integers modulo p. This should give a finite3 group E(Fp),whose structure should be easier to analyse than that of the big group E(Q). It7s a rather simple idea, but several complications4 arise. The main thing that can go wrong is that the reduction modulo p may fail to be an elliptic curve. That is actually very easy to see. To te11 whether the curve is elliptic (that is, if it has no singular points), orie needs to look at A. It is perfectly possible for A to be nonzero (so the curve over Q is elliptic) while being at the same time congruent to zero modulo p (so that the curve over iFp is singular). This pherromenon is called bad reduction, and it is easy to come up with examyles. One might take p = 5, and look at the curve y2 = x 3  5. This turns out to be an elliptic curve over Q, but its reduction modulo 5 is going to have a cusp. One says, then, that the curve has bad reduction at 5. In fact, the discriminant turns out to be
+
3 ~ ist finite because, apart from the point at infinity, there are only p2 possible points. In fact, the maximum possible number of points is smaller than that, but that fact takes ssome proving. 4 ~ may t seem a bit perverse to dwell on the nature of these complications, but it will turn out that we need to have at least some understanding of how this goes later on.
Part VII: Elliptic Curves, Cubes and Fermat's Last Theorem
A =  10800, which is clearly divisible by 2,3, and 5, so that the curve has bad reduction at each of these. (In each case, it's easy to verify that the reduced curve has a cusp.) We want to classify the possible types of reduction, but there is one further glitch that we have to deal with before we can do so. To see what it is, consider the curve y2 = x 3  625x. At first glance, it seems even worse than the first, and the discrirninant, which turns out to be A =  15625000000, looks uery divisible by 5. But look what we can do: let's change variables by setting x = 25u = S2u and y = 125v = s3v.Then our equation becomes which simplifies to and hence to
u 2 = u3  U, which is not only a nice elliptic curve, but has good reduction at 5. In other words, this example shows that curves which are isomorphic ouer Q can have very dffeent reductions modulo p. It turns out that among al1 the possible equations for our curve, one can choose an equation that is minimal, in the sense that its discriminant will be divisible by fewer primes than the discriminant for other equations. Since the primes that divide the discriminant are the primes of bad reduction, a minimal equation will have reduction properties that are as good as possible. When studying the reduction properties of the curve, then, one must also pass to such a minimal equation (and there are algorithms to do this). WelI, then, suppose we have done so, and have an elliptic curve E given by a minimal equation. Then we can classify al1 prime numbers into three groups: Primes of good reduction: those which do not divide the discrirninant of the minimal equation. The curve modu~op is an elliptic curve, and we have a group E(ffp). Primes of multiplicative reduction: those for which the curvk modulo p has a node. If the singular point is (x,, y,), it turns out that the set E(FP) {(x,, y,)) has a group structure, and is isomorphic to the multiplicative group FP  {O). Primes of additive reduction: those for which the curve modulo p has a cusp. If the singular point is (x,, y,), the set E(!Fp)  {(x,, y,)} once again has a group structure, and is isomorphic to the additive group iFp. No curve can have goad reduction everywhere, so there wiIl always be some bad primes, but the feeling one should get is that multiplicative reduction is somehow not as bad as additive reduction. There ar.e various technical reasons for this, which we don7treally need to go into. Instead, we codify the information about the reduction types of the curve into a number, called the conductor of the curve. We define the conductor to be a product N = FIpn(P),where 0 1 22
if E has good reduction at p if E has multiplicative reduction at p if E has additive reduction at p
(The exact value of n(p) for the case of additive reduction depends on some rather
"A Marvelous Proof"
295
subtle properties of the reduction modulo such primes; most of the time, the exponent is 2.) The result is that one can tell, by looking at the conductor, exactly what the reduction type of E at each prime is, The elliptic curves we will want to consider are those whose reduction properties are as good as possible. Since good reduction at al1 primes is not possible, we opt for the next best thing: good reduction at almost al1 primes, multiplicative reduction at the others. Such curves are called semistable: Definition 2. An elliptic curve is called semistable if al1 of its reductions are either good or multiplicative. Equivalently, a curve is semistable if its conductor is squarefree.
A crucial step in the application of Wiles' theorem to FLT will be verifying that a certain curve is semistable. Just to give us some reference points, let's look at a few examples. 1, Let E, be the curve y2 = x 3  5, which we considered above. One checks that this equation is, mininial, and that the curve has additive reduction at 2,3, and 5, so that it is not semistable. The conductor turns out to be equal to 10800 (essentially, the same as the discriminant!). 2. Let E, be the cuwe y 2 + y = x3 + x. This has multiplicative reduction at 7 and 13 (checking this rnakes a nice exercise) and good reduction at al1 other primes. Hence, E, is semistable and its conductor is 91. 3. Let E, be the curve y = x x + 2x + 2 (which is minimal). This has discriminant A =  1152 =  27 32, so that the bad primes are 2 and 3. It turns out that the reduction is multiplicative at 3 and additive at 2, and the conductor is 384; the curve is not semistable. 4, The main example for the purpose at hand: Let a, b, and c be relatively prime integers such that a b 4 c = O. Consider the curve Eabc whose equation5 is y2 = x(x  a)(x b). Depending on what a, b, and c are, this equation may or may not be minimal, so let's make the additional assumptions that a  1 (mod 4) and that b = O (mod 32). Xn this case, the equation is not minimal. A minimal equation for this curve turns out to be
+
+ +
which we get by the change in variables x + 4x, y + 8y + 4x. One can then compute that the discriminant is A = a2b2c2/256 (not surprising: a constant times the product of the squares of the differences of the roots of the original cubic), and that the curve is semistable. The primes of bad reduction are those that divide abc (this would be easy to see directly from the equation, by checking when there is a multiple root modulo p), and therefore the conductor is equal io the product of the primes that divide abc:
' ~ may t strike the reader as funny that c is absent from the equation. Keep in mind, however, that c is completely determined by a and b, so that it is really not as absent as al1 that. The crucial point is that the roots of the cubic on the right hand side are 0, a, and  b, so that the differences of the roots are (up to sign) exactly a, b, and c.
296
Part VII: Elliptic Curves, Cubes and Fermatls Last Theorem
(this number is sometimes called the radical of abc). We will be using curves of the form E,, (for very special a, b, and c) when we make the link with FLT. We need a final bit of elliptic curve theory. It is interesting to look at the number of points in the groups E(5,) as p ranges through the primes of good reduction for E. Part of the motivation for this is the reasoning that if the group E(Q) is large (i.e. there are many rational solutions), one would expect that for many choices of the prime p many of the points in E(Q) would survive reduction modulo p , so that the group E(ffp) would be large. Therefore, one would like to make some sort of conjecture that said that if the E(F,) are very large for many primes p, then the group E(Q) will be large. Elaborating and refining this idea leads to the conjecture of Birch and SwinnertonDyer, which we won7tget into here. But even this coarse version suggests that the variation of the size of as p runs through the primes should te11 us something about the arithmetic on the curve. To "encode" this variation, we start by observing that the (projective) line over iFp has exactly p + 1 points (the p elements of F ,, plus the point at infinity). We take this as the "standard" number of points for a curve over F,, and, when we look at E(ffp), record how far from the standard we are. To be precise, given an elliptic curve E and a prime number p at which E has good reduction, we define a number a, by the equation
For primes of bad reduction, we extend the definition in a convenient way; it turns out that we get a, = f1 when the reduction is multiplicative (with a precise rule to decide which) and a, = O when it is additive. The usual way to "record" the sequence of the a, is to use them to build a complex analytic function called the Lfinction of the curve E. It then is natural to conjecture that this Lfunction has properties similar to those of other Lfunctions that arise in number theory, and that one can read off properties of E from properties of its Lfunction. This is a huge story which we cannot te11 in this article, but which is really very close to some of the issues which we do discuss later on. Suffice it to say, for now, that we get a function
where the a, are exactly the same as the ones we just introduced, the a, are determined from the a, by "Euler product" expansion for the Lfunction, and the series can be shown to converge when Re(s) > 3/2. The Lfunction is conjectured to have an analytic continuation to the whole complex plane and to satis@ a certain functional equation, It is time to introduce the other actors in the play and to explain how they relate to elliptic curves. The reader who would like to delve further into this theory has a lot to choose from. As an informal introduction, one could look at J. Silverman7s article [Si193], which relates elliptic curves to "sums of twa cubes" and Ramanujan7s taxicab number. Various introductory texts are available, including [Cas91], [Wus87], [Kna92], [SilSó], and [ST92]. Each of these has particular strengths; the last is intended as an undergraduate text. In addition to these and other texts, the interested reader might enjoy looking at symbolic manipulation software that will handle elliptic curves well. Such capabilities are built into GPPARI and SIMATH, and can be added to Mathematica by using Silverman9s EllipticCurveCalc package
"A Marvelous Proof"
297
(which is what we used for most of the computations in this paper), and to Maple by using Conne117sApecs package. See[C 1, [Z '1,. [SVM], [Conl. +
2.3 Modular Porms, Modular forms start their lives as analytic objects (or, to be more honest, as objects of group representation theory), but end up playing a very intriguing role in number theory. In this section, we will uery briefly sketch out their definition and explain their relation to elliptic curves. Let 0 = { x + iy ly > O) be the complex upper halfplane. As is well known (and, in any case, easy to check), matrices in SL,(E) act on g in the following way. If y E SLz(Z) is the matrix
(so that a , b, c, and d are integers and ad  bc
=
l), and z
E
b7 we define
It is easy to check that if 2. E 6 then y z E b, and that y, * (y2 z ) = (y,y2) + r . We want to consider hnctions on the upper halfplane which are "as invariant as possible" under this action, perhaps when restricted to a smaller group. The subgroups we will need to consider are the "congruence subgroups" which we get by adding a congruence condition to the entries of the matrix. Thus, for any positive integer N, we want to look at the group
We are now ready to begin defining modular forms. They wiil be functions f :6 + @, holomorphic, which "transform well" under one of the subgroups T,(N). To be specific, we require that there exist an integer k such that
Applying this formula to the special case in which the rnatrix is
shows that any such function must satisfy f(z Fourier expansion
+ 1) = f(z), and hence must have a
00
f(z)
a,qn whereq =eZTiz.
=
n=
w
We require that this expression in fact oniy involve nonnegative powers of q (and in fact we extend that requirement to a finite number of other, similar, expansions, which the experts call the "Fourier expansions at the other cusps"). A function satisfying al1 of these constraints is called a modular form of weight k on To(N). The number N is usually called the Eeuel of the modular form f. We will need to consider one special subspace of the space of modular forms of a given weight and level. Rather than having a Fourier expansion with nonnegative powers only, we might require positiue powers only (in the main expansion and in the ones "at the other cusps"). We call such modular forms cusp forms; they,iJ +,''::. turn out to be the more interesting part of the space of modular forms. /
,,*PC