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.
In this chapter I’ll lay the groundwork for our later explorations, by introducing several types of number that you’ll meet again and posing several questions. Some of these questions are easy to answer, whereas others are harder but are solved in subsequent chapters, and a few are notorious problems for which no answer has yet been found. For the moment I won’t reveal which questions fall into which category, because you may like to think about them first. Their answers (where known) are summarized at the end of this book, in Chapter 9.
Integers
This book is about the integers (or whole numbers),
2. The integers.
These include the counting numbers or positive integers (1, 2, 3, 4, 5, … ), the negative integers ( …, −4, −3, −2, −1), and the number 0 (see Figure 2).
We can also split the collection of integers into the even numbers
and the odd numbers
Every even number is twice another integer—that is, it has the form 2n, where n is an integer: for example,
Similarly, every odd number is one more than twice another integer—that is, it has the form where n is an integer: for example,
The multiples of a given integer n are those numbers that leave no remainder when divided by n: for example,
These numbers all end in 0, and conversely all numbers that end with 0 (such as 70) are multiples of 10. Similarly,
These numbers all end in 0 or 5, and conversely all numbers that end in 0 or 5 (such as 40 and 65) are multiples of 5.
The multiples of 2 are the even numbers—those numbers that end in 2, 4, 6, 8, or 0. But what can we say about the multiples of other numbers? For example:
How can we recognize whether a given number, such as 12,345,678, is a multiple of 8? or of 9? or of 11? or of 88?
I’ll answer these questions in Chapter 2, where we’ll explore multiples in greater detail.
In number theory the single word ‘number’ generally refers to a positive integer, and we shall follow this convention unless otherwise stated.
Squares and cubes
The Pythagoreans seem to have been particularly interested in perfect squares, which they depicted geometrically by square patterns of dots, as in Figure 3.
3. The first four non-zero squares.
A square (or perfect square) has the form , where n is an integer: for example, 144 is a square because or (−12)2, and 0 is a square because . All the non-zero squares are positive integers, the first ten being
These squares all end in 1, 4, 5, 6, 9, or 0, and we might ask:
Do any squares end in 2, 3, 7, or 8?
We also notice that each of these squares is
either a multiple of 4: for example, ,
or one more than a multiple of 4: for example, ,
and we might ask whether this is always true:
Must all squares be of the form 4n or , where n is an integer?
The Pythagoreans also apparently observed such results
