Why prove anything

A pattern that holds in every case anyone has checked feels like a fact, and in mathematics it can still be false.

This lesson starts with patterns that survived far longer than anyone would need to be convinced, and then failed. They are the reason mathematics settles its claims by proof rather than by evidence. The rest of the lesson says what a proof is, names the parts of the structure that proofs build (axioms, definitions, theorems, lemmas, conjectures), writes the first proofs out in full from the definitions of even and odd, and then turns to the two skills every later lesson relies on: reading a proof actively, and writing one that a reader can check. It closes on the question of how much detail a proof needs, and on what the word "obvious" can hide. It assumes school algebra, the material of Mathematical Foundations, and nothing else.

Forty primes, then a square

In 1772 Euler noticed that the expression $n^{2} + n + 41$ produces primes with remarkable persistence. At $n = 0$ it gives $41$ , then $43$ , $47$ , $53$ , $61$ , $71$ , and every value up to $n = 39$ , where it gives $1601$ , is prime. Forty consecutive successes is more than most people would ask before believing a rule.

At $n = 40$ the value is $1681$ , and $1681 = 41^{2}$ . Once it has happened it is easy to see why. Write the expression at $n = 40$ with the first two terms grouped: $40^{2} + 40 = 40 (40 + 1) = 40 \times 41$ , so the whole thing is $40 \times 41 + 41 = 41 \times 41$ .

The same thought shows that $n = 41$ fails too: every term of $41^{2} + 41 + 41$ is a multiple of $41$ , and the value is $1763 = 41 \times 43$ . The structure that breaks the pattern was visible in the formula from the start. The forty checks established forty facts and said nothing about the forty-first, because nothing in them said why the values were prime. A check tells you what happened, not what must happen.

It is worth being exact about what the forty checks did establish. Each one is a small proof: " $n^{2} + n + 41$ is prime when $n = 17$ " is settled by computing $17^{2} + 17 + 41 = 347$ and confirming that no integer from $2$ to $18$ divides it. What no check can do is reach the claim "for every $n$ ", because that claim has infinitely many instances and each check settles one. Later in this lesson a proof will settle infinitely many instances in the other direction, showing that the expression is composite for every positive multiple of $41$ .

Doubling that stops at thirty-one

Place points on a circle and join every pair with a straight chord, taking care that no three chords pass through the same interior point. Count the regions the chords cut the disc into. One point makes no chord, so there is $1$ region. Two points give one chord and $2$ regions. Three points give a triangle and $4$ regions, four points give $8$ , and five give $16$ .

The sequence $1, 2, 4, 8, 16$ is as clean a pattern as mathematics offers, and the obvious guess is that six points give $32$ . They give $31$ , and no arrangement of six points does better. (If the six points are the corners of a regular hexagon, the three long diagonals meet at the centre, which breaks the rule about three chords, and the count drops to $30$ .)

Here too the failure makes sense once the right quantity is counted. Add the chords one at a time. A new chord that crosses $k$ chords already drawn passes through $k + 1$ existing regions and splits each of them in two, so it adds $k + 1$ regions. Summing over all the chords, the total is $1$ for the starting disc, plus $1$ for each chord, plus $1$ for each crossing point. With $n$ points there are $(\binom{n}{2})$ chords (one per pair of points, so $\frac{n (n - 1)}{2}$ ), and every choice of four points produces exactly one crossing (where the diagonals of their quadrilateral meet), so there are $(\binom{n}{4})$ crossings. The number of regions is therefore

R (n) = 1 + (\binom{n}{2}) + (\binom{n}{4})

For six points that is $1 + 15 + 15 = 31$ , and for seven it is $1 + 21 + 35 = 57$ , nowhere near $64$ . Eight points give $99$ against $128$ , and the gap only widens: $R (n)$ is a polynomial in $n$ of degree $4$ , while $2^{n - 1}$ doubles at every step.

The powers of two were a coincidence of small numbers: $2^{n - 1}$ and $1 + (\binom{n}{2}) + (\binom{n}{4})$ agree up to five points and then part company. (Problem 14 shows that the agreement is not an accident of arithmetic but has a reason, and that the reason expires at five.) The argument rests on the sentence "every choice of four points produces exactly one crossing", and a careful reader should want that sentence justified. Justifying sentences like it is what this course is about.

Why does every choice of four points give exactly one crossing?

Two chords with a common endpoint meet only at that endpoint, on the circle, so every interior crossing comes from two chords with four different endpoints. The question is which pairs of such chords cross.

A chord $A B$ cuts the disc into two pieces, one on each side of the line through $A$ and $B$ , and it cuts the circle into two arcs, one in each piece. Take another chord $C D$ with $C$ and $D$ different from $A$ and $B$ . If $C$ and $D$ lie on the same arc, the whole segment $C D$ lies in one piece, because each piece is the part of the disc on one side of a line, and the part of a disc on one side of a line contains every segment between two of its points. So $C D$ does not cross $A B$ . If $C$ and $D$ lie on different arcs, they are on opposite sides of the line $A B$ , so the segment $C D$ meets that line, and it meets it inside the disc, which is where $C D$ lies. So the chords cross. In short: two chords cross exactly when their endpoints alternate around the circle.

Now label four points in the order they sit around the circle as $P_{1}, P_{2}, P_{3}, P_{4}$ . They can be split into two pairs in three ways: ${P_{1} P_{2}, P_{3} P_{4}}$ , ${P_{1} P_{4}, P_{2} P_{3}}$ and ${P_{1} P_{3}, P_{2} P_{4}}$ . In the first two the endpoints do not alternate, and in the third they do. So exactly one of the three pairs of chords crosses, at the point where the diagonals of the quadrilateral $P_{1} P_{2} P_{3} P_{4}$ meet. Different sets of four points give different crossing points, because a crossing lies on exactly two chords (no three chords pass through one interior point) and those two chords determine their four endpoints. That proves there are exactly $(\binom{n}{4})$ crossings.

The claim that a new chord crossing $k$ old ones adds $k + 1$ regions needs a similar check. The $k$ crossing points are distinct, so they cut the new chord into $k + 1$ segments. Each segment runs through the interior of a single existing region from one side of it to the other, and so divides that region into two.

One more coincidence is waiting further out. With ten points the formula gives $1 + 45 + 210 = 256 = 2^{8}$ , a power of two again, though not the one the pattern predicted ( $2^{9} = 512$ ). A pattern that has failed can still throw up numbers that look like it, which is one more reason not to trust patterns.

Nine hundred million confirmations

Perhaps people should simply check more. The third pattern answers that. Count the prime factors of a whole number with repeats, so that $12 = 2 \times 2 \times 3$ has three and $9 = 3 \times 3$ has two, and give $1$ zero. Among the numbers from $1$ to $10$ , five ( $2$ , $3$ , $5$ , $7$ and $8$ ) have an odd number of prime factors, and up to $100$ it is fifty-one.

In 1919 George Pólya conjectured that this always happens: for every $n$ greater than $1$ , at least half of the numbers from $1$ to $n$ have an odd number of prime factors. It was checked by hand and later by machine over enormous ranges, and it held for every $n$ anyone tested.

In 1958 Brian Haselgrove proved that it fails somewhere, by an argument that showed a counterexample exists without producing one. In 1980 Minoru Tanaka found the first one by computer. It is $906 150 257$ . Up to that number, $453 075 128$ have an odd number of prime factors and $453 075 129$ have an even number, so the odd ones are outnumbered by one. Every $n$ from $2$ to $906 150 256$ obeys the conjecture.

A second conjecture of the same family has a stranger history. For each whole number $k$ , let $μ (k)$ be $0$ if some prime divides $k$ twice, and otherwise $1$ or $- 1$ according as $k$ has an even or an odd number of prime factors. So $μ (1) = 1$ , $μ (2) = μ (3) = - 1$ , $μ (4) = 0$ , $μ (6) = 1$ . Add these up to $n$ and call the total $M (n)$ : the first values are $M (1) = 1$ , $M (2) = 0$ , $M (3) = - 1$ , $M (4) = - 1$ , $M (5) = - 2$ . The running total wanders up and down, and in 1897 Franz Mertens conjectured that it always stays small: $| M (n) | < \sqrt{n}$ for every $n > 1$ . The conjecture mattered, because it would have implied the Riemann hypothesis, one of the most famous open problems in mathematics. It has been checked by computer far beyond $10^{14}$ , and no value of $n$ that breaks it has ever been found.

It is false. In 1985 Andrew Odlyzko and Herman te Riele proved that $| M (n) |$ exceeds $\sqrt{n}$ for some $n$ , and to this day nobody knows a single such $n$ . The first one is believed to be so large that no search by computer will ever reach it. Here the evidence was not merely insufficient: it may never be possible to see the conjecture fail, however long anyone checks.

A claim about every natural number is a claim about infinitely many cases, and any finite collection of checks, however large, leaves infinitely many unchecked. Nine hundred million confirmations are exactly as far from infinity as forty. Evidence, which is how the empirical sciences rightly work, cannot establish a mathematical claim of this kind. It can refute one: a single failure, such as $1681$ or Tanaka's number, disposes of a claim about every case completely.

How can anyone know a counterexample exists without finding it?

By proving that the claim, if true, would lead to something false. Haselgrove, and later Odlyzko and te Riele, did not search for a bad $n$ . They showed that if the conjecture held for every $n$ , then certain quantities built from the zeros of Riemann's zeta function would have to behave in a particular way, and then computed enough of those zeros, to high precision, to see that they do not. So the conjecture cannot hold for every $n$ , and some $n$ breaks it. The argument never needs to know which.

The same thing had happened before. For every $x$ that anyone could compute, the number of primes up to $x$ is smaller than a standard estimate for it, the logarithmic integral. In 1914 J. E. Littlewood proved that the difference changes sign infinitely often, so the inequality fails for some enormous $x$ . More than a century later no such $x$ has been exhibited, though the first one is known to be below $10^{317}$ .

This kind of proof, which shows that something exists without producing it, is called non-constructive, and it is entirely legitimate. It rests on two ideas this course develops properly later: that the negation of "for every $n$ , $P (n)$ " is "for some $n$ , not $P (n)$ " (in the quantifiers lesson), and that a statement which leads to a falsehood must itself be false (proof by contradiction, in the lesson on contrapositive and contradiction). The lesson on direct proof has a short example of an existence proof that never names its witness.

For the working mathematician the moral cuts both ways. Numerical evidence can be overwhelming and still wrong; and a conjecture can be settled, completely and permanently, while its counterexamples stay out of reach.

When one case is the whole proof

The asymmetry between confirming and refuting has a practical side. To refute a claim about every case, one case is enough, and checking that one case is a complete proof that the claim is false. The check has to be exact and has to be shown, but nothing more is required.

Euler supplies the next example against himself. Fermat had claimed that no cube is a sum of two positive cubes and no fourth power a sum of two fourth powers, and in 1769 Euler conjectured a generalisation: for every $k \geq 3$ , a sum of fewer than $k$ positive $k$ th powers is never a $k$ th power. So three fourth powers never add to a fourth power, four fifth powers never add to a fifth power, and so on. The conjecture stood for almost two hundred years. In 1966 L. J. Lander and T. R. Parkin, searching by computer, found

27^{5} + 84^{5} + 110^{5} + 133^{5} = 144^{5}

and published it in a paper of two sentences. Nothing more was needed: anyone can check that both sides equal $61 917 364 224$ , and once they have, the conjecture is dead for $k = 5$ . In 1988 Noam Elkies found three fourth powers with a fourth-power sum, and Roger Frye then found the smallest such example by computer, $95 800^{4} + 217 519^{4} + 414 560^{4} = 422 481^{4}$ .

A good counterexample often does more than refute: examined closely, it can show why the claim fails. The next Example gives one of the most famous counterexamples in number theory, verified twice, once by brute force and once by an argument that shows where the factor comes from.

Example. The numbers $F_{n} = 2^{2^{n}} + 1$ are called Fermat numbers. The first five are $F_{0} = 3$ , $F_{1} = 5$ , $F_{2} = 17$ , $F_{3} = 257$ and $F_{4} = 65 537$ , all prime, and in 1640 Fermat stated his belief that every $F_{n}$ is prime. Prove that $F_{5} = 2^{32} + 1$ is not.

The claim "every $F_{n}$ is prime" is refuted by exhibiting one $F_{n}$ with a factor strictly between $1$ and itself. Euler found such a factor in 1732: $641$ . The first proof is a multiplication. We have $2^{32} = 4 294 967 296$ , so $F_{5} = 4 294 967 297$ , and long multiplication gives

641 \times 6 700 417 = 4 294 967 297

Both factors are greater than $1$ , so $F_{5}$ is composite. That is a complete proof, and it would satisfy any referee.

The second proof avoids large numbers and shows where $641$ comes from. Notice that $641 = 5 \times 2^{7} + 1$ and also $641 = 5^{4} + 2^{4}$ . The second fact gives $2^{4} = 641 - 5^{4}$ , so

2^{32} = 2^{4} \times 2^{28} = (641 - 5^{4}) \times 2^{28} = 641 \times 2^{28} - (5 \times 2^{7})^{4}

The first fact gives $5 \times 2^{7} = 641 - 1$ . Expanding $(641 - 1)^{4}$ by the binomial theorem, every term except the last contains the factor $641$ , and the last is $(- 1)^{4} = 1$ , so $(641 - 1)^{4} = 641 m + 1$ for the integer $m = 641^{3} - 4 \times 641^{2} + 6 \times 641 - 4$ . Putting these together,

F_{5} = 2^{32} + 1 = 641 \times 2^{28} - (641 m + 1) + 1 = 641 (2^{28} - m)

and since $F_{5} > 641$ , the second factor $2^{28} - m$ is an integer greater than $1$ . It is in fact $6 700 417$ , so the two proofs reach the same factorisation by different routes.

Now you. Multiply the first few primes together and add $1$ : $2 + 1 = 3$ , $2 \times 3 + 1 = 7$ , $2 \times 3 \times 5 + 1 = 31$ , $2 \times 3 \times 5 \times 7 + 1 = 211$ and $2 \times 3 \times 5 \times 7 \times 11 + 1 = 2311$ are all prime. Prove that the pattern fails at the next step.

Answer

The next number is $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30 031$ , and

59 \times 509 = 30 031

Both factors are greater than $1$ , so $30 031$ is composite, and the claim that every such number is prime is false. The multiplication is the whole proof. Finding the factor is another matter: it takes trial division by the primes up to $\sqrt{30 031} \approx 173.3$ , and the first to divide is $59$ .

Notice that $59$ and $509$ are both larger than $13$ . That is no accident: none of the primes $2$ to $13$ can divide a number that is one more than a multiple of it (Problem 11 proves this). The same observation is the heart of Euclid's proof that there are infinitely many primes, which the lesson on contrapositive and contradiction gives in full. Euclid's argument never claims that these numbers are prime, only that their prime factors are new.

What a proof is

A proof is a finite chain of statements, each of which is justified by one of a few things: a definition, an axiom (a statement taken as a starting point and not argued for), a result that has already been proved, an assumption the proof has openly made (such as the hypothesis of the claim, "suppose $a$ is odd"), or a rule of logic applied to earlier lines. The last statement in the chain is the claim. Because every link is justified, the claim cannot fail in any case the chain covers, and one chain can cover infinitely many cases.

A proof is not an argument that makes the claim plausible, and it is not a picture: the chords on a circle suggested $32$ and delivered $31$ . What a proof offers is checkability. A reader can take each line, ask what justifies it, and find the answer in a definition, an axiom, an earlier theorem or the rules of logic. If every line survives that question, the reader has no choice but to accept the conclusion, without needing to trust the writer.

Two things follow from that description. First, a proof is relative to its starting points. It shows that the claim follows from the definitions and axioms used, and if those change, the proof may fail. The claim "the angles of a triangle add up to $180$ degrees" is a theorem of Euclid's geometry and false on the surface of a sphere, where a triangle with a vertex at the North Pole and two on the equator can have three right angles. Second, a proof is judged line by line, not as a whole. An argument that is persuasive overall but has one unjustified step is not a proof, however likely its conclusion. Many false "proofs" in the history of mathematics were wrong in exactly one sentence.

This is the trade mathematics makes. Its conclusions hold only under the stated assumptions, and within them they are permanent. Euclid's proof that there are infinitely many primes, written around 300 BCE, is as correct now as it was then, which no measurement from that century can claim.

Proofs in this course are written in sentences. Symbols appear where they are clearer, but words such as "suppose", "since" and "so" carry the argument, because they say which statement follows from which. A column of bare equations often hides exactly the step that needed justifying.

Who decides whether a proof is correct?

In principle, anyone who reads it carefully: that is the point of checkability. In practice, a new proof is read by experts, most formally by the referees of the journal it is sent to, and it is accepted when the people best placed to find an error have tried and failed. The system works well but not perfectly, and its failures are instructive.

In 1879 Alfred Kempe published a proof of the four colour theorem, that every map in the plane can be coloured with four colours so that neighbouring regions differ. It was accepted for eleven years. In 1890 Percy Heawood found the flaw: one step in Kempe's argument, a case in which two recolourings are done at once, can fail. Kempe's method still proved that five colours suffice, and the four colour theorem waited until 1976. In 1993 Andrew Wiles announced a proof of Fermat's Last Theorem; a gap was found while the paper was being checked, and Wiles, working with Richard Taylor, repaired it the following year. In both cases the error was found by exactly the kind of line-by-line reading this lesson describes.

What never decides the question is the reputation of the author, the number of people who believe the result, or the amount of evidence for it. A proof by an unknown student is as good as one by a famous professor, and Euler's name did not save his conjecture on sums of powers. Since the 1990s a further check has become available: proof assistants, programs that verify every logical step of a proof written in a formal language. The lesson on direct proof describes how they settled doubts about two proofs too long for any person to check by hand.

Axioms, definitions, theorems and conjectures

Mathematics organises what it knows with a small vocabulary, and every textbook uses it. The words say what role a statement plays, which is also what a reader may do with it.

An axiom is a statement accepted without proof, as a starting point. Every chain of proofs has to start somewhere, and the axioms are where. Euclid began his geometry with five postulates, such as "a straight line can be drawn between any two points"; this course takes as axioms the ordinary rules of arithmetic for the integers and the real numbers, listed later in this lesson, and a few more facts introduced when they are needed, such as the well-ordering of the natural numbers in the lesson on direct proof.

A definition gives a new word an exact meaning in terms of words already understood. "An integer $n$ is even if $n = 2 k$ for some integer $k$ " introduces "even" and asserts nothing, so it cannot be false. It can only be useful or useless, well chosen or badly chosen. Definitions are written with "if" but always meant as "if and only if": an integer that is not twice an integer is not even.

A theorem is a statement that has been proved, usually one important enough to be remembered. Lesser results go by other names, and the choice is a matter of emphasis, not of logic.

A proposition is a proved statement of moderate interest.
A lemma is a proved statement whose main purpose is to help prove something else. Long proofs are broken into lemmas the way long programs are broken into functions. Some lemmas outgrew their purpose and kept the name, such as Euclid's lemma about primes.
A corollary is a statement that follows from a theorem just proved with little extra work.
A conjecture is a statement that someone believes and nobody has proved. Goldbach's conjecture, that every even number greater than $2$ is a sum of two primes, has been open since 1742. The twin prime conjecture says there are infinitely many pairs of primes that differ by $2$ , such as $11$ and $13$ or $101$ and $103$ .

A conjecture that is proved becomes a theorem, whatever it is still called: "Fermat's Last Theorem" was a conjecture from the 1630s until Andrew Wiles proved it in the 1990s, and the Poincaré conjecture, proved by Grigori Perelman in 2003, kept its name. A conjecture that is refuted becomes a false statement, and the object that refutes it is a counterexample, as $n = 40$ is for Euler's expression.

Most theorems have the shape "if these conditions hold, then this conclusion follows". The conditions are the hypotheses of the theorem and what follows is its conclusion. A theorem says nothing about situations where its hypotheses fail, so every application must first check that they hold. Much of reading mathematics well is keeping track of which hypotheses a result needs.

If axioms are not proved, how do we know they are true?

For most of history the answer was that axioms are self-evident truths about the world, and Euclid's geometry was the model. But one of his postulates, the parallel postulate, never looked as self-evident as the others. In one common form it says that through a point not on a given line there is exactly one line that never meets the given one. For two thousand years mathematicians tried to prove it from the other four, and failed.

Around 1830 János Bolyai and Nikolai Lobachevsky, independently (and Gauss privately, before them), showed why. They developed a geometry in which the other axioms hold and the parallel postulate fails, with infinitely many parallels through the point, and found it perfectly coherent. Its theorems differ from Euclid's: the angles of a triangle add up to less than $180$ degrees. Later in the century Eugenio Beltrami built a model of the new geometry inside ordinary Euclidean geometry, which showed that if Euclid's geometry is free of contradictions, so is this one. So the parallel postulate cannot be proved from the others; it is a genuine choice.

The modern view grew from this. Axioms are not claims about the world, but a description of a structure: a proof shows that whatever satisfies the axioms also satisfies the theorem. The structure may model something physical, and whether it does is a question for physics. David Hilbert, who rebuilt Euclid's geometry on complete axioms around 1899, is reported to have said that one must be able to say "tables, chairs and beer mugs" in place of "points, lines and planes", since a proof may use only what the axioms say.

That leaves two demands on a system of axioms. It should be free of contradictions, since from a contradiction anything can be derived (the next lesson shows why), and it should say enough to decide the questions one cares about. In 1931 Kurt Gödel showed that for arithmetic the second demand cannot be fully met: for any consistent list of axioms about the whole numbers that a computer could print out, some statements about the whole numbers can be neither proved nor refuted from it. Mathematicians choose axioms that are consistent as far as anyone can tell, and rich enough for the mathematics they want to do.

Definitions do the work

A proof starts from definitions. This is the habit that most separates proof from school mathematics: a word such as "even" stops being something you recognise and becomes an exact statement you can use.

An integer $n$ is even if there is an integer $k$ with $n = 2 k$ . An integer $n$ is odd if there is an integer $k$ with $n = 2 k + 1$ . Everything this lesson proves about parity comes from those two sentences and the ordinary rules of algebra for integers, such as the fact that sums and products of integers are integers and that multiplication distributes over addition.

The definition settles questions that recognition leaves vague. Is $0$ even? Yes, since $0 = 2 \times 0$ . Is $- 3$ odd? Yes, since $- 3 = 2 \times (- 2) + 1$ . Is $- 10$ even? Yes, since $- 10 = 2 \times (- 5)$ , and the definition never asked for $k$ to be positive. The school test "the last digit is $0$ , $2$ , $4$ , $6$ or $8$ " agrees, but it is a fact about base-ten notation and would need its own proof before it could be used.

Notice also what the definitions do not say. Nothing in them states that every integer is even or odd, or that no integer is both. Both are true, but both need proofs of their own, which rest on division with remainder, and a proof that quietly relies on them before they are proved is incomplete. The direct proof lesson proves them, from a theorem about division that itself needs an axiom about the natural numbers. Until then, this lesson's proofs about parity may assume only what their hypotheses say.

The word "some" in the definitions matters too, and it gives every definition of this shape two uses. To show a number is even you must produce the $k$ , or show that one exists: $14$ is even because $14 = 2 \times 7$ . To use the fact that a number is even you may name its $k$ and work with it: if $a$ is even, write $a = 2 k$ for an integer $k$ , and from then on $k$ is available. Producing and naming are the whole mechanism of the proofs below. The first half of a typical proof names, the second half produces.

Definitions are choices, made to make the theorems come out cleanly. A prime is defined as an integer greater than $1$ whose only positive divisors are $1$ and itself, and the "greater than $1$ " is deliberate. If $1$ counted as prime, the theorem that every integer greater than $1$ factors into primes in only one way would be false, since $6 = 2 \times 3 = 1 \times 2 \times 3$ . Rather than add "apart from factors of $1$ " to every such theorem, mathematicians exclude $1$ once, in the definition.

First proofs

The sum $3 + 5 = 8$ is even, and so is $7 + 11 = 18$ , but those are evidence. The goal is an argument that covers every pair at once.

Example. Prove that the sum of two odd integers is even.

Let $a$ and $b$ be odd integers. By the definition of odd, there is an integer $k$ with $a = 2 k + 1$ , and there is an integer $m$ with $b = 2 m + 1$ . Then $a + b = (2 k + 1) + (2 m + 1) = 2 k + 2 m + 2 = 2 (k + m + 1)$ . Since $k$ and $m$ are integers, $k + m + 1$ is an integer. So $a + b$ is twice an integer, and by the definition of even, $a + b$ is even.

Three details are worth copying. It names arbitrary odd integers, so nothing is assumed about them except that they are odd. It uses two different letters, $k$ and $m$ , because $a$ and $b$ need not be equal; one letter would have proved the claim only for a number added to itself. And its last sentence names the definition it has satisfied, so the reader sees the chain close.

The proof also has the shape the vocabulary above predicts. The claim, spelled out, is "for all integers $a$ and $b$ , if $a$ is odd and $b$ is odd, then $a + b$ is even". The first sentence of the proof takes arbitrary $a$ and $b$ and assumes the hypotheses; the last states the conclusion. Everything between is justified by a definition or by arithmetic.

Now you. Prove that the sum of an even integer and an odd integer is odd.

Answer

Let $a$ be an even integer and $b$ an odd integer. By the definitions, there is an integer $k$ with $a = 2 k$ and an integer $m$ with $b = 2 m + 1$ . Then $a + b = 2 k + 2 m + 1 = 2 (k + m) + 1$ . Since $k + m$ is an integer, $a + b$ has the form twice an integer plus one, so by the definition of odd, $a + b$ is odd.

Example. Prove that the product of two odd integers is odd.

Let $a$ and $b$ be odd integers, so that $a = 2 k + 1$ and $b = 2 m + 1$ for some integers $k$ and $m$ . Then $a b = (2 k + 1) (2 m + 1) = 4 k m + 2 k + 2 m + 1 = 2 (2 k m + k + m) + 1$ . Since $k$ and $m$ are integers, so is $2 k m + k + m$ . Therefore $a b$ is twice an integer plus one, and by the definition of odd, $a b$ is odd.

The algebra here is chosen with the goal in view. Expanding $(2 k + 1) (2 m + 1)$ gives four terms, and the target is the form $2 \times (integer) + 1$ , so the three terms with a factor of $2$ are grouped together and the $1$ is left outside. Writing the conclusion's definition down first, and then steering the algebra towards it, is how nearly every proof in the first half of this course is found.

A proved result becomes a tool. Taking $b = a$ gives a corollary at once: the square of an odd integer is odd. Applying the result twice shows that $a^{3} = (a \times a) \times a$ is odd when $a$ is, and so on for every power, though "and so on" is itself a claim about infinitely many cases, which the induction lesson will turn into a proof.

Now you. Prove that if $a$ is an even integer and $b$ is any integer, then $a b$ is even.

Answer

Let $a$ be an even integer and $b$ any integer. By the definition of even, there is an integer $k$ with $a = 2 k$ . Then $a b = 2 k b = 2 (k b)$ . Since $k$ and $b$ are integers, $k b$ is an integer, so $a b$ is twice an integer and, by the definition of even, $a b$ is even.

Nothing was assumed about $b$ , not even its parity, and none was needed. That matters here, because this lesson has not yet proved that $b$ must be even or odd.

Proving that a pattern fails

Proof can also show that a pattern fails, and why, far beyond a single counterexample. For this the definitions needed are those of prime and composite: an integer greater than $1$ is prime if its only positive divisors are $1$ and itself, and composite if it is the product of two integers each greater than $1$ . The integer $1$ is neither.

Example. Prove that $n^{2} + n + 41$ is composite whenever $n$ is a positive multiple of $41$ .

Let $n$ be a positive multiple of $41$ , so that $n = 41 m$ for some integer $m \geq 1$ . Then $n^{2} + n + 41 = 41^{2} m^{2} + 41 m + 41 = 41 (41 m^{2} + m + 1)$ . The first factor, $41$ , is greater than $1$ . Since $m \geq 1$ , the second factor is at least $41 + 1 + 1 = 43$ , so it is greater than $1$ as well. Therefore $n^{2} + n + 41$ is a product of two integers each greater than $1$ , and by definition it is composite.

No amount of checking could do this: the proof shows Euler's expression fails at $n = 41$ , $82$ , $123$ and infinitely many other values, and why. Notice the check that the second factor exceeds $1$ . Without it the proof would be incomplete, since a number such as $41 = 41 \times 1$ is a product with a factor of $41$ and is prime. The hypothesis $m \geq 1$ is used exactly there.

Now you. Prove that $n^{2} + n + 41$ is composite whenever $n = 41 m + 40$ for some integer $m \geq 0$ . (At $m = 0$ this is the failure at $n = 40$ .)

Answer

Let $n = 41 m + 40$ with $m \geq 0$ an integer. Expanding, $n^{2} = 1681 m^{2} + 3280 m + 1600$ , so $n^{2} + n + 41 = 1681 m^{2} + 3321 m + 1681 = 41 (41 m^{2} + 81 m + 41)$ . The factor $41$ is greater than $1$ , and since $m \geq 0$ the second factor is at least $41$ , so it is greater than $1$ too. So $n^{2} + n + 41$ is a product of two integers each greater than $1$ , and is composite.

The same idea disposes of every polynomial of this kind. For any integers $b$ and $c$ with $c > 1$ , the value of $n^{2} + b n + c$ at $n = c$ is $c^{2} + b c + c = c (c + b + 1)$ , which is composite as soon as $c + b + 1 > 1$ . Euler's expression was never going to produce primes for ever, and neither is any other polynomial with integer coefficients that is not constant, a fact known since the eighteenth century.

Reading a proof actively

A proof is not read like a story, from start to finish at an even pace. It is read with a pencil, and the reader's job is to be convinced line by line, which means doing a share of the work. Five habits turn passive reading into active reading.

State the claim exactly before reading the proof. Say what is assumed and what is to be shown, with every "for all" and "if" made explicit. A proof of a claim you have not pinned down cannot be checked.
Try the claim on examples. Small cases show what the claim says and often show why it is true. They also give test values for each line of the proof.
Ask of every line what justifies it. The answer should be a definition, an axiom, an earlier result, an assumption made openly, or the rules of algebra and logic. If you cannot find the justification, you have found either a gap in your understanding or a gap in the proof, and both are worth finding.
Find where each hypothesis is used. A hypothesis that is never used is suspicious: either the theorem is stronger than stated, or the proof has a mistake. Then drop the hypothesis and see what goes wrong, which shows why it is there.
Ask what the proof gives beyond the claim. Often the argument proves more than it states, or suggests a stronger result, or fails in a way that points to one.

Example. Read the following proof actively.

Claim. If $m$ and $n$ are odd integers, then $m^{2} - n^{2}$ is divisible by $4$ .

Proof. Write $m = 2 k + 1$ and $n = 2 j + 1$ with $k$ and $j$ integers. Then $m^{2} - n^{2} = (4 k^{2} + 4 k + 1) - (4 j^{2} + 4 j + 1) = 4 (k^{2} + k - j^{2} - j)$ , which is $4$ times an integer. $□$

The claim. For all integers $m$ and $n$ : if $m$ is odd and $n$ is odd, then there is an integer $t$ with $m^{2} - n^{2} = 4 t$ . "Divisible by $4$ " has been unpacked into its definition, which is what the proof must produce.

Examples. $5^{2} - 3^{2} = 16$ , $7^{2} - 1^{2} = 48$ , $3^{2} - 7^{2} = - 40$ , $5^{2} - 5^{2} = 0$ . All are divisible by $4$ , including the negative one and the zero.

Line by line. "Write $m = 2 k + 1$ and $n = 2 j + 1$ " is justified by the definition of odd and the hypotheses; the letters differ because $m$ and $n$ need not be equal. The expansion is algebra, $(2 k + 1)^{2} = 4 k^{2} + 4 k + 1$ . The final grouping is the distributive law. That $k^{2} + k - j^{2} - j$ is an integer follows because $k$ and $j$ are integers, and the proof leaves that step to the reader, which is acceptable at this level.

Hypotheses. Both are used, in the first line. Drop one: with $m = 2$ and $n = 1$ , $m^{2} - n^{2} = 3$ , not divisible by $4$ . So the claim is false without it.

Beyond the claim. Every example was divisible by $8$ , not just $4$ : $16$ , $48$ , $- 40$ , $0$ . The proof suggests why. The expression $k^{2} + k - j^{2} - j$ is $(k^{2} + k) - (j^{2} + j)$ , and $k^{2} + k = k (k + 1)$ is a product of consecutive integers, which is always even. Proving "always even" needs the fact that every integer is even or odd, so the stronger result, that $m^{2} - n^{2}$ is divisible by $8$ , must wait for the lesson on direct proof, where it follows from the fact that every odd square is one more than a multiple of $8$ .

Now you. Read this argument actively, using the five habits, and find the step it takes for granted.

Claim. The product of two consecutive integers is even.

Proof. Let $n$ be an integer. One of $n$ and $n + 1$ is even. An even integer times any integer is even, so $n (n + 1)$ is even. $□$

Answer

The claim. For every integer $n$ , the integer $n (n + 1)$ is even, that is, $n (n + 1) = 2 t$ for some integer $t$ .

Examples. $3 \times 4 = 12$ , $0 \times 1 = 0$ , $(- 5) \times (- 4) = 20$ , $10 \times 11 = 110$ . All even.

Line by line. The first line introduces an arbitrary integer, which is right for a claim about every integer. The last line uses the second Now you in the section on first proofs, that an even integer times any integer is even, together with the fact that $n (n + 1) = (n + 1) n$ if the even one is $n + 1$ . The middle line, "one of $n$ and $n + 1$ is even", has no justification. It needs two facts: that $n$ is even or odd, and that if $n$ is odd then $n + 1$ is even. The second is easy: if $n = 2 k + 1$ then $n + 1 = 2 (k + 1)$ . The first is the statement that every integer is even or odd, which the definitions do not give and this lesson has not proved.

Hypotheses. There are none beyond " $n$ is an integer", and it is used: for $n = \frac{1}{2}$ the product is $\frac{3}{4}$ , which is not an even integer.

So the argument is correct but incomplete at this point in the course, and it becomes a complete proof once the lesson on direct proof proves that every integer is even or odd. The step is the kind that feels too obvious to state. Active reading is how such steps get noticed.

Writing a proof

A proof is written for a reader, and its job is to let that reader check every step without having to reconstruct the writer's thinking. A handful of conventions, followed by almost every mathematician, do most of the work.

Introduce every letter before using it, and say what it is. "Let $n$ be an integer" or "let $a$ and $b$ be odd integers" at the start; "there is an integer $k$ with $a = 2 k$ " when a new letter arrives from a definition. A letter that appears from nowhere cannot be checked, because the reader cannot know what may be assumed about it.

Use the connecting words precisely. The words carry the logic, and each has a job.

"Let" introduces an arbitrary object: "let $x$ be a real number". The proof must then work for every $x$ of that kind.
"Suppose" or "assume" introduces a hypothesis to be used for the rest of the argument, or for one case of it.
"Since", "because" and "by" give a justification: "since $k$ and $m$ are integers", "by the definition of odd".
"So", "therefore", "hence" and "thus" announce a conclusion drawn from what came before.
"We must show" or "it suffices to show" announces the goal, which helps the reader in a long proof.

Write in sentences. Every line of a proof, even one that is mostly symbols, should read aloud as an English sentence with a verb. " $a + b = 2 (k + m + 1)$ " is a sentence whose verb is "equals". Do not start a sentence with a symbol (" $n$ is even" is better as "The integer $n$ is even"), and do not use arrows such as $\Rightarrow$ as shorthand for "so" in a written proof: $\Rightarrow$ is a connective with a precise meaning, fixed in the next lesson, and " $A \Rightarrow B$ " does not say that $A$ is true.

Make chains of equations honest. In $a + b = (2 k + 1) + (2 m + 1) = 2 k + 2 m + 2 = 2 (k + m + 1)$ each $=$ joins two expressions that are equal, so the chain proves that the first equals the last. Never write a chain in which some link is not an equation between neighbours, and never start from the equation you are trying to prove.

Justify what a reader could doubt, and nothing more. Routine algebra such as expanding brackets needs no comment. Every use of a definition, of a hypothesis and of an earlier result should be visible. The test is a classmate who knows the definitions but not the proof: any step they could reasonably question needs its reason stated.

Say when you are done. End with the conclusion in words that echo the claim, and then a marker such as $□$ , or the older "Q.E.D." (from the Latin quod erat demonstrandum, "which was to be shown").

Here is the same proof written badly and then well. The bad version:

$a = 2 k + 1$ , $b = 2 k + 1$ , $a + b = 4 k + 2 = 2 (2 k + 1)$ $\Rightarrow$ even.

It never says what $a$ and $b$ are or what is being proved. It uses one letter $k$ for both numbers, so it proves the claim only for $a = b$ . It uses $\Rightarrow$ for "so". And it never says which definition "even" refers to. The good version is the first Example in the section on first proofs: every letter introduced, every step justified, the conclusion tied to the definition. It is longer, and every extra word is doing work.

A proof is also not the record of how it was found. The search for a proof is full of false starts, guesses and working backwards from the goal, and none of that belongs in the final text. The finished proof runs forwards from what is known to what is claimed, as if the route had been obvious all along. The lesson on direct proof shows why working backwards, handed in as a proof, can "prove" false things.

Levels of rigour, and what "obvious" hides

Every proof leaves some steps to the reader. The first Example did not prove that $k + m + 1$ is an integer from any axiom; it said "since $k$ and $m$ are integers", and trusted the reader to accept that sums of integers are integers. How much may be left out is a question of level, and there are roughly three.

An informal argument explains why something is true and skips whatever the speaker considers routine. It is how mathematicians talk to each other at a blackboard, and how the regions on a circle were counted above. A written proof, the kind this course teaches and every textbook and journal uses, justifies every step that a competent reader could doubt, from definitions, axioms and earlier results, and leaves only routine algebra and routine logic unstated. A formal proof leaves nothing out: every step is an application of a stated rule to earlier lines, and a computer can check it. Formal proofs of even simple facts are long, which is why people rarely write them by hand.

The level is a choice about audience, not about truth. A written proof is expected to be convertible into a formal one by a patient reader, and the unstated steps are the ones where that conversion is routine. The danger lies in steps that feel routine and are not. The word "obvious" is where such steps hide, and there are three ways it goes wrong: the obvious fact is false, the obvious fact is true but hard, or the obvious fact is true and easy but has not yet been proved at the point where it is used.

The third kind is the commonest in a first course. "Every integer is even or odd" is true and not hard, but it does not follow from the definitions without a theorem about division, and the Now you on reading actively showed how easily it slips into a proof unannounced. Another example is the ordinary rules of algebra. This course takes as axioms the following facts about the integers (the real numbers obey the same ones). Sums and products of integers are integers, and for all integers $a$ , $b$ and $c$ :

$a + b = b + a$ and $a b = b a$ ;
$(a + b) + c = a + (b + c)$ and $(a b) c = a (b c)$ ;
$a (b + c) = a b + a c$ ;
$a + 0 = a$ and $a \times 1 = a$ ;
there is an integer $- a$ with $a + (- a) = 0$ .

Subtraction is defined by $b - a = b + (- a)$ . Everything else in school algebra, including rules that feel as basic as these, can be proved from them. That is what makes them a good choice of axioms: a short list, from which the rest follows.

Example. Prove from the axioms that $a \times 0 = 0$ for every integer $a$ .

The rule is obvious, and that is the point: the proof shows that it is not an extra assumption but a consequence of the five. The only facts about $0$ available are axiom 4, $a + 0 = a$ , and axiom 5, which involves $0$ as the result of adding $- a$ . The trick is to use $0 + 0 = 0$ .

Let $a$ be an integer. By axiom 4, $0 + 0 = 0$ , so

a \times 0 = a \times (0 + 0) = a \times 0 + a \times 0

by axiom 3. Write $x = a \times 0$ , so this says $x = x + x$ . By axiom 5 there is an integer $- x$ with $x + (- x) = 0$ . Adding $- x$ to both sides of $x = x + x$ gives $x + (- x) = (x + x) + (- x)$ . The left side is $0$ . By axiom 2 the right side is $x + (x + (- x)) = x + 0$ , which is $x$ by axiom 4. So $0 = x$ , that is, $a \times 0 = 0$ . By axiom 1, also $0 \times a = 0$ . $□$

The step "add $- x$ to both sides" is a rule of logic rather than an axiom of arithmetic: if two expressions name the same number, adding the same thing to each gives the same result.

Now you. Prove from the axioms, in this order: (i) if $a + x = 0$ then $x = - a$ , so each integer has only one negative; (ii) $(- 1) \times a = - a$ ; (iii) $(- a) (- b) = a b$ . The last is the school rule "a negative times a negative is a positive".

Answer

(i) Let $a$ and $x$ be integers with $a + x = 0$ . Then

x = x + 0 = x + (a + (- a)) = (x + a) + (- a) = (a + x) + (- a) = 0 + (- a) = - a

using, in order, axiom 4, axiom 5, axiom 2, axiom 1, the hypothesis, and axioms 1 and 4 (since $0 + (- a) = (- a) + 0 = - a$ ).

(ii) Let $a$ be an integer. Then

a + (- 1) \times a = 1 \times a + (- 1) \times a = (1 + (- 1)) \times a = 0 \times a = 0

using axiom 4 (with axiom 1 to write $a = 1 \times a$ ), axiom 3 (with axiom 1 to put the common factor on the left), axiom 5, and the Example. So $(- 1) \times a$ is an integer that gives $0$ when added to $a$ , and by (i) it equals $- a$ .

(iii) First, $(- 1) \times (- 1) = 1$ . By (ii) with $a = - 1$ , $(- 1) \times (- 1) = - (- 1)$ . And $(- 1) + 1 = 1 + (- 1) = 0$ by axioms 1 and 5, so by (i), applied to the integer $- 1$ , the negative of $- 1$ is $1$ . Now let $a$ and $b$ be integers. By (ii), $- a = (- 1) a$ and $- b = (- 1) b$ , so

(- a) (- b) = ((- 1) a) ((- 1) b) = ((- 1) (- 1)) (a b) = 1 \times (a b) = a b

where the middle step rearranges a product of four factors using axioms 1 and 2 several times.

The rule that puzzles schoolchildren is therefore forced: any number system with the five properties must have $(- a) (- b) = a b$ . That is a better answer to "why?" than any story about debts.

The second way "obvious" goes wrong is that the fact is true but hard. A closed curve drawn in the plane without crossing itself divides the plane into an inside and an outside. Nobody doubts it, and it is the Jordan curve theorem, stated by Camille Jordan in 1887; his proof was long thought inadequate, and the first proof generally accepted as complete was given by Oswald Veblen in 1905. The difficulty is that "curve" includes shapes far wilder than anything one draws.

The first way is the worst: the obvious fact is false. For most of the nineteenth century mathematicians took it for granted that a continuous function, one whose graph can be drawn without lifting the pen, must have a slope at most points. In 1872 Karl Weierstrass presented a continuous function that has a slope at no point at all. Intuition is formed by the examples one has seen, and the theorems are about all examples, including the ones nobody has drawn.

Does anyone really prove that

1 + 1 = 2

Yes, and the place where it happens shows what a fully formal proof costs. Alfred North Whitehead and Bertrand Russell set out in Principia Mathematica, published in three volumes between 1910 and 1913, to derive mathematics from logic alone. The proposition from which $1 + 1 = 2$ follows, numbered $54.43$ , appears several hundred pages into the first volume, and the authors remark that it will follow once arithmetical addition has been defined. The length is not because $1 + 1 = 2$ is deep. It is because every notion involved, "one", "two", "plus", "equals", had to be built from logic first, and every step recorded.

Most of mathematics does not work that way. The natural numbers are usually given by axioms of their own (Giuseppe Peano's, from 1889, are the standard ones), and from those, $1 + 1 = 2$ takes a few lines: $2$ is defined as the number after $1$ , and addition is defined so that adding $1$ to a number gives the number after it.

The modern descendant of Principia is the proof assistant. Systems such as Lean and Coq check formal proofs by computer, and large libraries of mathematics have been formalised in them. Their users report the same experience Whitehead and Russell had: the steps a written proof calls obvious are where most of the effort goes, and occasionally where an error is found.

This course works at the level of written proofs throughout. Its standard for "obvious" is practical: a step may go unstated only if the reader could supply its proof from the definitions and earlier results in a line or two. The rules of algebra listed in this section meet that standard, having been proved or assumed here. "Every integer is even or odd" does not, until the lesson on direct proof.

Every proof in this lesson began by working out what its claim actually asserted. "The sum of two odd integers is even" turned out to mean: for any integers $a$ and $b$ , if $a$ is odd and $b$ is odd, then $a + b$ is even. Hidden in that ordinary sentence are an "if ... then" and a "for any", and the proof's shape came from them: take arbitrary $a$ and $b$ , assume they are odd, and reach the conclusion. Refuting Pólya's conjecture needed the same precision in reverse: knowing that one $n$ with fewer than half is enough means knowing exactly what the negation of "for every $n$ " says.

So statements have to be read exactly: "and", "or", "not" and "if ... then" do not always mean in mathematics what they mean in conversation. The next lesson fixes those meanings, and the conditional, the "if ... then" that every theorem is written in, turns out to mean something that surprises almost everyone the first time.

Problems

Work each problem on paper before opening anything; for Core and Challenge problems, try the hint before the solution. Unless a problem says otherwise, do not assume that every integer is even or odd.

Warm-up

1. Using only the definitions, show that: (a) $- 7$ is odd; (b) $6 n + 4$ is even for every integer $n$ ; (c) $2 n^{2} + 2 n + 1$ is odd for every integer $n$ ; (d) $10 n - 3$ is odd for every integer $n$ .

Solution

(a) We have $- 7 = 2 \times (- 4) + 1$ , and $- 4$ is an integer, so $- 7$ is odd.

(b) Let $n$ be an integer. Then $6 n + 4 = 2 (3 n + 2)$ , and $3 n + 2$ is an integer, so $6 n + 4$ is even.

(c) Let $n$ be an integer. Then $2 n^{2} + 2 n + 1 = 2 (n^{2} + n) + 1$ , and $n^{2} + n$ is an integer, so $2 n^{2} + 2 n + 1$ is odd.

(d) Let $n$ be an integer. Then $10 n - 3 = 10 n - 4 + 1 = 2 (5 n - 2) + 1$ , and $5 n - 2$ is an integer, so $10 n - 3$ is odd. The only step that needs thought is rewriting $- 3$ as $- 4 + 1$ , so that the constant term has the form the definition asks for.

2. In the setting of this lesson, say whether each statement is an axiom, a definition, a theorem or a conjecture, and whether it is known to be true. (a) For all integers $a$ and $b$ , $a + b = b + a$ . (b) An integer $n$ is odd if $n = 2 k + 1$ for some integer $k$ . (c) The product of two odd integers is odd. (d) Every even integer greater than $2$ is a sum of two primes. (e) The number $n^{2} + n + 41$ is prime for every natural number $n$ .

Solution

(a) An axiom (axiom 1 of the list in the section on levels of rigour). It is accepted without proof.

(b) A definition. It introduces the word "odd" and asserts nothing, so it is neither true nor false.

(d) Goldbach's conjecture. Nobody knows whether it is true.

(e) A conjecture that has been refuted, so a false statement: $n = 40$ is a counterexample, since $40^{2} + 40 + 41 = 1681 = 41 \times 41$ .

3. It was once believed that $2^{p} - 1$ is prime whenever $p$ is prime. Check the claim for $p = 2$ , $3$ , $5$ and $7$ , and then show that $p = 11$ is a counterexample.

Solution

The values are $2^{2} - 1 = 3$ , $2^{3} - 1 = 7$ , $2^{5} - 1 = 31$ and $2^{7} - 1 = 127$ . The first three are clearly prime, and $127$ is prime because none of $2$ , $3$ , $5$ , $7$ , $11$ divides it (a factorisation $127 = r s$ with $1 < r \leq s$ would need $r \leq \sqrt{127} < 12$ , and every integer from $2$ to $11$ that is not prime is a multiple of a smaller prime on the list).

For $p = 11$ , which is prime, $2^{11} - 1 = 2047$ , and $23 \times 89 = 2047$ . Both factors are greater than $1$ , so $2047$ is composite and the claim is false. Primes of the form $2^{p} - 1$ are called Mersenne primes, after Marin Mersenne; Problem 12 proves the true statement in the other direction.

4. Prove that for all integers $a$ and $b$ : (a) if $a$ is even and $b$ is odd, then $a - b$ is odd; (b) if $a$ and $b$ are both odd, then $a - b$ is even.

Solution

(a) Let $a$ be even and $b$ odd, so $a = 2 k$ and $b = 2 m + 1$ for some integers $k$ and $m$ . Then $a - b = 2 k - 2 m - 1 = 2 (k - m - 1) + 1$ . Since $k - m - 1$ is an integer, $a - b$ is odd.

(b) Let $a$ and $b$ be odd, so $a = 2 k + 1$ and $b = 2 m + 1$ for some integers $k$ and $m$ . Then $a - b = 2 k - 2 m = 2 (k - m)$ , and $k - m$ is an integer, so $a - b$ is even.

In (a) the constant $- 1$ had to be rewritten as $- 2 + 1$ to reach the form $2 \times (integer) + 1$ .

Core

5. Prove that if $a$ and $b$ are odd integers, then $a^{2} + b^{2}$ is even but not a multiple of $4$ .

Hint

Write $a^{2} + b^{2} = 4 s + 2$ for an integer $s$ . To show it is not $4 t$ for any integer $t$ , look at the difference $4 t - (4 s + 2)$ and show it can never be $0$ .

Solution

Let $a$ and $b$ be odd, so $a = 2 k + 1$ and $b = 2 m + 1$ for some integers $k$ and $m$ . Then

a^{2} + b^{2} = (4 k^{2} + 4 k + 1) + (4 m^{2} + 4 m + 1) = 4 s + 2

where $s = k^{2} + k + m^{2} + m$ is an integer. Since $4 s + 2 = 2 (2 s + 1)$ and $2 s + 1$ is an integer, $a^{2} + b^{2}$ is even.

Now let $t$ be any integer. Then $4 t - (a^{2} + b^{2}) = 4 t - 4 s - 2 = 2 (2 u - 1)$ , where $u = t - s$ is an integer. If $u \geq 1$ then $2 u - 1 \geq 1$ , and if $u \leq 0$ then $2 u - 1 \leq - 1$ ; every integer is at least $1$ or at most $0$ , so $2 u - 1 \neq 0$ in either case. Hence $4 t - (a^{2} + b^{2}) \neq 0$ , that is, $a^{2} + b^{2} \neq 4 t$ . Since $t$ was arbitrary, $a^{2} + b^{2}$ is not a multiple of $4$ .

For example, $1 + 9 = 10$ , $9 + 25 = 34$ and $49 + 1 = 50$ are all even and none is a multiple of $4$ .

6. Prove or disprove each claim. (a) The sum of three odd integers is odd. (b) The product of an even integer and an odd integer is odd. (c) The number $n^{2} + n + 17$ is prime for every natural number $n$ . (d) For all integers $a$ and $b$ , if $a + b$ is even, then $a$ and $b$ are both even.

Hint

Two are false. For each false one, a single well-chosen example settles it, but you must verify that the example really fails the conclusion, which may need a line of argument (for instance, that a certain number is not odd). For (c), try the $n$ that makes every term a multiple of $17$ , or the one just below it.

Solution

(a) True. Let $a$ , $b$ and $c$ be odd, so $a = 2 k + 1$ , $b = 2 m + 1$ and $c = 2 j + 1$ for some integers $k$ , $m$ and $j$ . Then $a + b + c = 2 (k + m + j + 1) + 1$ , and $k + m + j + 1$ is an integer, so $a + b + c$ is odd.

(b) False. Take $2$ , which is even, and $1$ , which is odd ( $1 = 2 \times 0 + 1$ ). Their product is $2$ . If $2$ were odd we would have $2 = 2 k + 1$ for an integer $k$ , so $2 k = 1$ ; but $2 k \leq 0$ when $k \leq 0$ and $2 k \geq 2$ when $k \geq 1$ . So $2$ is not odd, and the claim fails. (In fact the product of an even integer and any integer is even, by the second Now you on first proofs.)

(c) False. At $n = 16$ , $16^{2} + 16 + 17 = 256 + 16 + 17 = 289 = 17 \times 17$ , which is composite. The reason is the one that broke Euler's expression: $16^{2} + 16 = 16 \times 17$ , so the value is $16 \times 17 + 17 = 17^{2}$ . The value at $n = 17$ , $17^{2} + 17 + 17 = 17 \times 19$ , is composite too.

(d) False. Take $a = b = 1$ . Then $a + b = 2 = 2 \times 1$ is even, but $a$ is not even: $1 = 2 k$ would need $2 k = 1$ , which fails for every integer $k$ by the argument in (b). The correct statement is that $a + b$ is even exactly when $a$ and $b$ have the same parity, which follows from a result in the lesson on direct proof.

7. Find the flaw in this proof. Is the claim true?

Claim. For every integer $n$ , if $n^{2}$ is even, then $n$ is even.

Proof. Let $n$ be an even integer, so $n = 2 k$ for some integer $k$ . Then $n^{2} = 4 k^{2} = 2 (2 k^{2})$ , and $2 k^{2}$ is an integer, so $n^{2}$ is even. $□$

Hint

Compare what the proof assumes in its first line with what the claim assumes.

Solution

The claim has hypothesis " $n^{2}$ is even" and conclusion " $n$ is even". The proof assumes " $n$ is even" and concludes " $n^{2}$ is even". So it proves the converse, "if $n$ is even then $n^{2}$ is even", which is a different statement. Every line of the proof is correct; it is a correct proof of the wrong claim.

A proof of an "if ... then" statement must begin by assuming the hypothesis of that statement. The error is easy to make here because both statements are true and look alike, and the next lesson shows that a conditional and its converse are, in general, logically independent: either can be true while the other is false. (For example, "if $n$ is divisible by $4$ then $n$ is even" is true, and its converse is false at $n = 2$ .)

The claim itself is true. A direct attempt stalls, because from $n^{2} = 2 j$ there is no evident way to write $n$ as twice an integer. The lesson on contrapositive and contradiction proves it by proving the equivalent statement "if $n$ is not even then $n^{2}$ is not even", and then uses it to show that $\sqrt{2}$ is irrational.

8. Find the flaw in this argument.

- 1 = (- 1)^{1} = (- 1)^{\frac{2}{2}} = ((- 1)^{2})^{\frac{1}{2}} = 1^{\frac{1}{2}} = 1

Hint

Every step uses either arithmetic or a law of exponents. For which bases is the law $x^{p q} = (x^{p})^{q}$ valid when $q$ is a fraction?

Solution

The first two equalities are true, since $\frac{2}{2} = 1$ . The last two are true, since $(- 1)^{2} = 1$ and $1^{\frac{1}{2}} = \sqrt{1} = 1$ . The false step is $(- 1)^{\frac{2}{2}} = ((- 1)^{2})^{\frac{1}{2}}$ , which applies the law $x^{p q} = (x^{p})^{q}$ with $x = - 1$ , $p = 2$ and $q = \frac{1}{2}$ .

That law is proved for real exponents only when the base $x$ is positive. For negative bases, fractional powers are not even defined in the real numbers in general ( $(- 1)^{\frac{1}{2}}$ would be a real number whose square is $- 1$ , and there is none), and the law fails: here it would equate $(- 1)^{1} = - 1$ with $(1)^{\frac{1}{2}} = 1$ . The same slip lies behind the familiar error $\sqrt{x^{2}} = x$ , which fails for every negative $x$ ; the correct statement is $\sqrt{x^{2}} = | x |$ .

The lesson is about hypotheses. A rule of algebra is a theorem, and like every theorem it has hypotheses, often left unspoken in school. Applying it outside them can "prove" anything.

9. Prove that if $n$ is an odd integer, then $n^{2} + 4 n + 7$ is a multiple of $4$ . Is it always a multiple of $8$ ?

Hint

Substitute $n = 2 k + 1$ and collect terms. For the second question, try the smallest odd positive $n$ .

Solution

Let $n$ be odd, so $n = 2 k + 1$ for some integer $k$ . Then

n^{2} + 4 n + 7 = (4 k^{2} + 4 k + 1) + (8 k + 4) + 7 = 4 k^{2} + 12 k + 12 = 4 (k^{2} + 3 k + 3)

and $k^{2} + 3 k + 3$ is an integer, so $n^{2} + 4 n + 7$ is a multiple of $4$ .

It is not always a multiple of $8$ . At $n = 1$ the value is $12$ . If $12 = 8 u$ for an integer $u$ , then $u \leq 1$ gives $8 u \leq 8 < 12$ and $u \geq 2$ gives $8 u \geq 16 > 12$ , so there is no such $u$ . One counterexample settles the question.

10. Using only the five axioms in the section on levels of rigour, the Example there and the results of its Now you, prove that for all integers $a$ , $b$ and $c$ : (a) if $a + b = a + c$ then $b = c$ ; (b) $- (- a) = a$ ; (c) $- (a + b) = (- a) + (- b)$ .

Hint

For (a), add $- a$ to both sides and regroup. For (b) and (c), use part (i) of the Now you: to show that some integer $x$ is the negative of $y$ , it is enough to show $y + x = 0$ .

Solution

Two consequences of axioms 1, 4 and 5 are used throughout: $0 + x = x + 0 = x$ , and $(- x) + x = x + (- x) = 0$ , for every integer $x$ .

(a) Let $a$ , $b$ , $c$ be integers with $a + b = a + c$ . Then

b = 0 + b = ((- a) + a) + b = (- a) + (a + b) = (- a) + (a + c) = ((- a) + a) + c = 0 + c = c

using the two consequences above, axiom 2 twice, and the hypothesis in the middle step.

(b) Let $a$ be an integer. By axiom 5 and axiom 1, $(- a) + a = 0$ . So $a$ is an integer that gives $0$ when added to $- a$ , and by part (i) of the Now you, applied to the integer $- a$ , it is the negative of $- a$ : $a = - (- a)$ .

(a + b) + ((- a) + (- b)) = (a + (- a)) + (b + (- b)) = 0 + 0 = 0

by axioms 5 and 4. So $(- a) + (- b)$ gives $0$ when added to $a + b$ , and by part (i) of the Now you it is $- (a + b)$ .

Part (a) is the cancellation law for addition. The corresponding law for multiplication, "if $a b = a c$ and $a \neq 0$ then $b = c$ ", does not follow from these five axioms; it needs a further one, and the lesson on direct proof shows what happens when its condition $a \neq 0$ is forgotten.

11. Let $d \geq 2$ be an integer and let $M$ be a multiple of $d$ . Prove that $M + 1$ is not a multiple of $d$ . Deduce that none of the primes $2, 3, 5, 7, 11, 13$ divides $30 031$ .

Hint

Write $M = d k$ . For an arbitrary integer $t$ , show that $(M + 1) - d t$ cannot be $0$ by splitting into the cases $k - t \geq 0$ and $k - t \leq - 1$ .

Solution

Since $M$ is a multiple of $d$ , $M = d k$ for some integer $k$ . Let $t$ be any integer and put $u = k - t$ , an integer. Then

(M + 1) - d t = d k - d t + 1 = d u + 1

If $u \geq 0$ , then $d u \geq 0$ because $d > 0$ , so $d u + 1 \geq 1$ . If $u \leq - 1$ , then $d u \leq - d \leq - 2$ , so $d u + 1 \leq - 1$ . Every integer satisfies $u \geq 0$ or $u \leq - 1$ , so in either case $d u + 1 \neq 0$ , that is, $M + 1 \neq d t$ . Since $t$ was arbitrary, $M + 1$ is not a multiple of $d$ .

Now let $M = 2 \times 3 \times 5 \times 7 \times 11 \times 13 = 30 030$ . For each prime $p$ in the list, $M$ is $p$ times the product of the other five, so $M$ is a multiple of $p$ , and $p \geq 2$ . By the first part, $M + 1 = 30 031$ is not a multiple of $p$ .

So every prime factor of $30 031$ is larger than $13$ , which is why the Now you in the section on counterexamples found the factors $59$ and $509$ . The same reasoning, applied to the product of any finite list of primes, shows that no finite list contains every prime.

12. Prove that if $n = a b$ for integers $a \geq 2$ and $b \geq 2$ , then $2^{n} - 1$ is composite. Illustrate with $n = 6$ .

Hint

First prove the identity $x^{b} - 1 = (x - 1) (x^{b - 1} + x^{b - 2} + \dots + x + 1)$ by expanding the right-hand side. Then put $x = 2^{a}$ .

Solution

The identity. Let $x$ be a number and $b \geq 1$ an integer. Multiplying out,

(x - 1) (x^{b - 1} + x^{b - 2} + \dots + x + 1) = (x^{b} + x^{b - 1} + \dots + x^{2} + x) - (x^{b - 1} + x^{b - 2} + \dots + x + 1)

Every power $x^{1}, \dots, x^{b - 1}$ appears once with each sign and cancels, leaving $x^{b} - 1$ .

The claim. Let $n = a b$ with $a \geq 2$ and $b \geq 2$ integers, and put $x = 2^{a}$ . Then $2^{n} = (2^{a})^{b} = x^{b}$ , so by the identity

2^{n} - 1 = (2^{a} - 1) (2^{a (b - 1)} + 2^{a (b - 2)} + \dots + 2^{a} + 1)

Both factors are integers. The first is at least $2^{2} - 1 = 3$ , since $a \geq 2$ . The second is a sum of $b \geq 2$ positive terms, including $2^{a}$ and $1$ , so it is at least $2^{a} + 1 \geq 5$ . So $2^{n} - 1$ is a product of two integers each greater than $1$ , and is composite.

For $n = 6 = 2 \times 3$ : $2^{6} - 1 = 63 = (2^{2} - 1) (2^{4} + 2^{2} + 1) = 3 \times 21$ . Taking $a = 3$ , $b = 2$ instead gives $63 = 7 \times 9$ .

So if $2^{n} - 1$ is prime, then $n$ cannot be composite, and since $2^{1} - 1 = 1$ is not prime, $n$ must be prime. (Passing from "composite $n$ gives composite $2^{n} - 1$ " to this is the contrapositive, which the next lesson shows is equivalent.) Problem 3 shows that the converse fails.

Challenge

13. Prove that if a positive integer $n$ has an odd divisor $m > 1$ , then $2^{n} + 1$ is composite. Check the result for $n = 6$ , and explain why it shows that $2^{n} + 1$ can be prime only when $n$ is a power of $2$ .

Hint

For odd $m$ , replace $x$ by $- x$ in the identity of Problem 12 to get a factorisation of $x^{m} + 1$ . Then write $n = m t$ and put $x = 2^{t}$ . To show the second factor exceeds $1$ , compare $2^{n} + 1$ with $2^{t} + 1$ .

Solution

A factorisation. Let $m \geq 1$ be odd. The identity of Problem 12 with $b = m$ , applied to the number $- x$ , gives

(- x)^{m} - 1 = (- x - 1) ((- x)^{m - 1} + (- x)^{m - 2} + \dots + (- x) + 1)

Since $m$ is odd, $(- x)^{m} = - x^{m}$ , so the left side is $- (x^{m} + 1)$ , and the first factor on the right is $- (x + 1)$ . Multiplying both sides by $- 1$ ,

x^{m} + 1 = (x + 1) S (x), S (x) = x^{m - 1} - x^{m - 2} + x^{m - 3} - \dots - x + 1

where the signs alternate, since $(- x)^{j} = x^{j}$ for even $j$ and $- x^{j}$ for odd $j$ , and $m - 1$ is even.

The claim. Let $n$ be a positive integer with an odd divisor $m > 1$ , and write $n = m t$ for a positive integer $t$ . Put $x = 2^{t}$ , so $2^{n} = x^{m}$ . Then

2^{n} + 1 = (2^{t} + 1) \times S (2^{t})

The number $S (2^{t})$ is an integer, since it is a sum and difference of powers of $2$ . The first factor satisfies $2^{t} + 1 \geq 3$ . Since $m \geq 3$ and $t \geq 1$ , $n = m t > t$ , so $2^{n} + 1 > 2^{t} + 1 > 0$ . The product of $2^{t} + 1$ and $S (2^{t})$ is $2^{n} + 1$ , which is larger than $2^{t} + 1$ ; since $2^{t} + 1$ is positive, this forces $S (2^{t}) > 1$ . So $2^{n} + 1$ is a product of two integers each greater than $1$ , and is composite.

Check. For $n = 6$ , take $m = 3$ and $t = 2$ : $2^{6} + 1 = 65$ , and $(2^{2} + 1) (2^{4} - 2^{2} + 1) = 5 \times 13 = 65$ .

Powers of $2$ . Every positive integer can be written as $2^{s} \times m$ with $s \geq 0$ and $m$ odd: divide out factors of $2$ until none remain (the prime factorisation proved in the lesson on induction makes this precise). If $2^{n} + 1$ is prime, then by what was just proved $n$ has no odd divisor greater than $1$ , so its odd part $m$ is $1$ and $n = 2^{s}$ . So a prime of the form $2^{n} + 1$ is a Fermat number $F_{s} = 2^{2^{s}} + 1$ . The Example on Fermat numbers shows the converse fails at $s = 5$ .

14. For integers $a \geq 0$ and $k \geq 0$ , let $(\binom{a}{k})$ be the number of $k$ -element subsets of a set with $a$ elements, so $(\binom{a}{k}) = 0$ when $k > a$ . The section on the circle problem found $R (n) = 1 + (\binom{n}{2}) + (\binom{n}{4})$ regions for $n$ points. Prove that

R (n) = (\binom{n - 1}{0}) + (\binom{n - 1}{1}) + (\binom{n - 1}{2}) + (\binom{n - 1}{3}) + (\binom{n - 1}{4})

for every $n \geq 1$ , and deduce that $R (n) = 2^{n - 1}$ exactly when $n \leq 5$ .

Hint

First prove Pascal's rule, $(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ for $n \geq 1$ and $k \geq 1$ , by fixing one element of an $n$ -element set and sorting the $k$ -element subsets by whether they contain it. For the second part, count all the subsets of a set with $n - 1$ elements.

Solution

Pascal's rule. Let $n \geq 1$ and $k \geq 1$ , and let $X$ be a set with $n$ elements. Fix one element $x$ of $X$ . A $k$ -element subset of $X$ either contains $x$ or does not. Those that contain $x$ correspond exactly to the $(k - 1)$ -element subsets of $X$ without $x$ (remove $x$ , or put it back), and there are $(\binom{n - 1}{k - 1})$ of them. Those that do not contain $x$ are exactly the $k$ -element subsets of $X$ without $x$ , and there are $(\binom{n - 1}{k})$ . Every $k$ -element subset is in exactly one group, so $(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ . The rule holds even when $k > n$ or $k - 1 > n - 1$ , since both sides then count subsets that do not exist.

The identity. Let $n \geq 1$ . By Pascal's rule with $k = 2$ and $k = 4$ ,

(\binom{n}{2}) = (\binom{n - 1}{1}) + (\binom{n - 1}{2}), (\binom{n}{4}) = (\binom{n - 1}{3}) + (\binom{n - 1}{4})

and $1 = (\binom{n - 1}{0})$ , since a set has exactly one subset with no elements. Adding these three equations gives the identity.

Comparison with $2^{n - 1}$ . Let $Y$ be a set with $m = n - 1$ elements. A subset of $Y$ is fixed by deciding, for each of the $m$ elements, whether it is in or out, so $Y$ has $2^{m}$ subsets in all. Sorting them by size, $2^{m}$ is the sum of $(\binom{m}{k})$ over all $k$ from $0$ to $m$ . By the identity, $R (n)$ counts only the subsets of size at most $4$ . So

2^{n - 1} - R (n) = the number of subsets of Y with at least 5 elements

If $n \leq 5$ , then $m \leq 4$ , no subset has $5$ or more elements, and $R (n) = 2^{n - 1}$ . If $n \geq 6$ , then $m \geq 5$ , and $Y$ itself, or any $5$ of its elements, gives at least one subset of size at least $5$ , so $R (n) < 2^{n - 1}$ .

For $n = 6$ the only such subset is $Y$ itself, and $R (6) = 32 - 1 = 31$ . For $n = 10$ the missing subsets number $126 + 84 + 36 + 9 + 1 = 256$ , so $R (10) = 512 - 256 = 256$ , which explains the coincidence with a power of two noted earlier: a $9$ -element set has exactly as many subsets of size at least $5$ as of size at most $4$ , since taking complements swaps the two kinds.

So the pattern $1, 2, 4, 8, 16$ was not a coincidence of arithmetic after all. It was the count of all subsets of a set too small to have any subset of size $5$ , and it stopped the moment such subsets appeared.