A papyrus fragment of Euclid's Elements from Oxyrhynchus with Greek text and a small drawn diagram of a rectangle and squares
Unit 01 · All masterclasses · 70 min

Proof, Induction, and the Integers

What a proof is, how induction works, and the toolkit every later unit uses
Image: University of Pennsylvania Museum of Archaeology and Anthropology, CC BY-SA 4.0

The unit opens with an homage to number theory and then builds the toolkit of the whole program: the notation for the integers, sums, floors, and binomial coefficients; what a proof and a counterexample are, shown by Euler's factor of the fifth Fermat number; direct proof, contrapositive, and contradiction, with the irrationality of the square root of 2; induction in its weak and strong forms and the well-ordering principle; the pigeonhole principle; and the digit count of the largest known prime as a first lesson in how fast numbers grow.

Preview: the beginning of the unit

1 Introduction

The integers are the oldest objects of mathematics and the only ones that everybody owns. A child who can count has met them all, in the sense that the rule for the next one never changes, and yet nobody has understood them completely. Take the primes, the numbers \(2, 3, 5, 7, 11, 13, \ldots\) that cannot be split into smaller factors. A child can ask whether the list ever ends. Euclid (active around 300 BC) proved in his book, the Elements, that it does not, in an argument a page long that is still taught today, and Unit 3 presents it. The next question is almost as easy to ask and far harder to answer. How are the primes spread among the other numbers? Between 1 and 100 there are 25 of them, between 1 and a million 78,498, and a formula that describes this thinning out was conjectured around 1800 and proved only in 1896, with tools taken from calculus with complex numbers, a part of mathematics that seems far away from the integers. Unit 8 tells that story.

Some of the oldest questions are still open. On 7 June 1742 Christian Goldbach (1690-1764) wrote to Leonhard Euler (1707-1783) and asked, in effect, whether every even number greater than 2 is the sum of two primes. Computers have confirmed this for every even number up to \(4 \times 10^{18}\), which is four billion billion, and no proof exists. The question whether there are infinitely many pairs of primes that differ by 2, such as 11 and 13 or 101 and 103, is open as well, although since 2014 it has been known that infinitely many pairs of primes differ by at most 246, a result that grew out of a breakthrough by Yitang Zhang (University of California, Santa Barbara) in 2013. Number theory is the subject in which a statement that fits in one line can resist the best minds for 280 years, and in which the attempts to settle it have produced some of the deepest mathematics there is.

The people who built the subject form a connected story. Pierre de Fermat (1607-1665), a magistrate in Toulouse, worked on numbers in his spare time and announced his results in letters and in the margins of his books, usually without proofs. Euler, a century later, proved most of Fermat’s claims and disproved one of them, which is the story of Section 3. Carl Friedrich Gauss (1777-1855) gave the subject its modern form in his book Disquisitiones Arithmeticae (Latin for “arithmetical investigations”), finished when he was 21 and printed in 1801, when he was 24, and according to his biographer he called number theory the queen of mathematics. Bernhard Riemann (1826-1866) published a single paper on the primes in 1859, about nine pages long, that contains the most famous unsolved problem of mathematics, the Riemann hypothesis, which Unit 8 introduces. Each of these people read the ones before and answered them, and the conversation continues: in 1995 Andrew Wiles (University of Oxford) proved the statement that Fermat had written in a margin around 1637, now called Fermat’s Last Theorem (that \(x^n + y^n = z^n\) has no solutions in positive integers when \(n > 2\)), and the proof needed almost everything mathematics had learned in the meantime.

The same arithmetic now protects every bank transfer and every encrypted message. The system that does this is called RSA, after the initials of its three inventors; it was published in 1977, Unit 5 describes it, and it rests on a theorem that Fermat stated in a letter of 1640, now called Fermat’s little theorem, together with the fact that nobody knows how to split a number of 600 digits (about eight lines of print) into its prime factors in a reasonable time. Numbers of that size are small by the standards of the subject. The largest prime known in 2024 has 41,024,320 digits, and Section 7 shows how that count is obtained without writing the number down.

What makes number theory different from most of mathematics is that the questions are elementary and the methods are not. Anyone can check that \(2^{32} + 1\) is divisible by 641, and anyone can see that \(1 + 3 + 5 + 7\) is a square. The subject begins when one asks why, and whether it is always so. Its central habit is to separate a pattern from a theorem, and this masterclass is built around that habit. The present unit provides what every later unit uses: the notation for the integers, the meaning of a proof and of a counterexample, the three ways in which a statement about numbers is proved, the principle of induction and its twin, the well-ordering principle, the pigeonhole principle, and a sense of how large the numbers of this subject are. None of it needs more than school algebra, and all of it is needed by Unit 2.

The full unit is part of the program

Want to see a complete unit first? Unit 3, Prime Numbers and Unique Factorization, is free to read.