Number Theory: A Very Short Introduction
Page 12
By Fermat’s last theorem, discussed in Chapter 5, the equation has no non-zero solutions when . So this equation can have solutions only when at least one of the integers a, b, and c is 0: for example, and .
Can every number be written as the sum of six cubes?
In our discussion of Waring’s problem at the end of Chapter 5, we saw that 23, for example, requires at least nine cubes. However, as we remarked, every number from some point onwards can be written as the sum of seven cubes. It is not yet known whether ‘seven’ can be reduced to ‘six’.
Perfect numbers
In Chapter 3 we discussed perfect numbers, where a number n is perfect if the sum of all its proper factors (those different from n) is equal to n. The first four perfect numbers, known since the time of the Greeks, are 6, 28, 496, and 8128. The next two questions were discussed in Chapter 3.
What is the next perfect number after 8128?
After 8128 there is a large gap, and the next perfect number does not occur until 33,550,336.
Is there a formula for producing perfect numbers?
As we showed in Chapter 3, every number of the form , where is prime, is a perfect number, and all even perfect numbers can be written in this form—for example,
It is not yet known whether there are any odd perfect numbers.
Prime numbers
Prime numbers were discussed in Chapters 3 and 7. The next two questions were discussed at the beginning of Chapter 7, in the section on Two famous conjectures.
Does the list of twin primes go on for ever?
Twin primes are pairs of primes that differ by 2, and many examples are known. The twin prime conjecture is that there are infinitely many pairs of twin primes. It is generally believed to be true, but this has never been proved. Some related results are presented in Chapter 7.
Can every even number be written as the sum of two primes?
Another famous unanswered question is Goldbach’s conjecture, which asks whether every even number greater than 2 can be written as the sum of two primes. It is known to be true for all even numbers up to 400 trillion, but has not yet been proved in general.
In Chapter 7 we also saw how to construct strings of consecutive composite numbers of any desired length.
Is there a string of 1000 consecutive composite numbers?
As we saw in the section on The distribution of primes, an example of such a string of composite numbers is
In Chapter 5 we reduced the problem of deciding which numbers can be written as the sum of two squares to the corresponding problem for primes.
Which prime numbers can be written as the sum of two squares?
As we saw in the section on Sums of squares, every prime number of the form can be written in exactly one way as the sum of two squares, as can the prime 2 . However, no numbers of the form (and primes of this form, in particular) can be written as the sum of two squares.
The next two questions were discussed in Chapter 3 in connection with Mersenne and Fermat primes.
Is the number always prime when n is prime, and always composite when n is composite?
In our discussion of Mersenne primes, we saw that must be composite when n is composite. However, need not be prime when n is prime: for example, .
Are all numbers of the form , where n is a power of 2, prime?
In our discussion of Fermat primes, we saw that the first five ‘Fermat numbers’, , , , , and , are all prime. No other examples have ever been found.
The last two questions were discussed in Chapter 7, in the section on Primes in arithmetic progressions.
Are there infinitely many primes of the form ? or of the form ?
The answer to these questions is ‘yes’, and both can be proved by adapting Euclid’s proof that there are infinitely many primes. In the former case we also used the fact that −1 is a square (mod p) for any prime p of the form . These results can also be deduced directly from Dirichlet’s more general theorem on primes in arithmetic progressions, which states that there are infinitely many prime numbers of the form , where n is an integer, as long as .
Are there infinitely many primes with final digit 9?
Again, by Dirichlet’s theorem, there are infinitely many prime numbers of the form —that is, primes with final digit 9.
We have now reached the end of our story. Number theory continues to be an exciting part of modern mathematics, with many startling new developments over recent years. However, there are many parts of the subject that we have been unable to explore within these pages, and we hope that you will wish to continue your interest in the subject by referring to the items in our list of further reading.
Further reading
The following texts, some classic and others much newer, provide useful introductions to the various areas of number theory introduced in this book.
George E. Andrews, Number Theory, new edn, Dover Publications, 2000.
David M. Burton, Elementary Number Theory, 7th edn, McGraw-Hill, 1980.
H. Davenport, The Higher Arithmetic, 8th edn, Cambridge University Press, 2008.
Underwood Dudley, Elementary Number Theory, 2nd edn, Dover Publications, 2008.
Emil Grosswald, Topics from the Theory of Numbers, 2nd edn, Birkhäuser, 1984.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th edn (ed. D. R. Heath-Brown and J. H. Silverman), Oxford University Press, 2008.
Gareth A. Jones and J. Mary Jones, Elementary Number Theory, Springer, 1998.
Oystein Ore, Invitation to Number Theory, 2nd edn (revised and updated by John J. Watkins and Robin Wilson), Mathematical Association of America, 2017.
James J. Tattersall, Elementary Number Theory in Nine Chapters, 2nd edn, Cambridge University Press, 2005.
Martin H. Weissman, An Illustrated Theory of Numbers, American Mathematical Society, 2017.
More historical information can be found in:
Leonard Eugene Dickson, History of the Theory of Numbers, Vols. I, II, III, Dover Publications, 2005.
O. Ore, Number Theory and its History, Dover Publications, 1988.
John J. Watkins: Number Theory: A Historical Approach, Princeton University Press, 2014.
Popular books on the Riemann hypothesis, Fermat’s last theorem, and the twin prime conjecture are:
John Derbyshire, Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics, Plume Books, 2004.
Marcus du Sautoy, The Music of the Primes: Why an Unsolved Problem in Mathematics Matters, Harper/Perennial, 2004.
Vicky Neale, Closing the Gap: The Quest to Understand Prime Numbers, Oxford University Press, 2017.
Karl Sabbagh, Dr Riemann’s Zeros, Atlantic Books, 2003.
Simon Singh, Fermat’s Last Theorem, Fourth Estate, 1998.
More advanced books on specific topics include:
Tom M. Apostol, Introduction to Analytic Number Theory, 5th printing, Springer, 1998.
H. M. Edwards, Riemann’s Zeta Function, Dover Publications, 2003.
Barry Mazur and William Stein, Prime Numbers and the Riemann Hypothesis, Cambridge University Press, 2016.
Paulo Ribenboim, The Little Book of Bigger Primes, 2nd edn, Springer, 2010.
Ian Stewart and David Tall, Algebraic Number Theory and Fermat’s Last Theorem, 3rd edn, A. K. Peters / CRC Press, 2001.
An English translation of Gauss’s classic book of 1801 is:
Carl Friedrich Gauss, Disquisitiones Arithmeticae (trans. Arthur A. Clarke), Yale University Press, 1965.
Index
A
Adleman, L. 110
algorithm 23
al-Khwarizmi 24
almost prime 113
alternating sum 34
Ancient Greeks 2, 10, 53
arithmetic progression 124–5
B
Bachet de Méziriac, C. 89, 93–4
Baker, A. 129
Baker–Heegner–Stark theorem 129
Bernoulli, J. 134<
br />
birds problem 81–2, 144
C
calendars 63–6, 142
canonical form 44
card shuffling 1, 101–2, 144
Carmichael, R. 99
Carmichael number 100
Carroll, Lewis 65
Casting out nines 34–7, 62
census-taker puzzle 17
Chen Jingrun 113, 115
Chinese Remainder Theorem 71
cicada 20–1
Clay Mathematics Institute 130, 144
clock arithmetic 58–9, 63
Cocks, C. 110
Cole, F. N. 48
combination 16, 21
common divisor 20
common multiple 19
complex numbers 127–8, 137
complex plane 137–40
composite number 10–11, 38, 117, 148
congruences 58ff
congruent (mod n) 59
convergence of series 133
Conway, J. 65
counting necklaces 100
counting numbers 2
cryptography 4, 110–11
cubes 8–9, 29–30, 146–7
D
de la Vallée Poussin, C. 121–2
decimal system 31
Descartes, R. 51
difference of squares 87–8
digital root 35–6
digital sum 33
Diophantine equation 79, 144
Diophantus 2, 79, 85, 89, 93
Dirichlet, L. 96, 124–5, 130
Dirichlet’s theorem 124–5, 149
Disquisitiones Arithmeticae 2, 43, 58, 128
distribution of primes 116–22, 149
divides 14–16
divisibility 31–4, 61–2, 145
division rule 22
divisor 9, 14–19
divisor tests 30
Dodgson, C. L. 65
Dyson, F. 141
E
eggs problem 1, 49, 143
Eratosthenes 38
Erdős, P. 121
Euclid 2–3, 9, 22, 41, 50, 54, 122–3, 150
Euclid’s algorithm 22–7, 111
Euclid’s Elements 2, 9, 54
Euler, J. A. 91
Euler, L. 2–3, 46–7, 51–3, 87, 89, 95, 97, 112, 134–7
Euler product 136
Euler’s phi-function 103–6
Euler’s theorem 106–8, 110–11, 144
even number 5, 126
exponential function 120
F
factor 9, 14
factorial number 117
factorization 42–4
factorizing large numbers 108–10
Faro shuffling 101
Fermat, P. 2–3, 12, 51–2, 86–7, 89, 93, 95, 97–8, 108–9, 142, 146
Fermat number 13, 51, 53
Fermat prime 51–3, 55–6, 143–4, 149
Fermat’s ‘last theorem’ 2, 4, 92–6, 147
Fermat’s ‘little theorem’ 97–103, 106–8, 144
Fermat’s method, 108–9
Fibonacci, L. 26, 81
Fibonacci number 26
four-square theorem 89, 91
fundamental theorem of arithmetic 43–4
G
Gauss, C. F. 2–3, 55, 58, 65, 103, 128, 130, 139, 143
Gaussian integers 128
Germain, S. 95
GIMPS 49
Girard, A. 87
Goldbach, C. 112
Goldbach’s conjecture 112–14, 148
Gowers, T. 115
greatest common divisor 19–27, 44–5
Green, B. 126
Green–Tao theorem 126
Gregorian calendar 64
H
Hadamard, J. 121
Hardy, G. H. 90
harmonic series 134
Heegner, K. 128
Helfgott, H. 113–14
highest common factor 20
Hilbert, D. 91, 126
Humpty Dumpty 108
I
infinitely many primes 2, 41, 136, 150
infinite series 132–134
integer 4–6
ISBN number 34
J
Jingrun Chen 113, 115
Jones, J. 56
K
Kummer, E. 96
L
Lagrange, J. 2, 89
Lagrange’s four-square theorem 89, 91
Lamé, G. 96
law of quadratic reciprocity 77
least common multiple 17–19, 22, 44–5
Legendre, A.-M. 2, 75, 86, 89, 95–6, 124, 146
Legendre symbol 75
Lehmer, D. H. 62
Leibniz, G. 98
linear congruences 66–72
Lincoln, A. 36–7
logarithm, 120
Lucas, E. 47–8, 62
Lucas–Lehmer test 62
M
Maynard, J. 116
Mersenne, M. 12, 47–8, 87
Mersenne number 47–8
Mersenne prime 12, 46–50, 62–3, 149
method of infinite descent 95
Mills, W. H. 56
Mills’ constant 56
modular arithmetic 59
modulo 59
Montgomery, H. 141
multiple 5, 14–19
N
natural logarithm 120
necklaces 100
negative integer 5
number theory 2
number 6
O
odd number 5
P
perfect cube 8
perfect number 9–10, 49–51, 147
perfect square 1, 6, 143
phi function 103–6
pirates puzzle 67, 70–1
Platt, D. 113
Polignac, A. de 114
polygon 1, 53–6, 143–4
Polymath project 115–6
polynomial 56–7
Pope Gregory XIII 64
positive integer 5
postage stamp 36, 49, 96
prime number 2, 10–13, 38ff, 148–50
prime number theorem 117–22
primes in arithmetic progression 122–6, 149
primitive triple 82–5, 146
proof by contradiction 41
public key cryptography 110–11
Pythagorean theorem 7, 82
Pythagorean triple 82, 143
Pythagoreans 2, 6, 27
Q
quadratic reciprocity 77
quadratic residue 74
quadratic sieve method 108
quotient 22
R
Ramanujan, S. 90
reduction ad absurdum 41
regular polygon 1, 53–6, 143–4
regular prime 96
remainder 22
Riemann, B. 131–2, 138–40
Riemann hypothesis 1, 130, 138–41, 144–5
Riemann-zeta function 139–40
Riese, Adam 36–7
right-angled triangle 1, 7–8, 82–5, 143, 146
Rivest, R. 110
RSA encryption 110–11, 144
S
Sato, D. 56
Selberg, A. 121–2
self-replicating number 71–2
Shamir, A. 110
shuffling cards 1, 101–2, 144
sieve of Eratosthenes 38–40, 113
sieve methods 38–40, 110, 113, 115
simultaneous congruences 69–72
square-free number 128
squares 1, 6–7, 27–9, 61, 72–8, 143, 145–6
Stark, H. 128
sum of primes 11, 148
sum of squares 11–12, 85–90, 146, 148–9
Sunzi 69–71, 143
T
Tao, T.
115–16, 126
Taylor, R. 96
twin primes 11, 114, 148
twin prime conjecture, 114–16, 148
U
unique factorization 43–4, 126–9
V
Vinogradov, I. M. 113
W
Wada, H. 56
Waring, E. 91
Waring’s problem 91–2, 147
Wiens, D. 56
Wiles, A. 4, 96
Z
Zagier, D. 117–18, 141
zeros of zeta function 130, 139–41
zeta function 134–41, 144
Zhang, Y. 115
Economics
A Very Short Introduction
Partha Dasgupta
Economics has the capacity to offer us deep insights into some of the most formidable problems of life, and offer solutions to them too. Combining a global approach with examples from everyday life, Partha Dasgupta describes the lives of two children who live very different lives in different parts of the world: in the Mid-West USA and in Ethiopia. He compares the obstacles facing them, and the processes that shape their lives, their families, and their futures. He shows how economics uncovers these processes, finds explanations for them, and how it forms policies and solutions.
‘An excellent introduction . . . presents mathematical and statistical findings in straightforward prose.’
Financial Times
www.oup.com/vsi
Information
A Very Short Introduction
Luciano Floridi
Luciano Floridi, a philosopher of information, cuts across many subjects, from a brief look at the mathematical roots of information - its definition and measurement in ‘bits’ - to its role in genetics (we are information), and its social meaning and value. He ends by considering the ethics of information, including issues of ownership, privacy, and accessibility; copyright and open source. For those unfamiliar with its precise meaning and wide applicability as a philosophical concept, ‘information’ may seem a bland or mundane topic. Those who have studied some science or philosophy or sociology will already be aware of its centrality and richness. But for all readers, whether from the humanities or sciences, Floridi gives a fascinating and inspirational introduction to this most fundamental of ideas.
‘Splendidly pellucid.’
Steven Poole, The Guardian
www.oup.com/vsi
Innovation
A Very Short Introduction
Mark Dodgson & David Gann
This Very Short Introduction looks at what innovation is and why it affects us so profoundly. It examines how it occurs, who stimulates it, how it is pursued, and what its outcomes are, both positive and negative. Innovation is hugely challenging and failure is common, yet it is essential to our social and economic progress. Mark Dodgson and David Gann consider the extent to which our understanding of innovation developed over the past century and how it might be used to interpret the global economy we all face in the future.