by Robin Wilson
THE MONGOLS Morris Rossabi
MOONS David A. Rothery
MORMONISM Richard Lyman Bushman
MOUNTAINS Martin F. Price
MUHAMMAD Jonathan A. C. Brown
MULTICULTURALISM Ali Rattansi
MULTILINGUALISM John C. Maher
MUSIC Nicholas Cook
MYTH Robert A. Segal
NAPOLEON David Bell
THE NAPOLEONIC WARS Mike Rapport
NATIONALISM Steven Grosby
NATIVE AMERICAN LITERATURE Sean Teuton
NAVIGATION Jim Bennett
NAZI GERMANY Jane Caplan
NELSON MANDELA Elleke Boehmer
NEOLIBERALISM Manfred Steger and Ravi Roy
NETWORKS Guido Caldarelli and Michele Catanzaro
THE NEW TESTAMENT Luke Timothy Johnson
THE NEW TESTAMENT AS LITERATURE Kyle Keefer
NEWTON Robert Iliffe
NIELS BOHR J. L. Heilbron
NIETZSCHE Michael Tanner
NINETEENTH–CENTURY BRITAIN Christopher Harvie and H. C. G. Matthew
THE NORMAN CONQUEST George Garnett
NORTH AMERICAN INDIANS Theda Perdue and Michael D. Green
NORTHERN IRELAND Marc Mulholland
NOTHING Frank Close
NUCLEAR PHYSICS Frank Close
NUCLEAR POWER Maxwell Irvine
NUCLEAR WEAPONS Joseph M. Siracusa
NUMBER THEORY Robin Wilson
NUMBERS Peter M. Higgins
NUTRITION David A. Bender
OBJECTIVITY Stephen Gaukroger
OCEANS Dorrik Stow
THE OLD TESTAMENT Michael D. Coogan
THE ORCHESTRA D. Kern Holoman
ORGANIC CHEMISTRY Graham Patrick
ORGANIZATIONS Mary Jo Hatch
ORGANIZED CRIME Georgios A. Antonopoulos and Georgios Papanicolaou
ORTHODOX CHRISTIANITY A. Edward Siecienski
PAGANISM Owen Davies
PAIN Rob Boddice
THE PALESTINIAN-ISRAELI CONFLICT Martin Bunton
PANDEMICS Christian W. McMillen
PARTICLE PHYSICS Frank Close
PAUL E. P. Sanders
PEACE Oliver P. Richmond
PENTECOSTALISM William K. Kay
PERCEPTION Brian Rogers
THE PERIODIC TABLE Eric R. Scerri
PHILOSOPHY Edward Craig
PHILOSOPHY IN THE ISLAMIC WORLD Peter Adamson
PHILOSOPHY OF BIOLOGY Samir Okasha
PHILOSOPHY OF LAW Raymond Wacks
PHILOSOPHY OF SCIENCE Samir Okasha
PHILOSOPHY OF RELIGION Tim Bayne
PHOTOGRAPHY Steve Edwards
PHYSICAL CHEMISTRY Peter Atkins
PHYSICS Sidney Perkowitz
PILGRIMAGE Ian Reader
PLAGUE Paul Slack
PLANETS David A. Rothery
PLANTS Timothy Walker
PLATE TECTONICS Peter Molnar
PLATO Julia Annas
POETRY Bernard O’Donoghue
POLITICAL PHILOSOPHY David Miller
POLITICS Kenneth Minogue
POPULISM Cas Mudde and Cristóbal Rovira Kaltwasser
POSTCOLONIALISM Robert Young
POSTMODERNISM Christopher Butler
POSTSTRUCTURALISM Catherine Belsey
POVERTY Philip N. Jefferson
PREHISTORY Chris Gosden
PRESOCRATIC PHILOSOPHY Catherine Osborne
PRIVACY Raymond Wacks
PROBABILITY John Haigh
PROGRESSIVISM Walter Nugent
PROHIBITION W. J. Rorabaugh
PROJECTS Andrew Davies
PROTESTANTISM Mark A. Noll
PSYCHIATRY Tom Burns
PSYCHOANALYSIS Daniel Pick
PSYCHOLOGY Gillian Butler and Freda McManus
PSYCHOLOGY OF MUSIC Elizabeth Hellmuth Margulis
PSYCHOPATHY Essi Viding
PSYCHOTHERAPY Tom Burns and Eva Burns-Lundgren
PUBLIC ADMINISTRATION Stella Z. Theodoulou and Ravi K. Roy
PUBLIC HEALTH Virginia Berridge
PURITANISM Francis J. Bremer
THE QUAKERS Pink Dandelion
QUANTUM THEORY John Polkinghorne
RACISM Ali Rattansi
RADIOACTIVITY Claudio Tuniz
RASTAFARI Ennis B. Edmonds
READING Belinda Jack
THE REAGAN REVOLUTION Gil Troy
REALITY Jan Westerhoff
RECONSTRUCTION Allen. C. Guelzo
THE REFORMATION Peter Marshall
RELATIVITY Russell Stannard
RELIGION IN AMERICA Timothy Beal
THE RENAISSANCE Jerry Brotton
RENAISSANCE ART Geraldine A. Johnson
RENEWABLE ENERGY Nick Jelley
REPTILES T. S. Kemp
REVOLUTIONS Jack A. Goldstone
RHETORIC Richard Toye
RISK Baruch Fischhoff and John Kadvany
RITUAL Barry Stephenson
RIVERS Nick Middleton
ROBOTICS Alan Winfield
ROCKS Jan Zalasiewicz
ROMAN BRITAIN Peter Salway
THE ROMAN EMPIRE Christopher Kelly
THE ROMAN REPUBLIC David M. Gwynn
ROMANTICISM Michael Ferber
ROUSSEAU Robert Wokler
RUSSELL A. C. Grayling
RUSSIAN HISTORY Geoffrey Hosking
RUSSIAN LITERATURE Catriona Kelly
THE RUSSIAN REVOLUTION S. A. Smith
THE SAINTS Simon Yarrow
SAVANNAS Peter A. Furley
SCEPTICISM Duncan Pritchard
SCHIZOPHRENIA Chris Frith and Eve Johnstone
SCHOPENHAUER Christopher Janaway
SCIENCE AND RELIGION Thomas Dixon
SCIENCE FICTION David Seed
THE SCIENTIFIC REVOLUTION Lawrence M. Principe
SCOTLAND Rab Houston
SECULARISM Andrew Copson
SEXUAL SELECTION Marlene Zuk and Leigh W. Simmons
SEXUALITY Véronique Mottier
SHAKESPEARE’S COMEDIES Bart van Es
SHAKESPEARE’S SONNETS AND POEMS Jonathan F. S. Post
SHAKESPEARE’S TRAGEDIES Stanley Wells
SIKHISM Eleanor Nesbitt
THE SILK ROAD James A. Millward
SLANG Jonathon Green
SLEEP Steven W. Lockley and Russell G. Foster
SOCIAL AND CULTURAL ANTHROPOLOGY John Monaghan and Peter Just
SOCIAL PSYCHOLOGY Richard J. Crisp
SOCIAL WORK Sally Holland and Jonathan Scourfield
SOCIALISM Michael Newman
SOCIOLINGUISTICS John Edwards
SOCIOLOGY Steve Bruce
SOCRATES C. C. W. Taylor
SOUND Mike Goldsmith
SOUTHEAST ASIA James R. Rush
THE SOVIET UNION Stephen Lovell
THE SPANISH CIVIL WAR Helen Graham
SPANISH LITERATURE Jo Labanyi
SPINOZA Roger Scruton
SPIRITUALITY Philip Sheldrake
SPORT Mike Cronin
STARS Andrew King
STATISTICS David J. Hand
STEM CELLS Jonathan Slack
STOICISM Brad Inwood
STRUCTURAL ENGINEERING David Blockley
STUART BRITAIN John Morrill
SUPERCONDUCTIVITY Stephen Blundell
SUPERSTITION Stuart Vyse
SYMMETRY Ian Stewart
SYNAESTHESIA Julia Simner
SYNTHETIC BIOLOGY Jamie A. Davies
SYSTEMS BIOLOGY Eberhard O. Voit
TAXATION Stephen Smith
TEETH Peter S. Ungar
TELESCOPES Geoff Cottrell
TERRORISM Charles Townshend
THEATRE Marvin Carlson
THEOLOGY David F. Ford
THINKING AND REASONING Jonathan St B. T. Evans
THOMAS AQUINAS Fergus Kerr
THOUGHT Tim Bayne
TIBETAN BUDDHISM Matthew T. Kapstein
TIDES David George Bowers and Emyr Martyn Roberts
TOCQUEVILLE Harvey C. Mansfield
TOPOLOGY Richard Earl
TRAGEDY Adrian Poole
TRANSLATION Matthew Reynolds
THE TREATY OF VERSAILLES Michael S. Neiberg
TRIGONOMETRY Glen Van Brummelen
THE TROJAN WAR Eric H. Cline
TRUST Katherine Hawley
THE TUDORS John Guy
TWENTIETH–CENTURY BRITAIN Kenneth O. Morgan
TYPOGRAPHY Paul Luna
THE UNITED NATIONS Jussi M. Hanhimäki
UNIVERSITIES AND COLLEGES David Palfreyman and Paul Temple
THE U.S. CONGRESS Donald A. Ritchie
THE U.S. CONSTITUTION David J. Bodenhamer
THE U.S. SUPREME COURT Linda Greenhouse
UTILITARIANISM Katarzyna de Lazari-Radek and Peter Singer
UTOPIANISM Lyman Tower Sargent
VETERINARY SCIENCE James Yeates
THE VIKINGS Julian D. Richards
VIRUSES Dorothy H. Crawford
VOLTAIRE Nicholas Cronk
WAR AND TECHNOLOGY Alex Roland
WATER John Finney
WAVES Mike Goldsmith
WEATHER Storm Dunlop
THE WELFARE STATE David Garland
WILLIAM SHAKESPEARE Stanley Wells
WITCHCRAFT Malcolm Gaskill
WITTGENSTEIN A. C. Grayling
WORK Stephen Fineman
WORLD MUSIC Philip Bohlman
THE WORLD TRADE ORGANIZATION Amrita Narlikar
WORLD WAR II Gerhard L. Weinberg
WRITING AND SCRIPT Andrew Robinson
ZIONISM Michael Stanislawski
Available soon:
SMELL Matthew Cobb
THE SUN Philip Judge
ENZYMES Paul Engel
FIRE Andrew C. Scott
ECOLOGY Jaboury Ghazoul
For more information visit our web site
www.oup.com/vsi/
Robin Wilson
Number Theory
A Very Short Introduction
Great Clarendon Street, Oxford OX2 6DP, United Kingdom
Oxford University Press is a department of the University of Oxford. It furthers the University’s objective of excellence in research, scholarship, and education by publishing worldwide. Oxford is a registered trade mark of Oxford University Press in the UK and in certain other countries
© Robin Wilson 2020
The moral rights of the author have been asserted
First Edition published in 2020
Impression: 1
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, without the prior permission in writing of Oxford University Press, or as expressly permitted by law, by licence or under terms agreed with the appropriate reprographics rights organization. Enquiries concerning reproduction outside the scope of the above should be sent to the Rights Department, Oxford University Press, at the address above
You must not circulate this work in any other form and you must impose this same condition on any acquirer
Published in the United States of America by Oxford University Press
198 Madison Avenue, New York, NY 10016, United States of America
British Library Cataloguing in Publication Data
Data available
Library of Congress Control Number: 2020932768
ISBN 978–0–19–879809–5
ebook ISBN 978–0–19–251907–8
Printed in Great Britain by Ashford Colour Press Ltd, Gosport, Hampshire
Links to third party websites are provided by Oxford in good faith and for information only. Oxford disclaims any responsibility for the materials contained in any third party website referenced in this work.
Contents
List of illustrations
1 What is number theory?
2 Multiplying and dividing
3 Prime-time mathematics
4 Congruences, clocks, and calendars
5 More triangles and squares
6 From cards to cryptography
7 Conjectures and theorems
8 How to win a million dollars
9 Aftermath
Further reading
Index
List of illustrations
1 Euclid; Fermat; Euler; Gauss
Granger Historical Picture Archive/Alamy Stock Photo; Lebrecht Music & Arts/Alamy Stock Photo; The State Hermitage Museum, St. Petersburg. Photo © The State Hermitage Museum/photo by E.N. Nikolaeva; akg-images
2 The integers
3 The first four non-zero squares
4 Right-angled triangles
5 18 is a multiple of 3, and 3 is a factor of 18; b is a multiple of a, and a is a factor of b
6 If d divides a and b, then it also divides
7 Two gears with 90 and 54 teeth
8 A periodical cicada
David C. Marshall/Wikimedia Commons (CC BY-SA 4.0)
9 The division rule
10 Special cases of the division rule
11
12
13
14 The sum of the first few odd numbers is a square
15 If b is odd, then b2 has the form
16 Casting out nines
17 A German postage stamp commemorates Adam Riese; An example from Abraham Lincoln’s ‘Cyphering book’
Deutsche Bundespost; George A. Plimpton Papers, Rare Book & Manuscript Library, Columbia University in the City of New York
18 Factorizations of 108 and 630
19 A postage stamp celebrates the discovery in 2001 of the 39th Mersenne prime
Courtesy of Liechtensteinische Post AG
20 Some regular polygons
21 Constructing an equilateral triangle
22 Doubling the number of sides of a regular polygon
23 A 12-hour clock
24 A 7-day clock
25 Some solutions of the Diophantine equation
26 Bachet’s translation of Diophantus’s Arithmetica
Bodleian Library, University of Oxford (Saville W2, title page)
27 A postage stamp celebrates Andrew Wiles’s proof of Fermat’s last theorem
Courtesy of Czech Post
28 A necklace with five beads
29 Shuffling cards
30 The distribution of primes
31 The graph of the natural logarithm
32 The graphs of π(x) and x/log x
33 (a) Bernhard Riemann
Familienarchiv Thomas Schilling/Wikimedia Commons
(b) Riemann’s 1859 paper
Wikimedia Commons
34 Summing the powers of 1/2
35 Points on the complex plane
36 The zeros of the Riemann zeta function in the complex plane
Chapter 1
What is number theory?
Consider the following questions:
In which years does February have five Sundays?
What is special about the number 4,294,967,297?
How many right-angled triangles with whole-number sides have a side of length 29?
Are any of the numbers 11, 111, 1111, 11111, … perfect squares?
I have some eggs. When arranged in rows of 3 there are 2 left over, in rows of 5 there are 3 left over, and in rows of 7 there are 2 left over. How many eggs have I altogether?
Can one construct a regular polygon with 100 sides if measuring is forbidden?
How many shuffles are needed to restore the order of the cards in a pack with two Jokers?
If I can buy partridges for 3 cents, pigeons for 2 cents, and 2 sparrows for a cent, and if I spend 30 cents on buying 30 birds, how many birds of each kind must I buy?
How do prime numbers help to keep our credit cards secure?
What is the Riemann hypothesis, and how can I earn a million dollars?
As you’ll discover, these are all questions in number theory, the branch of mathematics that’s primarily concerned with our counting numbers, 1, 2, 3, …, and we’ll meet all of these questions again later. Of partic
ular importance to us will be the prime numbers, the ‘building blocks’ of our number system: these are numbers such as 19, 199, and 1999 whose only factors are themselves and 1, unlike 99 which is and 999 which is . Much of this book is concerned with exploring their properties.
Number theory is an old subject, dating back over two millennia to the Ancient Greeks. The Greek word ἀριθμὸς (arithmos) means ‘number’, and for the Pythagoreans of the 6th century bc ‘arithmetic’ originally referred to calculating with whole numbers, and by extension to what we now call number theory—in fact, until fairly recently the subject was sometimes referred to as ‘the higher arithmetic’. Three centuries later, Euclid of Alexandria discussed arithmetic and number theory in Books VII, VIII, and IX of his celebrated work, the Elements, and proved in particular that the list of prime numbers is never-ending. Then, possibly around ad 250, Diophantus, another inhabitant of Alexandria, wrote a classic text called Arithmetica which contained many questions with whole number solutions.
After the Greeks, there was little interest in number theory for over one thousand years until the pioneering insights of the 17th-century French lawyer and mathematician Pierre de Fermat, after whom ‘Fermat’s last theorem’, one of the most celebrated challenges of number theory, is named. Fermat’s work was developed by the 18th-century Swiss polymath Leonhard Euler, who solved several problems that Fermat had been unable to crack, and also by Joseph-Louis Lagrange in Berlin and Adrien-Marie Legendre in Paris. In 1793 the German prodigy Carl Friedrich Gauss constructed by hand a list of all the prime numbers up to three million when he was aged just 15, and shortly afterwards wrote a groundbreaking text entitled Disquisitiones Arithmeticae (Investigations into Arithmetic) whose publication in 1801 revolutionized the subject. Sometimes described as the ‘Prince of Mathematics’, Gauss asserted that
Mathematics is the queen of the sciences, and number theory is the queen of mathematics.
The names of these trailblazers will reappear throughout this book (see Figure 1).
1. From left to right; Euclid, Pierre de Fermat, Leonhard Euler, and Carl Friedrich Gauss.
More recently, the subject’s scope has broadened greatly to include many other topics, several of which feature in this book. In particular, there have been some spectacular developments, such as Andrew Wiles’s proof of Fermat’s last theorem (which had remained unproved for over 350 years) and some exciting new results on the way that prime numbers are distributed.
Number theory has long been thought of as one of the most ‘beautiful’ areas of mathematics, exhibiting great charm and elegance: prime numbers even arise in nature, as we’ll see. It’s also one of the most tantalizing of subjects, in that several of its challenges are so easy to state that anyone can understand them—and yet, despite valiant attempts by many people over hundreds of years, they’ve never been solved. But the subject has also recently become of great practical importance—in the area of cryptography. Indeed, somewhat surprisingly, much secret information, including the security of your credit cards, depends on a result from number theory that dates back to the 18th century.
