Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                
Everand Logo

Welcome to Everand!

  • Discover millions of ebooks, audiobooks, and so much more with a free trial

    From $11.99/month after trial. Cancel anytime.

    Prime Numbers: The Most Mysterious Figures in Math
    Prime Numbers: The Most Mysterious Figures in Math
    Prime Numbers: The Most Mysterious Figures in Math
    Ebook518 pages5 hours

    Prime Numbers: The Most Mysterious Figures in Math

    By David Wells

    3/5

    ()

    Read preview

    About this ebook

    A fascinating journey into the mind-bending world of prime numbers

    Cicadas of the genus Magicicada appear once every 7, 13, or 17 years. Is it just a coincidence that these are all prime numbers? How do twin primes differ from cousin primes, and what on earth (or in the mind of a mathematician) could be sexy about prime numbers? What did Albert Wilansky find so fascinating about his brother-in-law's phone number?

    Mathematicians have been asking questions about prime numbers for more than twenty-five centuries, and every answer seems to generate a new rash of questions. In Prime Numbers: The Most Mysterious Figures in Math, you'll meet the world's most gifted mathematicians, from Pythagoras and Euclid to Fermat, Gauss, and Erd?o?s, and you'll discover a host of unique insights and inventive conjectures that have both enlarged our understanding and deepened the mystique of prime numbers. This comprehensive, A-to-Z guide covers everything you ever wanted to know--and much more that you never suspected--about prime numbers, including:
    * The unproven Riemann hypothesis and the power of the zeta function
    * The "Primes is in P" algorithm
    * The sieve of Eratosthenes of Cyrene
    * Fermat and Fibonacci numbers
    * The Great Internet Mersenne Prime Search
    * And much, much more
    LanguageEnglish
    PublisherTurner Publishing Company
    Release dateJan 13, 2011
    ISBN9781118045718
    Prime Numbers: The Most Mysterious Figures in Math
    Author

    David Wells

    David Wells was the British under-21 chess champion in 1961, and for many years he was puzzle editor of Games & Puzzles magazine. His books include The Penguin Dictionary of Curious and Interesting Puzzles.

    Read more from David Wells

    Related to Prime Numbers

    Related ebooks

    Mathematics For You

    View More
    View More

    Related podcast episodes

    Related articles

    • UNLIMITED

      The Math That Takes Newton Into the Quantum World

      Feb 28, 2019

      In my 50s, too old to become a real expert, I have finally fallen in love with algebraic geometry. As the name suggests, this is the study of geometry using algebra. Around 1637, René Descartes laid the groundwork for this subject by taking a plane,

      9 min read

    • UNLIMITED

      Math’s Beautiful Monsters

      Oct 26, 2017

      Much like its creator, Karl Weierstrass’ monster came from nowhere. After four years at university spent drinking and fencing, Weierstrass had left empty handed. He eventually took a teaching course and spent most of the 1850s as a schoolteacher in B

      10 min read

    • UNLIMITED

      How I Rewired My Brain to Become Fluent in Math: The building blocks of understanding are memorization and repetition.

      Sep 15, 2016

      I was a wayward kid who grew up on the literary side of life, treating math and science as if they were pustules from the plague. So it’s a little strange how I’ve ended up now—someone who dances daily with triple integrals, Fourier transforms, and t

      11 min read

    • UNLIMITED

      How to Solve the Hardest Logic Puzzle Ever: A step-by-step guide to True, False, and Random.

      Nov 5, 2015

      While a doctoral student at Princeton University in 1957, studying under a founder of theoretical computer science, Raymond Smullyan would occasionally visit New York City. On one of these visits, he met a “very charming lady musician” and, on their

      9 min read

    • UNLIMITED

      Actually, There Is a Time Like the Present

      Nov 30, 2017

      We’ve all heard it before: There’s no time like the present. Broadly speaking, of course, it means to “seize the opportunity right now,” or maybe in my case, to avoid procrastinating. From a psychological perspective, this makes a lot of sense. As hu

      4 min read

    • UNLIMITED

      The Twin Prime Hero: Rags, riches, and fame in mathematics.

      Dec 29, 2016

      Yitang “Tom” Zhang spent the seven years following the completion of his Ph.D. in mathematics floating between Kentucky and Queens, working for a chain of Subway restaurants, and doing odd accounting work. Now he is on a lecture tour that includes st

      8 min read

    • UNLIMITED

      Math After COVID-19

      Apr 28, 2020

      Math After COVID-19
      4 min read

    • UNLIMITED

      Math’s Beautiful Monsters: How a destructive idea paved the way for modern math.

      Apr 3, 2014

      Much like its creator, Karl Weierstrass’ monster came from nowhere. After four years at university spent drinking and fencing, Weierstrass had left empty handed. He eventually took a teaching course and spent most of the 1850s as a schoolteacher in B

      10 min read

    • UNLIMITED

      How I Rewired My Brain to Become Fluent in Math: Sorry, education reformers, it’s still memorization and repetition we need.

      Oct 2, 2014

      I was a wayward kid who grew up on the literary side of life, treating math and science as if they were pustules from the plague. So it’s a little strange how I’ve ended up now—someone who dances daily with triple integrals, Fourier transforms, and t

      11 min read

    • UNLIMITED

      Decimal Fractions

      Aug 30, 2024

      Decimal Fractions
      3 min read

    • UNLIMITED

      Fractions

      May 26, 2023

      Fractions
      3 min read

    • UNLIMITED

      Cryptic Classroom #4: Charades

      Oct 28, 2021

      Cryptic Classroom #4: Charades
      3 min read

    Related categories

    Reviews for Prime Numbers

    3/5

    11 ratings0 reviews

    What did you think?

    Tap to rate

    Review must be at least 10 words

      Book preview

      Prime Numbers - David Wells

      001

      Table of Contents

      Title Page

      Copyright Page

      Acknowledgments

      Author’s Note

      Introduction

      Entries A to Z

      abc conjecture

      abundant number

      AKS algorithm for primality testing

      aliquot sequences (sociable chains)

      almost-primes

      amicable numbers

      Andrica’s conjecture

      arithmetic progressions, of primes

      Aurifeuillian factorization

      average prime

      Bang’s theorem

      Bateman’s conjecture

      Beal’s conjecture, and prize

      Benford’s law

      Bernoulli numbers

      Bertrand’s postulate

      Bonse’s inequality

      Brier numbers

      Brocard’s conjecture

      Brun’s constant

      Buss’s function

      Carmichael numbers

      Catalan’s conjecture

      Catalan’s Mersenne conjecture

      Champernowne’s constant

      champion numbers

      Chinese remainder theorem

      cicadas and prime periods

      circle, prime

      circular prime

      Clay prizes, the

      compositorial

      concatenation of primes

      conjectures

      consecutive integer sequence

      consecutive numbers

      consecutive primes, sums of

      Conway’s prime-producing machine

      cousin primes

      Cullen primes

      Cunningham project

      Cunningham chains

      decimals, recurring (periodic)

      deficient number

      deletable and truncatable primes

      Demlo numbers

      descriptive primes

      Dickson’s conjecture

      digit properties

      Diophantus (c. AD 200; d. 284)

      Dirichlet’s theorem and primes in arithmetic series

      distributed computing

      divisibility tests

      divisors (factors)

      economical numbers

      Electronic Frontier Foundation

      elliptic curve primality proving

      emirp

      Eratosthenes of Cyrene, the sieve of

      Erdös, Paul (1913-1996)

      errors

      Euclid (c. 330-270 BC)

      Euler, Leonhard (1707-1783)

      factorial

      factorial primes

      factorial sums

      factorials, double, triple . . .

      factorization, methods of

      Feit-Thompson conjecture

      Fermat, Pierre de (1607-1665)

      Fermat-Catalan equation and conjecture

      Fibonacci numbers

      formulae for primes

      Fortunate numbers and Fortune’s conjecture

      gaps between primes and composite runs

      Gauss, Johann Carl Friedrich (1777-1855)

      Gilbreath’s conjecture

      GIMPS—Great Internet Mersenne Prime Search

      Giuga’s conjecture

      Goldbach’s conjecture

      good primes

      Grimm’s problem

      Hardy, G. H. (1877-1947)

      heuristic reasoning

      Hilbert’s 23 problems

      home prime

      hypothesis H

      illegal prime

      inconsummate number

      induction

      jumping champion

      k-tuples conjecture, prime

      knots, prime and composite

      Landau, Edmund (1877-1938)

      left-truncatable prime

      Legendre, A. M. ( 1752-1833)

      Lehmer, Derrick Norman (1867-1938)

      Lehmer, Derrick Henry (1905-1991)

      Linnik’s constant

      Liouville, Joseph (1809-1882)

      Littlewood’s theorem

      Lucas, Édouard (1842-1891)

      lucky numbers

      magic squares

      Matijasevic and Hilbert’s 10th problem

      Mersenne numbers and Mersenne primes

      Mertens constant

      Mertens theorem

      Mills’ theorem

      mixed bag

      multiplication, fast

      Niven numbers

      odd numbers as p + 2a

      Opperman’s conjecture

      palindromic primes

      pandigital primes

      Pascal’s triangle and the binomial coefficients

      patents on prime numbers

      Pépin’s test for Fermat numbers

      perfect numbers

      perfect, multiply

      permutable primes

      π, primes in the decimal expansion of

      Pocklington’s theorem

      Polignac’s conjectures

      powerful numbers

      primality testing

      prime number graph

      prime number theorem and the prime counting function

      prime pretender

      primitive prime factor

      primitive roots

      primorial

      Proth’s theorem

      pseudoperfect numbers

      pseudoprimes

      pseudoprimes, strong

      public key encryption

      pyramid, prime

      Pythagorean triangles, prime

      quadratic residues

      quadratic reciprocity, law of

      Ramanujan, Srinivasa (1887-1920)

      randomness, of primes

      record primes

      repunits, prime

      Rhonda numbers

      Riemann hypothesis

      Riesel number

      right-truncatable prime

      RSA algorithm

      RSA Factoring Challenge, the New

      Ruth-Aaron numbers

      Scherk’s conjecture

      semiprimes

      sexy primes

      Shank’s conjecture

      Siamese primes

      Sierpinski numbers

      Sloane’s On-Line Encyclopedia of Integer Sequences

      Smith numbers

      smooth numbers

      Sophie Germain primes

      squarefree numbers

      Stern prime

      strong law of small numbers

      triangular numbers

      trivia

      twin primes

      Ulam spiral

      unitary divisors

      untouchable numbers

      weird numbers

      Wieferich primes

      Wilson’s theorem

      Wolstenholme’s numbers, and theorems

      Woodall primes

      zeta mysteries: the quantum connection

      Appendix A: The First 500 Primes

      Appendix B: Arithmetic Functions

      Glossary

      Bibliography

      Index

      001

      Copyright © 2005 by David Wells. All rights reserved

      Published by John Wiley & Sons, Inc., Hoboken, New Jersey

      Published simultaneously in Canada

      No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 646-8600, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permissions.

      Limit of Liability/Disclaimer of Warranty: While the publisher and the author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor the author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

      For general information about our other products and services, please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.

      Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books. For more information about Wiley products, visit our web site at www.wiley.com.

      Library of Congress Cataloging-in-Publication Data:

      Wells, D. G. (David G.)

      Prime numbers: the most mysterious figures in math / David Wells. p. cm.

      Includes bibliographical references and index.

      ISBN-13 978-0-471-46234-7 (cloth)

      ISBN-10 0-471-46234-9 (cloth)

      1. Numbers, Prime. I. Title.

      QA246.W35 2005

      512.7’23—dc22

      2004019974

      Acknowledgments

      I am delighted to thank, once again, David Singmaster for his assistance and the use of his library: on this occasion I can also note that his thesis supervisor was D. H. Lehmer. I am happy to acknowledge the following permissions:

      The American Mathematical Society for permission to reproduce, slightly modified, the illustration on page 133 of prime knots with seven crossings or less from Pasolov and Sossinsky (1997), Knots, links, braids and 3-manifolds, Translations of Mathematical Monographs 154:33, Figure 3.13.

      Chris Caldwell for permission to reproduce, slightly modified, the graph on page 156 showing the Mersenne primes, from his Prime Pages Web site.

      The graph on page 184 comparing various historical estimates of the values of π(n) is in the public domain, but I am happy to note that it is adapted from the diagram on page 224 of Beiler (1966), Recreations in the Theory of Numbers, published by Dover Publications.

      Author’s Note

      Terms in bold, throughout the book, refer to entries in alphabetical order, or to entries in the list of contents, and in the index.

      Throughout this book, the word number will refer to a positive integer or whole number, unless stated otherwise.

      Letters stand for integers unless otherwise indicated.

      Notice the difference between the decimal point that is on the line, as in 1/8 = 0.125, and the dot indicating multiplication, above the line:

      20 = 2 · 2 · 5

      Divisor and factor: these are almost synonymous. Any differences are purely conventional. As Hugh Williams puts it, if a divides b, then "we call a a divisor (or factor) of b. Since 1 and a are always divisors of a, we call these factors the trivial divisors (or factors) of a." (Williams 1998, 2)

      On the other hand, we always talk about the prime factorization of a number, because no word like divisorization exists! For this reason, we also talk about finding the factors of a large number such as 2³¹ − 1.

      Similarly, by convention, the divisor function d(n), which is the number of divisors of n, is never called the factor function. And so on.

      The meanings of φ (n), σ (n), and d (n) are explained in the glossary.

      The natural logarithm of n, the log to base e, is written as log n. This does not mean the usual logarithm to base 10, which would be written log10 n.

      The expression 8 > 5 means that 8 is greater than 5. Similarly, 5 < 8 means that 5 is less than 8.

      The expression n ≥ 5 (5 ≤ n) means that n is greater than or equal to 5 (5 is less than or equal to n).

      The expression 4 | 12 means that 4 divides 12 exactly.

      The expression 4 002 13 means that 4 does not divide 13 exactly.

      Finally, instead of saying, When 30 is divided by 7 it leaves a remainder 2, it is much shorter and more convenient to write,

      30 ≡ 2 (mod 7)

      This is a congruence, and we say that 30 is congruent to 2, mod 7. The expression mod stands for modulus, because this is an example of modular arithmetic. The idea was invented by that great mathematician Gauss, and is more or less identical to the clock arithmetic that many readers will have met in school.

      In clock (or modular) arithmetic you count and add numbers as if going around a clockface. If the clockface goes from 1 to 7 only, then 8 is the same as 1, 9 = 2, 10 = 3, and so on.

      If, however, the clockface goes from 1 to 16 (for example), then 1 = 17, 2 = 18, and 3 · 9 = 11.

      If you count in (say) 8s around the traditional clockface showing 12 hours, then your count will go: 8, 4, 12, 8, 4, 12, repeating endlessly and missing all the hours except 4, 8, and 12. If you count in 5s, however, it goes like this: 5, 10, 3, 8, 1, 6, 11, 4, 9, 2, 7, 12, 5, and by the time you start to repeat you have visited every hour on the clock. This is because 8 and 12 have a common factor 4, and but 5 and 12 have no common factor.

      Mathematicians use the ≡ sign instead of =, the equal sign, to indicate that they are using modular arithmetic. So instead of saying that prime numbers are always of the form 6n + 1 or 6n − 1, because 6n + 2 and 6n + 4 are even and 6n + 3 is divisible by 3, we can write 6n ≡ ±1 (mod 6).

      Most statements made in this book have no reference. Either they are well-known, or they can be found in several places in the literature. Even if I do know where the claim was first made, a reference is not necessarily given, because this is a popular book, not a work of scholarship.

      However, where a result appears to be due to a specific author or collaboration of authors and is not widely known, I have given their names, such as (Fung and Williams). If a date is added, as in (Fung and Williams 1990), that means the reference is in the bibliography. If this reference is found in a particular book, it is given as (Fung and Williams: Guy).

      The sequences with references to Sloane and an A number are taken from Neil Sloane’s On-Line Encyclopedia of Integer Sequences, at www.research.att.com/~njas/sequences. See also the entry in this book for Sloane’s On-Line Encyclopedia of Integer Sequences, as well as the Some Prime Web Sites section at the end of the bibliography.

      The index is very full, but if you come across an expression such as φ(n) and want to know what it means, the glossary starting on page 251 will help.

      Introduction

      Prime numbers have always fascinated mathematicians. They appear among the integers seemingly at random, and yet not quite: there seems to be some order or pattern, just a little below the surface, just a little out of reach.

      —Underwood Dudley (1978)

      Small children when they first go to school learn that there are two things you can do to numbers: add them and multiply them. Addition sums are relatively easy, and addition has nice simple properties: 10 can be written as the sum of two numbers to make this pretty pattern:

      10 = 1 + 9 = 2 + 8 = 3 + 7 = 4 + 6 =

      5 + 5 = 6 + 4 = 7 + 3 = 8 + 2 = 9 + 1

      It is also easy to write even large numbers, like 34470251, as a sum: 34470251 = 34470194 + 57. The inverse of addition, subtraction, is pretty simple also.

      Multiplication is much trickier, and its inverse, division, is really quite hard; the simple pattern disappears, and writing 34470251 as a product is, well, fiendishly difficult. Suddenly, simple arithmetic has turned into difficult mathematics!

      The difficulty is easy to understand but hard to resolve. The fact is that some numbers, the composite numbers, can be written as a product of two other numbers, as we learn from our multiplication tables. These numbers start with: 2 × 2 is 4, 2 × 3 is 6, and 2 × 4 is 8, followed later by 3 × 3 is 9 and 6 × 7 is 42, and so on.

      Other numbers cannot be written as a product, except of themselves and 1. For example, 5 = 5 × 1 = 1 × 5, but that’s all. These are the mysterious prime numbers, whose sequence starts,

      2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,

      37, 41, 43, 47, 53, 59, 61, 67, 71, . . .

      Notice that 1 is an exception: it is not counted as a prime number, nor is it composite. This is because many properties of prime numbers are easier to state and have fewer exceptions if 1 is not prime. (Zero also is neither prime nor composite.)

      The prime numbers seem so irregular as to be random, although they are in fact determinate. This mixture of almost-randomness and pattern has enticed mathematicians for centuries, professional and amateur alike, to make calculations, spot patterns, make conjectures, and then (attempt) to prove them.

      Sometimes, their conjectures have been false. So many conjectures about primes are as elegant as they are simple, and the temptation to believe them, to believe that you have discovered a pattern in the primes, can be overwhelming—until you discover the counterexample that destroys your idea. As Henri Poincaré wrote, When a sudden illumination invades the mathematicians’s mind, . . . it sometimes happens . . . that it will not stand the test of verification . . . it is to be observed almost always that this false idea, if it had been correct, would have flattered our natural instincts for mathematical elegance. (Poincaré n.d.)

      Sometimes a conjecture has only been proved many years later. The most famous problem in mathematics today, by common consent, is a conjecture, the Riemann hypothesis, which dates from a brilliant paper published in 1859. Whoever finally proves it will become more famous than Andrew Wiles, who was splashed across the front pages when he finally proved Fermat’s Last Theorem in 1994.

      This fertility of speculation has given a special role to the modern electronic computer. In the good old bad old days, computer actually meant a person who computed, and a long and difficult task it could be for the mathematician who was not a human calculator like Euler or Gauss.

      Today, computers can generate data faster than it can be read, and can complete calculations in seconds or hours that would have taken a human calculator years—and the computer makes no careless mistakes. (The programmer may err, of course!) Computers also put you in touch with actual numbers, in a way that an abstract proof does not. As John Milnor puts it:

      If I can give an abstract proof of something, I’m reasonably happy. But if I can get a concrete, computational proof and actually produce numbers I’m much happier. I’m rather an addict at doing things on the computer. . . . I have a visual way of thinking, and I’m happy if I can see a picture of what I’m working with. (Bailey and Borwein 2000)

      It has even been seriously argued that mathematics is becoming more of an experimental science as a result of the computer, in which the role of proof is devalued. That is nonsense: it is only by penetrating below the surface glitter that mathematicians gain the deepest understanding. Why did Gauss publish six proofs of the law of quadratic reciprocity (and leave a seventh among his papers)? Because each proof illuminated the phenomenon from a different angle and deepened his understanding.

      Computers have had two other effects. The personal computer has encouraged thousands of amateurs to get stuck in and to explore the prime numbers. The result is a mass of material varying from the amusing but trivial to the novel, serious, and important.

      The second effect is that very complex calculations needed to prove that a large number is prime, or to find its factors, have suddenly become within reach. In 1876 Édouard Lucas proved that 2¹²⁷ − 1 is prime. It remained the largest known prime of that form until 1951. Today, a prime of this size can be proved prime in a few seconds, though the problem of factorization remains intractable for large numbers, so public key encryption and methods such as the RSA algorithm have recently made prime numbers vitally important to business (and the military).

      Despite the thousands of mathematicians working on properties of the prime numbers, numerous conjectures remain unresolved. Computers are wonderful at creating data, and not bad at finding counterexamples, but they prove nothing. Many problems and conjectures about prime numbers will only be eventually solved through deeper and deeper insight, and for the time being seem to be beyond our understanding. As Gauss put it, It is characteristic of higher arithmetic that many of its most beautiful theorems can be discovered by induction with the greatest of ease but have proofs that lie anywhere but near at hand and are often found only after many fruitless investigations with the aid of deep analysis and lucky combinations. See our entry on zeta mysteries: the quantum connection! Gauss added, referring to his own methods of working as well as those of Fermat and Euler and others:

      [I]t often happens that many theorems, whose proof for years was sought in vain, are later proved in many different ways. As soon as a new result is discovered by induction, one must consider as the first requirement the finding of a proof by any possible means [emphasis added]. But after such good fortune, one must not in higher arithmetic consider the investigation closed or view the search for other proofs as a superfluous luxury. For sometimes one does not at first come upon the most beautiful and simplest proof, and then it is just the insight into the wonderful concatenation of truth in higher arithmetic that is the chief attraction for study and often leads to the discovery of new truths. For these reasons the finding of new proofs for known truths is often at least as important as the discovery itself. (Gauss 1817)

      The study of the primes brings in every style and every level of mathematical thinking, from the simplest pattern spotting (often misleading, as we have noted) to the use of statistics and advanced counting techniques, to scientific investigation and experiment, all the way to the most abstract concepts and most subtle proofs that depend on the unparalleled insight and intuitive perceptions of the greatest mathematicians. Prime numbers offer a wonderful field for exploration by amateurs and professionals alike.

      This is not a treatise or an historical account, though it contains many facts, historical and otherwise. Rather, it is an introduction to the fascination and beauty of the prime numbers. Here is an example that I have occasionally used to, successfully, persuade nonbelievers with no mathematical background that mathematics can indeed be delightful. First write down the square numbers, 1 · 1 = 1, 2 · 2 = 4, 3 · 3 = 9, and so on. (Notice that to avoid using the × for multiplication, because x is also used in algebra, we use a dot above the text baseline.)

      1 4 9 16 25 36 49 64 81 100 . . .

      This sequence is especially simple and regular. Indeed, we don’t even need to multiply any numbers to get it. We could just as well have started with 1 and added the odd numbers. 1 + 3 = 4; 4 + 5 = 9; 9 + 7 = 16, and so on.

      Now write down the prime numbers, the numbers with no factors except themselves and 1:

      2 3 5 7 11 13 17 19 23 29 . . .

      No such simplicity here! The jumps from one number to the next vary irregularly from 1 to 6 (and would eventually become much larger). Yet there is a concealed pattern connecting these two sequences. To see it, strike out 2, which is the only even prime, and all the primes that are one less than a multiple of 4; so we delete 3, 7, 11, 19, and 23 . . . The sequence of remaining primes goes,

      5 13 17 29 37 41 53 57 61 73 . . .

      And the connection? Every one of these primes is the sum of two squares, of two of the numbers in the first sequence, in a unique way:

      5 = 1 + 4, 13 = 4 + 9, 17 = 1 + 16, 29 = 4 + 25, 37 = 1 + 36

      and so on. This extraordinary fact is related to Pythagoras’s theorem about the sides of a right-angled triangle, and was known to Diophantus in the third century. It was explored further by Fermat, and then by Euler and Gauss and a host of other great mathematicians. We might justly say that it has been the mental springboard and the mysterious origin of a large portion of the theory of numbers—and yet the basic facts of the case can be explained to a school pupil.

      There lies the fascination of the prime numbers. They combine the maximum of simplicity with the maximum of depth and mystery. On a plaque attached to the NASA deep space probe we are described in symbols for the benefit of any aliens who might meet the spacecraft as bilaterally symmetrical, sexually differentiated bipeds located on one of the outer spirals of the Milky Way, capable of recognizing the prime numbers and moved by one extraordinary quality that lasts longer than all our other urges—curiosity.

      I hope that you will discover (or be reminded of ) some of the fascination of the primes in this book. If you are hooked, no doubt you will want to look at other books—there is a selection of recommended books marked in the bibliography with an asterisk—and you will also find a vast amount of material on the Internet: some of the best sites are listed at the Some Prime Web Sites section at the end of the bibliography. To help you with your own research, Appendix A is a list of the first 500 primes, and Appendix B lists the first 80 values of the most common arithmetic functions.

      Note: As this book went to press, the record for the largest known prime number was broken by Dr. Martin Nowak, a German eye specialist who is a member of the worldwide GIMPS (Great Internet Mersenne Prime Search) project, after fifty days of searching on his 2.4GHz Pentium 4 personal computer. His record prime is 2²⁵,⁹⁶⁴,⁹⁵¹ − 1 and has 7,816,230 digits.

      Entries A to Z

      abc conjecture

      The abc conjecture was first proposed by Joseph Oesterlé and David Masser in 1985. It concerns the product of all the distinct prime factors of n, sometimes called the radical of n and written r (n). If n is squarefree (not divisible by any perfect square), then r(n) = n. On the other hand, for a number such as 60 = 2² · 3 · 5, r (60) = 2 · 3 · 5 = 30. r(n) is smallest when n is a power of a prime: then r(pq) = p. So r (8) = r (32) = r (256) = 2, and r(6561) = r(3⁸) = 3.

      The more duplicated factors n has, the larger n will be compared to r(n). For example, if n = 9972 = 2² · 3² · 277, then r(9972) = 1662, and r(n) = ¼n.

      The abc conjecture says, roughly, that if a and b are two numbers with no common factor, and sum c, then the number abc cannot be very composite. More precisely, David Masser proved that the ratio r(abc)/c can be as small as you like. Less than ¹⁄100? Yes! Less than 0.00000001? Yes! And so on.

      However—and this is Masser’s claim and the abc conjecture—this is only just possible. If we calculate r (abc)n/c instead, where n is any number greater than 1, then we can’t make r (abc)/c as small as we like, and this is true even if n is only slightly greater than 1. So even if n is as small as 1.00001, r(abc)n/c has a lower limit that isn’t zero.

      Why is this conjecture about numbers that are not squarefree so important? Because, incredibly, so many important theorems could be proved quite easily, if it were true. Here are just five of the many consequences of the abc conjecture being true:

      • Fermat’s Last Theorem could be proved very easily. The proof by Andrew Wiles is extremely long and complex.

      • There are infinitely many Wieferich primes.

      • There is only a finite number of sets of three consecutive powerful numbers.

      • There is only a finite number of solutions satisfying Brocard’s equation, n! + 1 = m².

      • All the polynomials (x n − 1)/(x − 1) have an infinity of squarefree values.

      Enjoying the preview?
      Page 1 of 1