Prime numbers

PRIME

NUMBERS

The Most Mysterious

Figures in Math

David Wells

John Wiley & Sons, Inc.

ffirs.qxd 3/22/05 12:12 PM Page i

ffirs.qxd 3/22/05 12:12 PM Page i

PRIME

NUMBERS

The Most Mysterious

Figures in Math

David Wells

John Wiley & Sons, Inc.

ffirs.qxd 3/22/05 12:12 PM Page i

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

Printed in the United States of America

10 9 8 7 6 5 4 3 2 1

ffirs.qxd 3/22/05 12:12 PM Page ii

Contents

Acknowledgments xi

Author’s Note xiii

Introduction 1

Entries A to Z

abc conjecture 6

abundant number 7

AKS algorithm for primality testing 8

aliquot sequences (sociable chains) 9

almost-primes 11

amicable numbers 11

amicable curiosities 12

Andrica’s conjecture 13

arithmetic progressions, of primes 13

Aurifeuillian factorization 14

average prime 15

Bang’s theorem 16

Bateman’s conjecture 16

Beal’s conjecture, and prize 16

Benford’s law 17

Bernoulli numbers 19

Bernoulli number curiosities 20

Bertrand’s postulate 20

Bonse’s inequality 21

Brier numbers 21

Brocard’s conjecture 22

Brun’s constant 22

Buss’s function 23

Carmichael numbers 23

Catalan’s conjecture 24

Catalan’s Mersenne conjecture 25

Champernowne’s constant 26

ftoc.qxd 3/22/05 12:13 PM Page iii

champion numbers 26

Chinese remainder theorem 26

cicadas and prime periods 27

circle, prime 27

circular prime 28

Clay prizes, the 28

compositorial 29

concatenation of primes 29

conjectures 30

consecutive integer sequence 32

consecutive numbers 32

consecutive primes, sums of 32

Conway’s prime-producing machine 33

cousin primes 33

Cullen primes 34

Cunningham project 34

Cunningham chains 35

decimals, recurring (periodic) 36

the period of 1/13 36

cyclic numbers 37

Artin’s conjecture 38

the repunit connection 38

magic squares 39

deficient number 40

deletable and truncatable primes 40

Demlo numbers 40

descriptive primes 41

Dickson’s conjecture 41

digit properties 42

Diophantus (c. AD 200; d. 284) 42

Dirichlet’s theorem and primes in arithmetic series 44

primes in polynomials 45

distributed computing 45

divisibility tests 48

divisors (factors) 48

how many divisors? how big is d(n)? 49

record number of divisors 50

curiosities of d(n) 50

divisors and congruences 51

the sum of divisors function 51

the size of σ(n) 52

iv • Contents

ftoc.qxd 3/22/05 12:13 PM Page iv

a recursive formula 52

divisors and partitions 53

curiosities of σ(n) 53

prime factors 54

divisor curiosities 54

economical numbers 55

Electronic Frontier Foundation 55

elliptic curve primality proving 56

emirp 57

Eratosthenes of Cyrene, the sieve of 58

Erdös, Paul (1913–1996) 59

his collaborators and Erdös numbers 61

errors 63

Euclid (c. 330–270 BC) 64

unique factorization 65

2 is irrational 65

Euclid and the infinity of primes 66

consecutive composite numbers 67

primes of the form 4n + 3 67

a recursive sequence 67

Euclid and the first perfect number 68

Euclidean algorithm 68

Euler, Leonhard (1707–1783) 69

Euler’s convenient numbers 70

the Basel problem 72

Euler’s constant 73

Euler and the reciprocals of the primes 73

Euler’s totient (phi) function 74

Carmichael’s totient function conjecture 75

curiosities of φ(n) 77

Euler’s quadratic 77

the Lucky Numbers of Euler 78

factorial 80

factors of factorials 80

factorial primes 80

factorial sums 81

factorials, double, triple . . . 82

factorization, methods of 82

factors of particular forms 84

Fermat’s algorithm 85

Legendre’s method 86

Contents • v

ftoc.qxd 3/22/05 12:13 PM Page v

congruences and factorization 87

how difficult is it to factor large numbers? 87

quantum computation 88

Feit-Thompson conjecture 89

Fermat, Pierre de (1607–1665) 89

Fermat’s Little Theorem 91

Fermat quotient 92

Fermat and primes of the form x2 + y2 92

Fermat’s conjecture, Fermat numbers, and Fermat primes 94

Fermat factorization, from F5 to F30 95

Generalized Fermat numbers 97

Fermat’s Last Theorem 97

the first case of Fermat’s Last Theorem 99

Wall-Sun-Sun primes 99

Fermat-Catalan equation and conjecture 100

Fibonacci numbers 101

divisibility properties 102

Fibonacci curiosities 103

Édouard Lucas and the Fibonacci numbers 104

Fibonacci composite sequences 105

formulae for primes 106

Fortunate numbers and Fortune’s conjecture 108

gaps between primes and composite runs 109

Gauss, Johann Carl Friedrich (1777–1855) 110

Gauss and the distribution of primes 111

Gaussian primes 112

Gauss’s circle problem 113

Gilbreath’s conjecture 113

GIMPS—Great Internet Mersenne Prime Search 115

Giuga’s conjecture 116

Giuga numbers 116

Goldbach’s conjecture 117

good primes 119

Grimm’s problem 119

Hardy, G. H. (1877–1947) 119

Hardy-Littlewood conjectures 121

heuristic reasoning 123

a heuristic argument by George Pólya 123

Hilbert’s 23 problems 124

home prime 125

hypothesis H 126

vi • Contents

ftoc.qxd 3/22/05 12:13 PM Page vi

illegal prime 126

inconsummate number 128

induction 128

jumping champion 131

k-tuples conjecture, prime 131

knots, prime and composite 132

Landau, Edmund (1877–1938) 134

left-truncatable prime 134

Legendre, A. M. (1752–1833) 134

Lehmer, Derrick Norman (1867–1938) 135

Lehmer, Derrick Henry (1905–1991) 135

Linnik’s constant 137

Liouville, Joseph (1809–1882) 137

Littlewood’s theorem 138

the prime numbers race 138

Lucas, Édouard (1842–1891) 139

the Lucas sequence 142

primality testing 144

Lucas’s game of calculation 145

the Lucas-Lehmer test 146

lucky numbers 147

the number of lucky numbers and primes 148

“random” primes 148

magic squares 149

Matijasevic and Hilbert’s 10th problem 150

Mersenne numbers and Mersenne primes 151

Mersenne numbers 152

hunting for Mersenne primes 152

the coming of electronic computers 153

Mersenne prime conjectures 155

the New Mersenne conjecture 156

how many Mersenne primes? 156

Eberhart’s conjecture 157

factors of Mersenne numbers 157

Lucas-Lehmer test for Mersenne primes 158

Mertens constant 159

Mertens theorem 159

Mills’ theorem 160

Wright’s theorem 161

mixed bag 161

multiplication, fast 162

Contents • vii

ftoc.qxd 3/22/05 12:13 PM Page vii

Niven numbers 163

odd numbers as p + 2a2 164

Opperman’s conjecture 164

palindromic primes 164

pandigital primes 165

Pascal’s triangle and the binomial coefficients 165

Pascal’s triangle and Sierpinski’s gasket 167

Pascal triangle curiosities 167

patents on prime numbers 168

Pépin’s test for Fermat numbers 169

perfect numbers 170

odd perfect numbers 172

perfect, multiply 172

permutable primes 174

π, primes in the decimal expansion of 174

Pocklington’s theorem 175

Polignac’s conjectures 175

Polignac or obstinate numbers 175

powerful numbers 176

primality testing 177

probabilistic methods 179

prime number graph 180

prime number theorem and the prime counting function 181

history 181

elementary proof 182

record calculations 183

estimating p(n) 185

calculating p(n) 185

a curiosity 185

prime pretender 186

primitive prime factor 187

primitive roots 187

Artin’s conjecture 188

a curiosity 188

primorial 188

primorial primes 189

Proth’s theorem 189

pseudoperfect numbers 190

pseudoprimes 190

bases and pseudoprimes 192

viii • Contents

ftoc.qxd 3/22/05 12:13 PM Page viii

pseudoprimes, strong 192

public key encryption 193

pyramid, prime 194

Pythagorean triangles, prime 195

quadratic residues 195

residual curiosities 196

polynomial congruences 196

quadratic reciprocity, law of 197

Euler’s criterion 198

Ramanujan, Srinivasa (1887–1920) 198

highly composite numbers 199

randomness, of primes 200

Von Sternach and a prime random walk 202

record primes 203

some records 203

repunits, prime 204

Rhonda numbers 206

Riemann hypothesis 206

the Farey sequence and the Riemann hypothesis 209

the Riemann hypothesis and σ(n), the sum of divisors

function 210

squarefree and blue and red numbers 210

the Mertens conjecture 211

Riemann hypothesis curiosities 211

Riesel number 212

right-truncatable prime 212

RSA algorithm 212

Martin Gardner’s challenge 214

RSA Factoring Challenge, the New 215

Ruth-Aaron numbers 216

Scherk’s conjecture 217

semi-primes 217

sexy primes 218

Shank’s conjecture 218

Siamese primes 219

Sierpinski numbers 219

Sierpinski strings 219

Sierpinski’s quadratic 219

Sierpinski’s φ(n) conjecture 219

Sloane’s On-Line Encyclopedia of Integer Sequences 220

Contents • ix

ftoc.qxd 3/22/05 12:13 PM Page ix

Smith numbers 221

Smith brothers 222

smooth numbers 222

Sophie Germain primes 223

safe primes 224

squarefree numbers 224

Stern prime 225

strong law of small numbers 225

triangular numbers 228

trivia 228

twin primes 229

twin curiosities 230

Ulam spiral 232

unitary divisors 233

unitary perfect 234

untouchable numbers 235

weird numbers 235

Wieferich primes 235

Wilson’s theorem 236

twin primes 237

Wilson primes 237

Wolstenholme’s numbers, and theorems 238

more factors of Wolstenholme numbers 239

Woodall primes 240

zeta mysteries: the quantum connection 241

Appendix A: The First 500 Primes 245

Appendix B: Arithmetic Functions 249

Glossary 251

Bibliography 253

Index 265

x • Contents

ftoc.qxd 3/22/05 12:13 PM Page x

Acknowledgments

I am delighted to thank, once again, David Singmaster for his assis￾tance 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 Mono￾graphs 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), Recre￾ations in the Theory of Numbers, published by Dover Publications.

flast.qxd 3/22/05 12:12 PM Page xi

flast.qxd 3/22/05 12:12 PM Page xii