Contrapositive and contradiction

Some true statements give a direct proof nothing to work with, because the hypothesis says nothing usable about the thing the conclusion is about.

The previous lesson proved conditionals by assuming the hypothesis and walking forward from definitions, and it ended on a claim that walk cannot finish: for every integer $n$ , if $n^{2}$ is even then $n$ is even. It also used, without proof, the fact that $\sqrt{2}$ is irrational. This lesson pays both debts with two indirect methods, proof by contrapositive and proof by contradiction. With them it proves that $\sqrt{p}$ is irrational for every prime $p$ , and so is $\log_{2} 3$ ; it proves Euclid's lemma, the fact about primes on which the uniqueness of prime factorisation rests; it proves Euclid's theorem that there are infinitely many primes, and that infinitely many of them have the form $4 k + 3$ . It then states and proves the pigeonhole principle, a counting fact whose proof is a one-line contradiction and whose uses run through all of combinatorics. It ends with how to choose a method and how to recognise a proof by contradiction that is really something else.

Throughout, the definitions are those of the previous lessons: $n$ is even when $n = 2 k$ for some integer $k$ , odd when $n = 2 k + 1$ , and $a ∣ b$ when $b = a k$ for some integer $k$ . The lesson also uses what the lesson on direct proof proved from the division algorithm: every integer is even or odd and none is both, and for $b > 0$ every integer has exactly one of the forms $b k, b k + 1, \dots, b k + (b - 1)$ .

Turning the conditional round

The contrapositive of $P \Rightarrow Q$ is $\neg Q \Rightarrow \neg P$ . The two are logically equivalent: each is false in exactly one row of its truth table, the row with $P$ true and $Q$ false, since $\neg Q \Rightarrow \neg P$ fails exactly when $\neg Q$ is true and $\neg P$ is false. So a proof of the contrapositive is a proof of the original, not an approximation to one. A proof by contrapositive is a direct proof aimed at that equivalent statement: assume $\neg Q$ , and reach $\neg P$ .

With a universal quantifier in front nothing changes. "For every $x$ , if $P (x)$ then $Q (x)$ " is equivalent to "for every $x$ , if not $Q (x)$ then not $P (x)$ ", because the two conditionals are equivalent for each $x$ separately. A proof lets $x$ be arbitrary, assumes $\neg Q (x)$ , and derives $\neg P (x)$ .

The contrapositive must not be confused with the converse, $Q \Rightarrow P$ , which is a different statement and may be false when the original is true. "If $n$ is divisible by $4$ then $n$ is even" is true, its converse "if $n$ is even then $n$ is divisible by $4$ " is false at $n = 2$ , and its contrapositive "if $n$ is odd then $n$ is not divisible by $4$ " is true, as it must be.

What makes the swap worth doing is that negation can turn a useless hypothesis into a useful one. " $n^{2}$ is even" gives $n^{2} = 2 k$ , and there is no way back through the square to $n$ . Its partner in the contrapositive is " $n$ is not even", which, because every integer is even or odd and none is both, means " $n$ is odd", and that gives $n = 2 k + 1$ , a formula for $n$ itself. Squaring a formula is easy. Unsquaring a fact is not.

Example. Prove that for every integer $n$ , if $n^{2}$ is even then $n$ is even.

We prove the contrapositive: for every integer $n$ , if $n$ is not even then $n^{2}$ is not even. Let $n$ be an integer that is not even. Since every integer is even or odd, $n$ is odd, so $n = 2 k + 1$ for some integer $k$ . Then $n^{2} = 4 k^{2} + 4 k + 1 = 2 (2 k^{2} + 2 k) + 1$ . Since $2 k^{2} + 2 k$ is an integer, $n^{2}$ is odd, and since no integer is both odd and even, $n^{2}$ is not even. This proves the contrapositive, and therefore the original statement.

The first sentence is not decoration. Without it, the proof looks like a proof of the converse, and a careful reader will wonder whether the writer has confused the two. Both facts about parity from the previous lesson were used, one at each end: "even or odd" turned "not even" into "odd" at the start, and "not both" turned "odd" into "not even" at the finish.

Combined with the direct proof that the square of an even number is even, the Example gives a biconditional: $n$ is even if and only if $n^{2}$ is even. The two directions were proved by different methods, which is common.

Now you. Prove that for every integer $n$ , if $n^{2} - 6 n + 5$ is even then $n$ is odd.

Answer

We prove the contrapositive: if $n$ is not odd then $n^{2} - 6 n + 5$ is not even. Let $n$ be an integer that is not odd. Then $n$ is even, so $n = 2 k$ for some integer $k$ . Then

n^{2} - 6 n + 5 = 4 k^{2} - 12 k + 5 = 2 (2 k^{2} - 6 k + 2) + 1

and $2 k^{2} - 6 k + 2$ is an integer, so $n^{2} - 6 n + 5$ is odd, and hence not even. This proves the contrapositive, and so the claim.

A direct attempt starts from $n^{2} - 6 n + 5 = 2 m$ and has to extract the parity of $n$ from a quadratic; the contrapositive starts from a formula for $n$ and only has to expand. (Another route: $n^{2} - 6 n + 5 = (n - 1) (n - 5)$ , and a product of two integers is odd exactly when both are odd, but proving that last fact is itself a contrapositive argument.)

Assuming the opposite

A proof by contradiction proves a statement $Q$ by assuming $\neg Q$ and deriving something impossible: a statement together with its negation, $R \land \neg R$ . The justification is one row of a truth table. The conditional $\neg Q \Rightarrow (R \land \neg R)$ has a conclusion that is false in every row, so if the conditional has been proved, its hypothesis must be false too. And $\neg Q$ false means $Q$ true.

The contradiction can be with anything known to be true: with the assumption itself, with another hypothesis, with a definition, or with a theorem proved earlier. " $1 = 0$ ", " $p ∣ 1$ although $p > 1$ ", " $n$ is both even and odd" and " $b$ is a smaller positive element than the least one" are all typical endings.

For a conditional $P \Rightarrow Q$ , the thing to assume is its negation, which is $P \land \neg Q$ . So the proof starts with two assumptions rather than one: everything the direct proof had, plus the negated conclusion as a further fact to use. For a universal statement $\forall x Q (x)$ , the negation is $\exists x \neg Q (x)$ : assume that one counterexample exists, name it, and derive an impossibility. The assumption must be the exact negation, computed by the rules of the lesson on quantifiers. Assuming too much ("every $x$ fails", when the negation only says "some $x$ fails") proves nothing, a mistake examined in the section on disguises below.

A proof by contradiction announces itself in its first line, "Suppose, for contradiction, that ...", names the impossibility when it arrives, and ends by saying what has been proved. The reader should never have to guess which statements are established facts and which are the doomed assumption.

The method is old. Aristotle, in the Prior Analytics of the fourth century BCE, gives as his standard example of reasoning "to the impossible" the proof that the diagonal of a square cannot be measured by its side, since otherwise odd numbers would equal even ones: the next section's proof, in geometric dress.

The contrapositive is a special case. If the argument uses $\neg Q$ to reach $\neg P$ , that contradicts the assumed $P$ . The difference is the destination. A contrapositive proof has a fixed target, $\neg P$ , while a proof by contradiction may end at any impossibility at all.

Here is the shape at its simplest. Claim: there is no smallest positive rational number. Suppose, for contradiction, that $q$ is a smallest positive rational. Then $\frac{q}{2}$ is rational, since $q = \frac{a}{b}$ gives $\frac{q}{2} = \frac{a}{2 b}$ , and it is positive, and $\frac{q}{2} < q$ because $q > 0$ . So $\frac{q}{2}$ is a positive rational smaller than the smallest one, which is impossible. Hence there is no smallest positive rational. The claim is a negative ("there is no ..."), with no hypothesis to start from, and assuming the positive version handed the proof an object, $q$ , to work on. That is the typical reason for choosing contradiction.

Example. Prove that the sum of a rational number and an irrational number is irrational.

Recall that a real number is rational if it equals $\frac{a}{b}$ for some integers $a$ and $b$ with $b \neq 0$ , and irrational otherwise. Let $r$ be rational and $x$ irrational, and suppose, for contradiction, that $r + x$ is rational. Write $r = \frac{a}{b}$ and $r + x = \frac{c}{d}$ with $a$ , $b$ , $c$ , $d$ integers and $b$ , $d$ non-zero. Then

x = (r + x) - r = \frac{c}{d} - \frac{a}{b} = \frac{b c - a d}{b d}

and $b c - a d$ and $b d$ are integers with $b d \neq 0$ . So $x$ is rational, contradicting the hypothesis that $x$ is irrational. Hence $r + x$ is irrational.

"Irrational" is a negative, "not equal to any fraction", and it gives a direct proof nothing to hold. Assuming the sum rational turns it into an equation with integers in it, and equations can be rearranged.

Now you. Prove that the product of a non-zero rational number and an irrational number is irrational. Where does the proof use that the rational number is non-zero?

Answer

Let $r$ be a non-zero rational and $x$ irrational, and suppose, for contradiction, that $r x$ is rational. Write $r = \frac{a}{b}$ and $r x = \frac{c}{d}$ with $a$ , $b$ , $c$ , $d$ integers and $b$ , $d$ non-zero. Since $r \neq 0$ , also $a \neq 0$ , so we may divide by $r$ :

x = \frac{r x}{r} = \frac{c}{d} \cdot \frac{b}{a} = \frac{b c}{a d}

with $b c$ and $a d$ integers and $a d \neq 0$ (a product of non-zero integers). So $x$ is rational, a contradiction. Hence $r x$ is irrational.

The hypothesis $r \neq 0$ was used to divide by $r$ , and it cannot be dropped: $0 \times x = 0$ is rational for every $x$ .

Is proof by contradiction as safe as a direct proof?

In classical mathematics, which is the mathematics of this course and of almost all working mathematicians, yes. Its justification is the truth table, and truth tables rest on the principle that every statement is true or false. But there are two kinds of proof by contradiction, and only one of them depends on that principle.

The first kind proves a negative statement, $\neg P$ , by assuming $P$ and deriving an impossibility. That is simply what "not $P$ " means: $P$ leads to absurdity. The irrationality of $\sqrt{2}$ is of this kind, since "irrational" means "not rational", and the proof assumes $\sqrt{2}$ rational and derives an absurdity. So is the claim that there is no smallest positive rational.

The second kind proves a positive statement, $P$ , by assuming $\neg P$ and deriving an impossibility. That shows $\neg \neg P$ , "it is not the case that $P$ fails", and passing from $\neg \neg P$ to $P$ is the law of double negation, equivalent to the law of excluded middle. Constructive mathematicians, following L. E. J. Brouwer, accept the first kind and reject the second in general, because a proof that "there is no way for an object to fail to exist" does not show how to find the object. For them "there exists" means "we can construct".

The theorem below that there are infinitely many primes is of the first kind too, since "infinite" means "not finite", and constructivists accept it. Even so, the way it is usually written hides information. Recast as a direct argument, it shows how to produce a new prime from any finite list of primes, which is more than the bare claim. That is the practical lesson for classical mathematicians as well: a proof by contradiction is valid, but when a direct version exists it often carries a construction that the contradiction concealed.

The square root of two

"Irrational" is a negative: no pair of integers, out of infinitely many, has a certain property. Contradiction assumes one pair exists and extracts an impossibility from it, a single argument about a single, arbitrary pair.

Approximations show why checking cannot settle it. The fraction $\frac{99}{70}$ gives $99^{2} = 9801$ against $2 \times 70^{2} = 9800$ , and $\frac{577}{408}$ gives $577^{2} = 332 929$ against $2 \times 408^{2} = 332 928$ . The gap is one each time, and no amount of searching can show that it never closes.

The proof needs a fraction for $\sqrt{2}$ that cannot be simplified, and the cleanest way to get one is the well-ordering principle from the previous lesson: every non-empty set of natural numbers has a least element.

Example. Prove that $\sqrt{2}$ is irrational.

Suppose, for contradiction, that $\sqrt{2}$ is rational, so $\sqrt{2} = \frac{a}{b}$ for some integers $a$ and $b$ with $b \neq 0$ . Replacing $a$ and $b$ by $- a$ and $- b$ if necessary, we may take $b > 0$ . So the set of natural numbers $b$ for which $\sqrt{2} = \frac{a}{b}$ with some integer $a$ is not empty, and by the well-ordering principle it has a least element. Let $b$ be that least element and $a$ the matching integer.

Squaring $\sqrt{2} = \frac{a}{b}$ and multiplying by $b^{2}$ gives $a^{2} = 2 b^{2}$ , so $a^{2}$ is even. By the Example of the previous section, $a$ is even, so $a = 2 c$ for some integer $c$ . Substituting, $4 c^{2} = 2 b^{2}$ , so $b^{2} = 2 c^{2}$ , and $b^{2}$ is even. By the same result, $b$ is even, say $b = 2 d$ with $d$ an integer, and $d$ is a natural number because $b$ is. Then $\sqrt{2} = \frac{a}{b} = \frac{2 c}{2 d} = \frac{c}{d}$ with $0 < d < b$ , which contradicts the choice of $b$ as the least possible denominator. Hence $\sqrt{2}$ is not rational.

The contradiction is with the minimality of $b$ , and the minimality is where "lowest terms" comes from. Textbooks often say "write $\sqrt{2} = \frac{a}{b}$ in lowest terms", which assumes that every fraction can be reduced to lowest terms; the well-ordering principle is the reason it can.

A proof that proves too much is wrong, so why does the argument not show $\sqrt{4}$ irrational? Run it with $4$ : from $a^{2} = 4 b^{2}$ the next step would need "if $4 ∣ a^{2}$ then $4 ∣ a$ ", and that is false, since $4 ∣ 36$ while $4$ does not divide $6$ . The proof for $2$ works because of a special property of $2$ , and it breaks exactly where it should. The next section identifies the property: $2$ is prime.

Now you. Prove that $\sqrt{3}$ is irrational. You may use the result of the previous lesson that if $3$ does not divide $n$ , then $n = 3 k + 1$ or $n = 3 k + 2$ for some integer $k$ , and in both cases $n^{2}$ has the form $3 m + 1$ .

Answer

First, if $3 ∣ n^{2}$ then $3 ∣ n$ . We prove the contrapositive: if $3$ does not divide $n$ , then $n^{2} = 3 m + 1$ for some integer $m$ , and by the uniqueness of the remainder, $n^{2}$ leaves remainder $1$ and not $0$ on division by $3$ , so $3$ does not divide $n^{2}$ .

Now suppose, for contradiction, that $\sqrt{3} = \frac{a}{b}$ with $a$ an integer and $b$ a natural number, and choose $b$ as small as possible by the well-ordering principle. Squaring gives $a^{2} = 3 b^{2}$ , so $3 ∣ a^{2}$ , and therefore $3 ∣ a$ . Write $a = 3 c$ . Then $9 c^{2} = 3 b^{2}$ , so $b^{2} = 3 c^{2}$ and $3 ∣ b^{2}$ , hence $3 ∣ b$ ; write $b = 3 d$ with $d$ a natural number. Then $\sqrt{3} = \frac{c}{d}$ with $d < b$ , contradicting the choice of $b$ . Hence $\sqrt{3}$ is irrational.

The proof is the proof for $\sqrt{2}$ with $3$ in place of $2$ , and the one new ingredient was "if $3 ∣ n^{2}$ then $3 ∣ n$ ", proved, like its analogue for $2$ , by contrapositive.

The same method proves a claim of a different look, which the previous lesson used and promised to prove.

Theorem. $\log_{2} 3$ is irrational.

Proof. Since $3 > 1 = 2^{0}$ and $2^{x}$ increases with $x$ , $\log_{2} 3 > 0$ . Suppose, for contradiction, that $\log_{2} 3 = \frac{p}{q}$ with $p$ and $q$ integers, which we may take to be positive. Then $2^{\frac{p}{q}} = 3$ , and raising both sides to the power $q$ gives $2^{p} = 3^{q}$ . Since $p \geq 1$ , the left side is $2 \times 2^{p - 1}$ , which is even. The right side is a product of $q$ odd numbers, and a product of odd numbers is odd, since $(2 s + 1) (2 t + 1) = 2 (2 s t + s + t) + 1$ . So $2^{p} = 3^{q}$ is both even and odd, which no integer is. Hence $\log_{2} 3$ is irrational. $□$

It follows that $\log_{2} 9 = 2 \log_{2} 3$ is irrational too, by the Now you of the previous section with the rational number $2$ , which completes the constructive example of the previous lesson: ${\sqrt{2}}^{\log_{2} 9} = 3$ is an irrational number raised to an irrational power with a rational result, and both numbers are named. The argument also shows why $\log_{2} 3$ matters outside mathematics. In music, a perfect fifth has frequency ratio $3 : 2$ and an octave $2 : 1$ , and a stack of fifths never lands exactly on a stack of octaves, because $(\frac{3}{2})^{q} = 2^{m}$ would give $3^{q} = 2^{m + q}$ . The nearest miss, twelve fifths against seven octaves, is off by the ratio $\frac{3^{12}}{2^{19}} = \frac{531 441}{524 288}$ , a little over $1.0136$ , and every tuning system has to hide this gap somewhere.

Euclid's lemma

An integer $p > 1$ is prime if its only positive divisors are $1$ and $p$ . An integer $n > 1$ that is not prime is composite: it has a positive divisor other than $1$ and $n$ , and so can be written $n = r s$ with $1 < r < n$ and $1 < s < n$ . The number $1$ is neither.

What made $2$ and $3$ work in the last section was the step "if $p ∣ a^{2}$ then $p ∣ a$ ". For prime $p$ it always holds, and the reason is the most important single fact about primes.

Theorem (Euclid's lemma). Let $p$ be a prime and $a$ , $b$ integers. If $p ∣ a b$ , then $p ∣ a$ or $p ∣ b$ .

It appears as Proposition 30 of Book VII of Euclid's Elements. It is not obvious, and it fails for composite numbers: $6 ∣ 4 \times 9$ , although $6$ divides neither $4$ nor $9$ . The proof goes through a lemma about integer combinations, proved by the well-ordering principle and two small contradictions.

Lemma. Let $p$ be a prime and $a$ an integer that $p$ does not divide. Then there are integers $x$ and $y$ with $p x + a y = 1$ .

Proof. Let $S$ be the set of positive integers of the form $p x + a y$ with $x$ and $y$ integers. It is not empty, since $p = p \times 1 + a \times 0$ is in it, so by the well-ordering principle it has a least element $d = p x_{0} + a y_{0}$ .

First, $d ∣ p$ . By the division algorithm, $p = d q + r$ with $0 \leq r < d$ . Then

r = p - d q = p - (p x_{0} + a y_{0}) q = p (1 - x_{0} q) + a (- y_{0} q)

is of the form $p x + a y$ . If $r$ were positive it would be an element of $S$ smaller than $d$ , contradicting the choice of $d$ . So $r = 0$ , and $d ∣ p$ .

Second, $d ∣ a$ , by the same argument: $a = d q' + r'$ with $0 \leq r' < d$ , and $r' = a - d q' = p (- x_{0} q') + a (1 - y_{0} q')$ is of the form $p x + a y$ , so $r' = 0$ by the minimality of $d$ .

Since $d$ is a positive divisor of the prime $p$ , either $d = 1$ or $d = p$ . If $d = p$ , then $p = d ∣ a$ , contrary to the hypothesis. So $d = 1$ , and $1 = p x_{0} + a y_{0}$ . $□$

Proof of Euclid's lemma. Suppose $p ∣ a b$ . If $p ∣ a$ there is nothing more to prove, so suppose $p$ does not divide $a$ ; we show $p ∣ b$ . By the lemma, $p x + a y = 1$ for some integers $x$ and $y$ . Multiplying by $b$ gives

b = p (b x) + (a b) y

Now $p$ divides $p (b x)$ , and $p$ divides $a b$ and hence $(a b) y$ . A common divisor of two integers divides their sum, so $p ∣ b$ . $□$

The first line of the proof is a technique worth naming. To prove " $A$ or $B$ ", assume that $A$ fails and prove $B$ . It is valid because $\neg A \Rightarrow B$ is equivalent to $A \lor B$ (the previous lessons' rule that $P \Rightarrow Q$ is equivalent to $\neg P \lor Q$ ), and it converts an "or", which gives a proof little to hold, into a hypothesis, $\neg A$ , that the proof can use.

Applied with $b = a$ , Euclid's lemma gives what the irrationality proofs need: if $p ∣ a^{2}$ , then $p ∣ a$ . Applied repeatedly, it shows that a prime dividing a product of several integers divides at least one of them. And with that, the proof for $\sqrt{2}$ goes through for every prime.

Theorem. For every prime $p$ , $\sqrt{p}$ is irrational.

Proof. Let $p$ be prime, and suppose, for contradiction, that $\sqrt{p} = \frac{a}{b}$ with $a$ an integer and $b$ a natural number, where $b$ is the least natural number for which such an $a$ exists. Then $a^{2} = p b^{2}$ , so $p ∣ a^{2}$ , and by Euclid's lemma $p ∣ a$ . Write $a = p c$ . Then $p^{2} c^{2} = p b^{2}$ , so $b^{2} = p c^{2}$ , and $p ∣ b^{2}$ , so $p ∣ b$ by Euclid's lemma again. Write $b = p d$ , where $d$ is a natural number and $d < b$ because $p > 1$ . Then $\sqrt{p} = \frac{p c}{p d} = \frac{c}{d}$ , contradicting the minimality of $b$ . $□$

Euclid's lemma is also what makes prime factorisation unique: if a number had two different factorisations into primes, a prime from one would divide the product of the other, hence divide one of its factors, hence equal it, and cancelling it would give a smaller counterexample. That argument, and the fundamental theorem of arithmetic it proves, are in the Discrete Mathematics lesson on primes. With unique factorisation the irrationality results extend at once: $\sqrt{n}$ is irrational for every natural number $n$ that is not a perfect square, since in $a^{2} = n b^{2}$ every prime appears to an even power on the left, and some prime appears to an odd power on the right.

The primes never run out

The primes thin out, from a quarter of the numbers up to $100$ to about one in thirteen of those up to a million, so whether they stop is a real question. Around 300 BCE Euclid answered it in Book IX of the Elements, Proposition 20. The proof needs one preliminary fact, itself proved by contradiction.

Lemma. Every integer $N > 1$ has a prime divisor.

Proof. The set of divisors of $N$ that are greater than $1$ is a non-empty set of natural numbers, since it contains $N$ , so by the well-ordering principle it has a least element $d$ . Suppose, for contradiction, that $d$ is not prime. Then $d = r s$ for some integers with $1 < r < d$ . Now $r ∣ d$ and $d ∣ N$ , so $r ∣ N$ by the transitivity of divisibility. That makes $r$ a divisor of $N$ greater than $1$ and smaller than $d$ , contradicting the choice of $d$ . So $d$ is prime. $□$

The least divisor greater than $1$ is always prime: for $N = 91$ it is $7$ , and for $N = 30 031$ it is $59$ . The argument is another instance of a pattern that the next lesson turns into a method: take the smallest thing that goes wrong, and show that a smaller one would too.

Example. Prove that there are infinitely many primes.

Suppose, for contradiction, that there are only finitely many, and list all of them as $p_{1}, p_{2}, \dots, p_{k}$ . Let $N = p_{1} p_{2} \dots p_{k} + 1$ . Then $N > 1$ , so by the lemma $N$ has a prime divisor $p$ . Since the list contains every prime, $p$ is one of $p_{1}, \dots, p_{k}$ , and so $p$ divides the product $p_{1} p_{2} \dots p_{k}$ . It also divides $N$ . A number dividing two integers divides their difference, so $p ∣ N - p_{1} p_{2} \dots p_{k}$ , that is, $p ∣ 1$ . But $p > 1$ , and no integer greater than $1$ divides $1$ , since a divisor of a non-zero integer is at most its size. This contradiction shows the primes are not finite in number.

The ingredients were all proved earlier: the lemma above, the fact that a common divisor divides a difference, and the size bound for divisors from the previous lesson.

Now you. Prove directly that for every positive integer $n$ there is a prime greater than $n$ . (Consider a prime divisor of $n! + 1$ .)

Answer

Let $n$ be a positive integer. Since $n! + 1 > 1$ , it has a prime divisor $p$ by the lemma. If $p \leq n$ , then $p$ is one of the factors $1, 2, \dots, n$ of $n!$ , so $p ∣ n!$ ; as also $p ∣ n! + 1$ , it would follow that $p ∣ 1$ , which is impossible for $p > 1$ . So $p > n$ .

For $n = 6$ , $6! + 1 = 721 = 7 \times 103$ , and both prime factors exceed $6$ . The proof uses a small contradiction to locate $p$ , but it never assumes the primes are finite in number: from any $n$ it produces a prime beyond it, and it is a proof of $\forall n \exists p (p > n \land p prime)$ , the quantifier form of "infinitely many".

A common retelling of Euclid's proof runs: multiply the primes together, add one, and the result is a new prime. The proof says something weaker, that $N$ has a prime divisor not on the list, and the retelling is false. The first cases make it look right: $2 + 1 = 3$ , $2 \times 3 + 1 = 7$ , then $31$ , $211$ and $2311$ , all prime. The sixth breaks it:

2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30 031 = 59 \times 509

Neither $59$ nor $509$ is among the primes from $2$ to $13$ , exactly as the proof promises. The new prime is a divisor of $N$ , not $N$ itself.

Nor did Euclid assume the primes were finite. His proposition reads "prime numbers are more than any assigned multitude of prime numbers": given any finite collection of primes, their product plus one has a prime divisor, and the divisibility argument shows that divisor is not in the collection. That proves more than the textbook version, since it turns any finite list into a new prime, and it needs no contradiction about all the primes at once.

Are there other proofs that the primes never run out?

Many, and several open whole subjects. Here is one that uses only divisibility. The Fermat numbers are $F_{n} = 2^{2^{n}} + 1$ , so $F_{0} = 3$ , $F_{1} = 5$ , $F_{2} = 17$ , $F_{3} = 257$ . Their product satisfies

F_{0} F_{1} \dots F_{n - 1} = F_{n} - 2

because $(2^{2^{0}} - 1) F_{0} F_{1} \dots F_{n - 1}$ collapses from the left by $(x - 1) (x + 1) = x^{2} - 1$ : $(2 - 1) (2 + 1) = 2^{2} - 1$ , then $(2^{2} - 1) (2^{2} + 1) = 2^{4} - 1$ , and so on up to $2^{2^{n}} - 1 = F_{n} - 2$ , while the first factor $2^{2^{0}} - 1$ is $1$ .

Now take $m < n$ and let $d$ be a positive common divisor of $F_{m}$ and $F_{n}$ . Then $d$ divides the product $F_{0} \dots F_{n - 1}$ , which contains $F_{m}$ , and $d$ divides $F_{n}$ , so $d$ divides their difference, $2$ . Every Fermat number is odd, so $d = 1$ . Two different Fermat numbers therefore share no prime divisor. Each has a prime divisor, so choosing one for each Fermat number gives infinitely many different primes. This argument is usually credited to Christian Goldbach, in correspondence with Euler. It is direct and constructive, and it shows more than Euclid's: there are at least $n$ primes up to $F_{n - 1}$ .

Euler found a proof of a different kind, which showed more still: the sum of the reciprocals of the primes, $\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \dots$ , grows without bound. A finite set of primes would make that sum finite. His method, which connects primes to the infinite product $\prod_{p} (1 - \frac{1}{p^{s}})^{- 1}$ , was developed by Dirichlet and Riemann into analytic number theory, and it culminated in the prime number theorem of 1896, proved independently by Jacques Hadamard and Charles de la Vallée Poussin: the number of primes up to $x$ is approximately $\frac{x}{\ln x}$ . In 1955 Hillel Furstenberg published a proof that uses the language of topology, a curiosity rather than a tool, but a reminder that a theorem this basic can be reached from almost anywhere.

Primes of the form 4k + 3

Every odd prime leaves remainder $1$ or $3$ on division by $4$ , and both kinds occur: $5$ , $13$ , $17$ , $29$ have the form $4 k + 1$ , and $3$ , $7$ , $11$ , $19$ have the form $4 k + 3$ . Euclid's idea, adapted, shows that the second kind never runs out. The adaptation needs one fact about remainders and one lemma.

The fact: a product of integers of the form $4 k + 1$ has the form $4 k + 1$ , since $(4 s + 1) (4 t + 1) = 4 (4 s t + s + t) + 1$ , and a product of several such numbers can be multiplied two at a time.

Lemma. Every positive integer of the form $4 k + 3$ has a prime divisor of the form $4 k + 3$ .

Proof. Suppose, for contradiction, that some positive integer of the form $4 k + 3$ has no prime divisor of that form. By the well-ordering principle there is a least such integer; call it $m$ . Then $m$ is not prime, since otherwise it would be its own prime divisor of the form $4 k + 3$ . And $m \geq 3$ , so $m = r s$ with $1 < r < m$ and $1 < s < m$ . Since $m$ is odd, $r$ and $s$ are odd (if either were even, so would be $m$ ), so each has the form $4 k + 1$ or $4 k + 3$ . They cannot both have the form $4 k + 1$ , since then $m$ would too, and by the uniqueness of the remainder $m$ cannot have both forms. So one of them, say $r$ , has the form $4 k + 3$ . As $r < m$ , the minimality of $m$ gives $r$ a prime divisor $q$ of the form $4 k + 3$ . Then $q ∣ r$ and $r ∣ m$ , so $q ∣ m$ , contradicting the choice of $m$ . $□$

Theorem. There are infinitely many primes of the form $4 k + 3$ .

Proof. Suppose, for contradiction, that there are only finitely many, and list them all as $p_{1}, p_{2}, \dots, p_{k}$ ; the list is not empty, since $3$ is on it. Let

N = 4 p_{1} p_{2} \dots p_{k} - 1 = 4 (p_{1} p_{2} \dots p_{k} - 1) + 3

so $N$ is a positive integer of the form $4 k + 3$ . By the lemma, $N$ has a prime divisor $q$ of the form $4 k + 3$ . By assumption, $q$ is one of $p_{1}, \dots, p_{k}$ , so $q$ divides $4 p_{1} p_{2} \dots p_{k}$ . Since $q$ also divides $N$ , it divides the difference $4 p_{1} p_{2} \dots p_{k} - N = 1$ , which is impossible for a prime. Hence there are infinitely many primes of the form $4 k + 3$ . $□$

The choice of $N$ is careful. The factor $4$ and the $- 1$ make $N$ of the form $4 k + 3$ , which is what calls the lemma into play. The more obvious $N = p_{1} p_{2} \dots p_{k} + 1$ might be of either form. With $p_{1} = 3$ and $p_{2} = 7$ the proof builds $N = 83$ , which is itself a prime of the form $4 k + 3$ . Adding $11$ to the list gives $N = 923 = 13 \times 71$ , and $71 = 4 \times 17 + 3$ is the new prime, as promised, while $13$ has the form $4 k + 1$ .

Now you. Prove that there are infinitely many primes of the form $6 k + 5$ .

Answer

Facts about remainders. By the division algorithm every integer has one of the forms $6 k, 6 k + 1, \dots, 6 k + 5$ . An integer of the form $6 k$ , $6 k + 2$ or $6 k + 4$ is even, and one of the form $6 k + 3$ is divisible by $3$ . A product of numbers of the form $6 k + 1$ has that form, since $(6 s + 1) (6 t + 1) = 6 (6 s t + s + t) + 1$ .

Lemma: every positive integer of the form $6 k + 5$ has a prime divisor of that form. Suppose not, and let $m$ be the least positive integer of the form $6 k + 5$ with no prime divisor of that form. Then $m$ is not prime, so $m = r s$ with $1 < r, s < m$ . Now $m = 2 (3 k + 2) + 1$ is odd and $m = 3 (2 k + 1) + 2$ is not divisible by $3$ , so neither $r$ nor $s$ is even or divisible by $3$ (either would pass to $m$ ). Hence each of $r$ and $s$ has the form $6 k + 1$ or $6 k + 5$ . They are not both of the form $6 k + 1$ , or $m$ would be. So one, say $r$ , has the form $6 k + 5$ and is smaller than $m$ , and it has a prime divisor of that form, which then divides $m$ . This contradicts the choice of $m$ .

Theorem. Suppose there are only finitely many primes of the form $6 k + 5$ , listed as $p_{1}, \dots, p_{k}$ (the list contains $5$ ). Let $N = 6 p_{1} \dots p_{k} - 1 = 6 (p_{1} \dots p_{k} - 1) + 5$ . By the lemma, $N$ has a prime divisor $q$ of the form $6 k + 5$ , which must be some $p_{i}$ and so divides $6 p_{1} \dots p_{k}$ . Then $q$ divides $6 p_{1} \dots p_{k} - N = 1$ , which is impossible. So there are infinitely many primes of the form $6 k + 5$ .

Why does the same argument fail for primes of the form

4 k + 1

Try it. Suppose $p_{1}, \dots, p_{k}$ are all the primes of the form $4 k + 1$ , and let $N = 4 p_{1} \dots p_{k} + 1$ , of the form $4 k + 1$ . The argument needs $N$ to have a prime divisor of the form $4 k + 1$ , and that is where it breaks: a product of two numbers of the form $4 k + 3$ has the form $4 k + 1$ , since $(4 s + 3) (4 t + 3) = 4 (4 s t + 3 s + 3 t + 2) + 1$ . So a number of the form $4 k + 1$ can have only prime divisors of the other kind. The very first case shows it: with the list ${5}$ , $N = 21 = 3 \times 7$ , and neither factor has the form $4 k + 1$ . The lemma has no analogue, and the argument proves nothing.

The theorem is still true, and a different choice of $N$ proves it: take $N = (2 p_{1} \dots p_{k})^{2} + 1$ . The missing ingredient is that every odd prime dividing a number of the form $x^{2} + 1$ has the form $4 k + 1$ , which follows from Fermat's little theorem (the Discrete Mathematics course proves it in its lesson on Fermat, Euler and RSA). Granting that, a prime divisor of $N$ has the form $4 k + 1$ and is not on the list, since it does not divide $N - 1$ .

These are the first cases of a much larger theorem, proved by Peter Gustav Lejeune Dirichlet in 1837: if $a$ and $d$ are positive integers with no common divisor greater than $1$ , the progression $a, a + d, a + 2 d, \dots$ contains infinitely many primes. Euclid-style arguments work only for a few progressions, and Dirichlet's proof needed new tools from analysis, in the tradition that Euler's proof of the infinitude of primes began. It is often counted as the birth of analytic number theory.

The pigeonhole principle

Some existence proofs need no construction at all, only counting. If thirteen people are in a room, two of them were born in the same month. Nobody can say which two without asking, but the claim is certain, because twelve months cannot give thirteen people a month each.

Theorem (the pigeonhole principle). If more than $k$ objects are placed in $k$ boxes, some box contains at least two objects.

Proof. Let $n > k$ objects be placed in $k$ boxes, and suppose, for contradiction, that every box contains at most one. Then the total number of objects is at most $1 + 1 + \dots + 1 = k$ , so $n \leq k$ , contradicting $n > k$ . $□$

The proof is really a contrapositive: "if every box holds at most one object, there are at most $k$ objects" is obvious, and the principle is its contrapositive. Stated in the language of the lesson on functions, it says that a function from a set of $n$ elements to a set of $k$ elements, with $n > k$ , cannot be injective: two elements of the first set have the same value.

The principle itself is trivial. The skill lies in choosing the objects and the boxes so that "two objects in one box" says something useful. The proof then names no particular pair, so the argument is non-constructive in the sense of the previous lesson.

Example. Prove that among any five different integers chosen from $1, 2, \dots, 8$ , there are two whose sum is $9$ .

Make four boxes, one for each pair of numbers summing to $9$ : ${1, 8}$ , ${2, 7}$ , ${3, 6}$ , ${4, 5}$ . Every number from $1$ to $8$ belongs to exactly one box. Put each of the five chosen numbers in its box. Five numbers in four boxes means, by the pigeonhole principle, that some box receives two of them, and since the chosen numbers are different, they are the two different members of that box. Their sum is $9$ .

Five is the least number that works: the four numbers $1, 2, 3, 4$ contain no two summing to $9$ . A pigeonhole argument is sharp exactly when the objects can be spread one per box, and checking that is how to tell whether the bound can be improved.

Now you. Let $n$ be a natural number. Prove that among any $n + 1$ integers there are two whose difference is divisible by $n$ .

Answer

By the division algorithm each integer has a remainder on division by $n$ , one of the $n$ values $0, 1, \dots, n - 1$ . Use these remainders as boxes. The $n + 1$ integers go into $n$ boxes, so by the pigeonhole principle two of them, say $a$ and $b$ , have the same remainder $r$ : $a = n q + r$ and $b = n q' + r$ for integers $q$ and $q'$ . Then $a - b = n (q - q')$ , and $q - q'$ is an integer, so $n ∣ a - b$ .

The integers need not be different: if two of them are equal, their difference $0$ is divisible by $n$ anyway. And $n + 1$ is sharp, since $0, 1, \dots, n - 1$ are $n$ integers whose differences are all strictly between $- n$ and $n$ and non-zero, so none is divisible by $n$ .

When there are many more objects than boxes, the conclusion strengthens. Write $⌈ x ⌉$ for the ceiling of $x$ , the least integer greater than or equal to $x$ , so $⌈ 2.1 ⌉ = 3$ and $⌈ 3 ⌉ = 3$ .

Theorem (generalised pigeonhole principle). If $n$ objects are placed in $k$ boxes, some box contains at least $⌈ \frac{n}{k} ⌉$ objects.

Proof. Suppose, for contradiction, that every box contains at most $⌈ \frac{n}{k} ⌉ - 1$ objects. By the definition of the ceiling, $⌈ \frac{n}{k} ⌉ - 1 < \frac{n}{k}$ , since otherwise $⌈ \frac{n}{k} ⌉ - 1$ would be an integer at least $\frac{n}{k}$ and smaller than the least one. So the total number of objects is at most $k (⌈ \frac{n}{k} ⌉ - 1) < k \cdot \frac{n}{k} = n$ , contradicting that there are $n$ objects. $□$

In words: some box holds at least the average number of objects. A hundred people include at least $⌈ \frac{100}{12} ⌉ = 9$ born in the same month. No human head has a million hairs, so the possible numbers of hairs are $0$ to $999 999$ , a million boxes, and London has more than eight million inhabitants; so at least $⌈ \frac{8 000 001}{1 000 000} ⌉ = 9$ Londoners have exactly the same number of hairs on their heads.

The generalised principle proves a result that sounds like it must need a search.

Theorem. In any group of six people, where each pair either know each other or do not, there are three who all know one another or three who are all strangers to one another.

Proof. Pick one person, $A$ . The other five fall into two boxes: those who know $A$ and those who do not. By the generalised principle one box contains at least $⌈ \frac{5}{2} ⌉ = 3$ people.

Suppose three people $B$ , $C$ , $D$ all know $A$ . If any two of $B$ , $C$ , $D$ know each other, those two together with $A$ are three people who all know one another. If no two of them know each other, then $B$ , $C$ , $D$ are three mutual strangers. Either way the claim holds.

If instead three people $B$ , $C$ , $D$ are all strangers to $A$ , the same argument with "know" and "do not know" exchanged applies: if two of them are strangers, they and $A$ are three mutual strangers, and otherwise $B$ , $C$ , $D$ all know one another. $□$

Six is the least number that works. Five people seated at a round table, each knowing exactly their two neighbours, contain no three mutual acquaintances (among any three at a table of five, two are not neighbours) and no three mutual strangers (among any three, two are neighbours). The theorem is the first case of Ramsey theory, named after Frank Ramsey, whose 1930 paper proved that such structure is unavoidable in every large enough system: complete disorder is impossible.

Does the pigeonhole principle hold for infinite sets?

Not in the same form, and the failure is instructive. Put the natural numbers, as objects, into the boxes labelled $2, 3, 4, \dots$ by sending $n$ to box $n + 1$ . Every box receives exactly one object, although there are, in the naive sense, more objects than boxes, since the objects include $1$ and the boxes do not. So "more objects than boxes forces a shared box" is false for infinite collections, and the reason is that "more" has lost its meaning.

Galileo noticed a version of this in 1638, in his Two New Sciences: the perfect squares $1, 4, 9, 16, \dots$ are a small part of the natural numbers, yet they can be paired off with all of them, $n$ with $n^{2}$ . He concluded that "equal", "greater" and "less" do not apply to infinite quantities. Richard Dedekind in 1888 turned the paradox into a definition: a set is infinite exactly when it can be matched one to one with a part of itself. For finite sets the pigeonhole principle says this never happens, and that is the precise sense in which the principle is a fact about finiteness.

One form does survive. If infinitely many objects are placed in finitely many boxes, some box contains infinitely many. Suppose, for contradiction, that every one of the $k$ boxes held only finitely many, say at most $m_{1}, \dots, m_{k}$ objects. Then there would be at most $m_{1} + \dots + m_{k}$ objects in all, a finite number. This infinite pigeonhole principle is a workhorse of analysis. Applied to a sequence whose terms take only finitely many values, it gives a value taken infinitely often, and so a constant subsequence; refined by repeatedly halving an interval, it proves the theorem of Bolzano and Weierstrass that every bounded sequence of reals has a convergent subsequence.

How to compare the sizes of infinite sets correctly, by matching rather than counting, is the subject of the lesson on countable and uncountable sets, which shows that some infinite sets are genuinely larger than others.

Choosing a method

Try the direct route first. When it stalls, look at the shape of the statement.

If it is a conditional whose hypothesis gives nothing to manipulate while the negation of its conclusion gives a formula, as " $n^{2}$ is even" against " $n$ is odd", use the contrapositive.
If the statement is a negative with no hypothesis to start from, such as "is irrational", "there is no largest", "has no solution" or "there are infinitely many", use contradiction, since assuming the positive version hands the proof an object to work on.
If the conclusion is an "or", assume that one part fails and prove the other, as in Euclid's lemma.
If the claim is that two things must coincide, or that some part must be large, and no particular one is named, look for boxes and count.

Prefer the contrapositive when both methods work. Its target, $\neg P$ , is fixed in advance, so a mistake usually shows as a failure to arrive. A proof by contradiction accepts any impossibility, including one produced by an algebra slip, so a wrong one can look exactly like a right one. A proof by contradiction also keeps an assumption in the air that will turn out false, and every line written under it is true only in an impossible world. A reader checking the proof has to keep track of which lines are established facts and which depend on the doomed assumption, and the more lines there are, the harder that becomes.

Methods also combine. A biconditional may have one direction proved directly and the other by contrapositive, as with " $n$ is even if and only if $n^{2}$ is even". A proof by contradiction may use a contrapositive inside it, as the proof for $\sqrt{3}$ did. And a proof by cases may use a different method in each case.

Contradictions in disguise

Many proofs by contradiction are something else wearing its opening sentence. The test is to delete "suppose, for contradiction" and ask whether the assumption was ever used.

Consider: "Suppose, for contradiction, that the sum of odd integers $a$ and $b$ is odd. Write $a = 2 k + 1$ and $b = 2 m + 1$ . Then $a + b = 2 (k + m + 1)$ , which is even, a contradiction." The assumed oddness of $a + b$ did nothing until the last word. Strip the wrapper and what remains is a direct proof that $a + b$ is even. This is the fake contradiction: a direct proof with a false assumption bolted to the front and a clash with it bolted to the end.

The second disguise hides a contrapositive. "Suppose $n^{2}$ is even and $n$ is odd. Then $n = 2 k + 1$ , so $n^{2}$ is odd, contradicting $n^{2}$ even." The hypothesis appears only in the final clash; the work ran from $\neg Q$ to $\neg P$ . Writing it as a contrapositive says the same thing with fewer assumptions in the air.

The textbook proof of Euclid's theorem is the third: its argument works on any finite list, so the assumption that the list held every prime was never needed. Removing a disguise improves a proof. Every line becomes true, rather than true only in an impossible world about to collapse, and a stronger or constructive result often appears, as it did with Euclid.

Worse than a disguise is an assumption that is not the negation at all. A proof by contradiction of $Q$ must assume exactly $\neg Q$ , and if it assumes something stronger, the contradiction may come from the extra strength and prove nothing. Here is the pattern at its plainest.

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

Proof. Suppose, for contradiction, that $n^{2} + n$ is odd for every integer $n$ . Taking $n = 1$ gives $1 + 1 = 2$ odd, a contradiction.

The claim is true, but this is not a proof of it. The negation of $\forall n (n^{2} + n is even)$ is $\exists n (n^{2} + n is odd)$ : one integer where it fails, which the proof must name as an arbitrary unknown, not a universal failure that can be tested at any convenient value. The same "proof" would establish that every integer is prime: suppose every integer is composite; then $2$ is composite, a contradiction. The same mistake in words is "suppose $a$ and $b$ are both odd" as the negation of " $a$ and $b$ are both even", when the negation is "at least one of $a$ and $b$ is odd". Before writing "suppose, for contradiction", compute the negation by the rules of the lesson on quantifiers and write it down in full.

The last hazard is the one the previous section warned about: a proof by contradiction that reaches its contradiction by an error. Every false step leads somewhere false, and in a proof by contradiction a false conclusion is the goal, so an algebra slip can look like success. When a contradiction arrives unexpectedly early, or from a line that did not use the assumption, suspect the algebra before celebrating.

What these methods leave open

Several proofs in this lesson ran the same way: take the least natural number with some property, the least denominator for $\sqrt{2}$ , the least divisor greater than $1$ , the least number of the form $4 k + 3$ without a prime divisor of that form, and show that a smaller one would exist. The engine in each was the well-ordering principle, not the contrapositive or the contradiction around it.

Some claims need that engine and nothing else. Take "every integer $n \geq 2$ is a product of primes". For an arbitrary $n$ , either $n$ is prime, or $n = a b$ with $a$ and $b$ smaller than $n$ ; to finish, the proof needs $a$ and $b$ to be products of primes already, which is the claim for smaller numbers. A direct argument about an arbitrary $n$ cannot supply that, and neither can the contrapositive or a contradiction on their own: the argument for each $n$ leans on the cases below it, and checking them one by one never ends. The next lesson turns the smallest-counterexample idea into a method of its own, induction, which follows such a chain all the way up, and proves that it and well-ordering are two forms of the same principle.

Problems

Work each problem on paper before opening anything; for Core and Challenge problems, try the hint before the solution.

Warm-up

1. For each statement, write its contrapositive (if it is a conditional) and the assumption with which a proof by contradiction would begin. (a) For every integer $n$ , if $n^{2}$ is odd then $n$ is odd. (b) For all real numbers $x$ and $y$ , if $x + y$ is irrational then $x$ is irrational or $y$ is irrational. (c) There is no largest prime. (d) For every natural number $n$ , if $2^{n} - 1$ is prime then $n$ is prime.

Solution

(a) Contrapositive: for every integer $n$ , if $n$ is even then $n^{2}$ is even. Contradiction assumes: there is an integer $n$ with $n^{2}$ odd and $n$ even.

(b) Contrapositive: for all real $x$ and $y$ , if $x$ and $y$ are both rational then $x + y$ is rational (De Morgan turns "not ( $x$ irrational or $y$ irrational)" into " $x$ rational and $y$ rational"). Contradiction assumes: there are real $x$ and $y$ with $x + y$ irrational and both $x$ and $y$ rational.

(c) This is not a conditional, so there is no contrapositive. Contradiction assumes: there is a largest prime, that is, a prime $p$ with $q \leq p$ for every prime $q$ .

(d) Contrapositive: for every natural number $n$ , if $n$ is not prime then $2^{n} - 1$ is not prime. Contradiction assumes: there is a natural number $n$ that is not prime with $2^{n} - 1$ prime.

In each case the assumption for contradiction is existential: a proof by contradiction of a universal claim assumes one counterexample, not that everything fails.

2. Prove by contrapositive: (a) for every integer $n$ , if $5 n + 3$ is even then $n$ is odd; (b) for all real numbers $x$ and $y$ , if $x + y \geq 2$ then $x \geq 1$ or $y \geq 1$ .

Solution

(a) We prove: if $n$ is not odd then $5 n + 3$ is not even. Let $n$ be an integer that is not odd; then $n$ is even, $n = 2 k$ for some integer $k$ . So $5 n + 3 = 10 k + 3 = 2 (5 k + 1) + 1$ , which is odd, and hence not even. This proves the contrapositive.

(b) The negation of " $x \geq 1$ or $y \geq 1$ " is " $x < 1$ and $y < 1$ ", and the negation of " $x + y \geq 2$ " is " $x + y < 2$ ". So we prove: if $x < 1$ and $y < 1$ then $x + y < 2$ . Let $x$ and $y$ be real numbers with $x < 1$ and $y < 1$ . Adding the inequalities gives $x + y < 2$ . This proves the contrapositive.

In (b) a direct proof would face an "or" in the conclusion with nothing to decide between its parts; the contrapositive turns it into an "and" in the hypothesis, which can be used at once.

3. (a) A drawer holds $10$ black socks and $10$ white socks. How many must be taken out in the dark to be sure of a matching pair? To be sure of two black socks? (b) How many people must be in a room to be sure that five of them were born in the same month? (c) Thirty students sit a test marked in whole numbers from $0$ to $10$ . Prove that at least three of them receive the same mark.

Solution

(a) Three socks. With two colours as boxes, three socks put two in one box, which is a matching pair; two socks are not enough, since they may be one of each colour. For two black socks, twelve: in the worst case the first ten drawn are all white, so eleven may contain only one black sock, while twelve socks include at most ten white ones and so at least two black ones.

(b) $49$ . With twelve months as boxes, $49$ people give some month at least $⌈ \frac{49}{12} ⌉ = 5$ people. With $48$ people it is possible that exactly four were born in each month, so $48$ is not enough.

(c) There are $11$ possible marks, $0$ to $10$ . By the generalised pigeonhole principle, some mark is received by at least $⌈ \frac{30}{11} ⌉ = 3$ students, since $\frac{30}{11}$ lies between $2$ and $3$ .

4. Prove by contradiction: (a) there are no integers $m$ and $n$ with $14 m + 21 n = 100$ ; (b) there are no natural numbers $x$ and $y$ with $x^{2} - y^{2} = 1$ .

Solution

(a) Suppose, for contradiction, that $14 m + 21 n = 100$ for some integers $m$ and $n$ . Then $100 = 7 (2 m + 3 n)$ , so $7 ∣ 100$ . But $100 = 7 \times 14 + 2$ , and by the uniqueness of the remainder, the remainder of $100$ on division by $7$ is $2$ , not $0$ . So $7$ does not divide $100$ , a contradiction.

(b) Suppose, for contradiction, that $x^{2} - y^{2} = 1$ for some natural numbers $x$ and $y$ . Then $(x - y) (x + y) = 1$ . Here $x + y \geq 2$ is a positive integer, so $x - y$ is positive too, since the product is positive; hence $x - y \geq 1$ , and $(x - y) (x + y) \geq 1 \times 2 = 2 > 1$ , a contradiction.

Core

5. Prove that $\sqrt{6}$ is irrational, and deduce that $\sqrt{2} + \sqrt{3}$ is irrational.

Hint

For $\sqrt{6}$ , follow the proof for $\sqrt{2}$ , using Euclid's lemma with the prime $2$ . For the sum, suppose it equals a rational $r$ and square both sides.

Solution

$\sqrt{6}$ is irrational. Suppose, for contradiction, that $\sqrt{6} = \frac{a}{b}$ with $a$ an integer and $b$ a natural number, and choose $b$ as small as possible, by the well-ordering principle. Squaring, $a^{2} = 6 b^{2} = 2 (3 b^{2})$ , so $2 ∣ a^{2}$ , and by Euclid's lemma $2 ∣ a$ . Write $a = 2 c$ . Then $4 c^{2} = 6 b^{2}$ , so $2 c^{2} = 3 b^{2}$ . Hence $2 ∣ 3 b^{2}$ , and by Euclid's lemma $2 ∣ 3$ or $2 ∣ b^{2}$ . The first is false, so $2 ∣ b^{2}$ , and by Euclid's lemma again $2 ∣ b$ . Write $b = 2 d$ with $d$ a natural number smaller than $b$ . Then $\sqrt{6} = \frac{2 c}{2 d} = \frac{c}{d}$ , contradicting the minimality of $b$ .

$\sqrt{2} + \sqrt{3}$ is irrational. Suppose, for contradiction, that $\sqrt{2} + \sqrt{3} = r$ with $r$ rational. Squaring,

r^{2} = 2 + 2 \sqrt{6} + 3 = 5 + 2 \sqrt{6}

so $\sqrt{6} = \frac{r^{2} - 5}{2}$ . Sums, differences, products and quotients (by non-zero numbers) of rationals are rational, so $\frac{r^{2} - 5}{2}$ is rational, and therefore $\sqrt{6}$ is rational, contradicting the first part. Hence $\sqrt{2} + \sqrt{3}$ is irrational.

The sum of two irrationals can be rational ( $\sqrt{2} + (- \sqrt{2}) = 0$ ), so the second part needed an argument particular to these two numbers; squaring converted it into a statement about $\sqrt{6}$ alone.

6. Find the flaw in this proof, show that the claim is false, and state and prove a correct claim with the same hypothesis.

Claim. For every integer $n$ , if $4 ∣ n^{2}$ then $4 ∣ n$ .

Proof. We prove the contrapositive. Suppose $4$ does not divide $n$ . By the division algorithm, $n = 4 k + r$ with $r$ equal to $1$ , $2$ or $3$ . Then $n^{2} = 16 k^{2} + 8 k r + r^{2} = 4 (4 k^{2} + 2 k r) + r^{2}$ , and $r^{2}$ is $1$ , $4$ or $9$ , which is not divisible by $4$ . So $n^{2}$ is not divisible by $4$ .

Hint

Check the three values of $r^{2}$ one at a time.

Solution

The flaw is the claim that none of $1$ , $4$ , $9$ is divisible by $4$ : the value $r = 2$ gives $r^{2} = 4$ , which is. In that case $n^{2} = 4 (4 k^{2} + 4 k + 1)$ is divisible by $4$ , and the contrapositive fails. The case split was correct and complete; one case was simply checked wrongly.

The claim is false, and $n = 2$ is a counterexample: $4 ∣ 4 = 2^{2}$ , but $4$ does not divide $2$ . (This is the step that stopped the irrationality proof from "proving" $\sqrt{4}$ irrational.)

A correct claim: for every integer $n$ , if $4 ∣ n^{2}$ then $n$ is even. We prove the contrapositive: if $n$ is not even then $4$ does not divide $n^{2}$ . Let $n$ be odd, $n = 2 k + 1$ . Then $n^{2} = 4 k^{2} + 4 k + 1 = 4 (k^{2} + k) + 1$ , so by the uniqueness of the remainder, $n^{2}$ leaves remainder $1$ on division by $4$ , and $4$ does not divide it.

7. Prove or disprove each statement. (a) If $p$ is a prime other than $3$ , then $p^{2} + 2$ is not prime. (b) Every positive integer of the form $4 k + 1$ has a prime divisor of the form $4 k + 1$ .

Hint

For (a), divide by $3$ . For (b), look back at why the lesson's argument for primes of the form $4 k + 3$ could not be copied.

Solution

(a) True. Let $p$ be a prime with $p \neq 3$ . Then $3$ does not divide $p$ , since the only positive divisors of $p$ are $1$ and $p$ , and neither is $3$ . So $p = 3 k + 1$ or $p = 3 k + 2$ for some integer $k$ . In the first case $p^{2} + 2 = 9 k^{2} + 6 k + 3 = 3 (3 k^{2} + 2 k + 1)$ , and in the second $p^{2} + 2 = 9 k^{2} + 12 k + 6 = 3 (3 k^{2} + 4 k + 2)$ . Either way $3 ∣ p^{2} + 2$ . Since $p \geq 2$ , $p^{2} + 2 \geq 6 > 3$ , so $3$ is a divisor of $p^{2} + 2$ strictly between $1$ and $p^{2} + 2$ , and $p^{2} + 2$ is not prime.

Equivalently, by contrapositive: if $p$ and $p^{2} + 2$ are both prime, then $p = 3$ . And $p = 3$ does give a prime, $11$ .

(b) False. The number $21 = 4 \times 5 + 1$ has the form $4 k + 1$ , and its only prime divisors are $3$ and $7$ , both of the form $4 k + 3$ . (The number $1 = 4 \times 0 + 1$ is an even simpler counterexample, having no prime divisor at all, but $21$ shows that the failure is not just a matter of $1$ .) The reason is that $(4 s + 3) (4 t + 3)$ has the form $4 k + 1$ .

8. Prove that for every natural number $n$ , if $2^{n} - 1$ is prime then $n$ is prime. Show that the converse is false.

Hint

Prove the contrapositive. If $n = a b$ , put $x = 2^{a}$ and factor $x^{b} - 1$ .

Solution

We prove the contrapositive: if $n$ is not prime, then $2^{n} - 1$ is not prime.

Let $n$ be a natural number that is not prime. If $n = 1$ , then $2^{n} - 1 = 1$ , which is not prime. Otherwise $n$ is composite, so $n = a b$ with $1 < a < n$ and $1 < b < n$ . Put $x = 2^{a}$ . Then $2^{n} - 1 = x^{b} - 1$ , and

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

since multiplying out the right side, every power $x^{j}$ with $1 \leq j \leq b - 1$ appears once with each sign and cancels, leaving $x^{b} - 1$ . So $x - 1 = 2^{a} - 1$ divides $2^{n} - 1$ . Since $a \geq 2$ , $2^{a} - 1 \geq 3 > 1$ , and since $a < n$ , $2^{a} - 1 < 2^{n} - 1$ . So $2^{n} - 1$ has a divisor strictly between $1$ and itself, and is not prime.

The converse, "if $n$ is prime then $2^{n} - 1$ is prime", is false: $11$ is prime, but $2^{11} - 1 = 2047 = 23 \times 89$ . Primes of the form $2^{n} - 1$ are called Mersenne primes, after Marin Mersenne, and the problem shows that searching for them only needs to consider prime exponents.

9. Prove that in any group of $n \geq 2$ people, where friendship is mutual and nobody counts as their own friend, two people have the same number of friends within the group.

Hint

The possible numbers of friends are $0, 1, \dots, n - 1$ , which is $n$ boxes for $n$ people: one too many. Show that two of these boxes cannot both be occupied.

Solution

Each person has between $0$ and $n - 1$ friends in the group. The values $0$ and $n - 1$ cannot both occur. For suppose some person $A$ has $n - 1$ friends; then $A$ is a friend of every other person, and since friendship is mutual, every other person has at least one friend, $A$ . So nobody has $0$ friends. (And $A$ has $n - 1 \geq 1$ friends, so $A$ does not have $0$ either.)

So either every person has between $0$ and $n - 2$ friends, or every person has between $1$ and $n - 1$ friends. In either case the numbers of friends take at most $n - 1$ values. The $n$ people are placed in at most $n - 1$ boxes by their number of friends, so by the pigeonhole principle two of them are in the same box: they have the same number of friends.

10. Prove that for every natural number $n$ there is a positive multiple of $n$ whose decimal digits are all $0$ or $1$ .

Hint

Consider the $n + 1$ numbers $1, 11, 111, \dots$ , the last with $n + 1$ ones, and their remainders on division by $n$ .

Solution

For $j = 1, 2, \dots, n + 1$ , let $R_{j}$ be the number whose decimal representation consists of $j$ ones, so $R_{1} = 1$ , $R_{2} = 11$ , $R_{3} = 111$ . There are $n + 1$ of these numbers and only $n$ possible remainders on division by $n$ , so by the pigeonhole principle two of them, $R_{i}$ and $R_{j}$ with $i < j$ , have the same remainder. As in the Now you on the pigeonhole principle, $n$ divides $R_{j} - R_{i}$ .

Now $R_{j} - R_{i}$ is the number made of $j - i$ ones followed by $i$ zeros: for instance $R_{5} - R_{2} = 11 111 - 11 = 11 100$ . In general $R_{j} = R_{j - i} \times 10^{i} + R_{i}$ , since the first $j - i$ digits of $R_{j}$ are ones followed by the last $i$ , which form $R_{i}$ ; so $R_{j} - R_{i} = R_{j - i} \times 10^{i}$ . This is positive, a multiple of $n$ , and every digit is $0$ or $1$ .

For example, with $n = 7$ , the remainders of $1, 11, 111, 1111, 11 111, 111 111$ are $1, 4, 6, 5, 2, 0$ , so $111 111 = 7 \times 15 873$ already works. The proof does not find the multiple, but it guarantees one with at most $n + 1$ digits.

11. Five points are placed in a square of side $2$ (inside or on the boundary). Prove that two of them are at distance at most $\sqrt{2}$ from each other. Show that $\sqrt{2}$ cannot be replaced by any smaller number.

Hint

Cut the square into four squares of side $1$ .

Solution

Place the square with corners $(0, 0)$ and $(2, 2)$ , and cut it by the lines $x = 1$ and $y = 1$ into four closed squares of side $1$ . Every point of the big square lies in at least one small square; assign each of the five points to one small square containing it. Five points in four squares means, by the pigeonhole principle, that two points, $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$ , are assigned to the same small square.

Both lie in a square of side $1$ , so $| x_{1} - x_{2} | \leq 1$ and $| y_{1} - y_{2} | \leq 1$ . Their distance is

\sqrt{(x_{1} - x_{2})^{2} + (y_{1} - y_{2})^{2}} \leq \sqrt{1 + 1} = \sqrt{2}

To see that $\sqrt{2}$ is best possible, place the points at the four corners and the centre $(1, 1)$ . Two corners are at distance at least $2$ , and the centre is at distance exactly $\sqrt{2}$ from each corner, so the smallest distance between two of the five points is $\sqrt{2}$ . No smaller number can replace it.

12. Let $a$ , $b$ and $c$ be odd integers. Prove that the equation $a x^{2} + b x + c = 0$ has no rational solution.

Hint

Suppose $x = \frac{p}{q}$ with $q$ as small as possible, so that $p$ and $q$ are not both even. Clear denominators and look at the parity of each term.

Solution

Suppose, for contradiction, that $x = \frac{p}{q}$ is a solution, with $p$ an integer and $q$ a natural number chosen as small as possible by the well-ordering principle. Then $p$ and $q$ are not both even: if they were, $\frac{p}{q} = \frac{p / 2}{q / 2}$ with the natural number $\frac{q}{2}$ smaller than $q$ .

Multiplying $a \frac{p^{2}}{q^{2}} + b \frac{p}{q} + c = 0$ by $q^{2}$ gives

a p^{2} + b p q + c q^{2} = 0

There are three cases, using that a product of integers is odd exactly when every factor is odd, and that a sum of three integers is odd when one or three of them are odd.

If $p$ and $q$ are both odd, then $a p^{2}$ , $b p q$ and $c q^{2}$ are all odd, and their sum is odd.

If $p$ is even and $q$ odd, then $a p^{2}$ and $b p q$ are even and $c q^{2}$ is odd, so the sum is odd.

If $p$ is odd and $q$ even, then $a p^{2}$ is odd and $b p q$ and $c q^{2}$ are even, so the sum is odd.

In every case $a p^{2} + b p q + c q^{2}$ is odd, but it equals $0$ , which is even, and no integer is both. This contradiction shows that no rational number is a solution.

The discriminant gives a check in an example: $x^{2} + x + 1 = 0$ has no real solution at all, but $x^{2} + 3 x + 1 = 0$ has the real solutions $\frac{- 3 \pm \sqrt{5}}{2}$ , and the problem shows, without computing them, that they are irrational.

Challenge

13. Prove that for every natural number $n \geq 2$ , the number $1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$ is not an integer.

Hint

Let $2^{k}$ be the largest power of $2$ that is at most $n$ . Show that $2^{k}$ is the only number from $1$ to $n$ divisible by $2^{k}$ . Then multiply the sum by $2^{k - 1}$ times the product of the odd numbers up to $n$ , and look at which terms become integers.

Solution

Let $n \geq 2$ and write $H = 1 + \frac{1}{2} + \dots + \frac{1}{n}$ . Let $2^{k}$ be the largest power of $2$ with $2^{k} \leq n$ ; then $k \geq 1$ , since $2 \leq n$ , and $2^{k + 1} > n$ .

Step 1: among $1, 2, \dots, n$ , only $2^{k}$ is divisible by $2^{k}$ . Every $i$ from $1$ to $n$ can be written $i = 2^{j} o$ with $j \geq 0$ and $o$ odd (divide out factors of $2$ until an odd number remains; the process stops because the numbers decrease). If $j \geq k + 1$ , then $i \geq 2^{k + 1} > n$ , which is impossible, so $j \leq k$ . If $j = k$ and $o \geq 3$ , then $i \geq 3 \times 2^{k} > 2^{k + 1} > n$ , again impossible. So $j = k$ only for $i = 2^{k}$ , and every other $i \leq n$ has $j \leq k - 1$ .

Step 2: clear most denominators. Let $m$ be the product of all the odd numbers from $1$ to $n$ , which is odd, and let $M = 2^{k - 1} m$ , an integer since $k \geq 1$ . For each $i \leq n$ with $i \neq 2^{k}$ , write $i = 2^{j} o$ as above, with $j \leq k - 1$ . The odd number $o$ is at most $n$ , so it is one of the factors of $m$ , and

\frac{M}{i} = 2^{k - 1 - j} \cdot \frac{m}{o}

is an integer. For $i = 2^{k}$ , however, $\frac{M}{2^{k}} = \frac{m}{2}$ , which is not an integer, because $m$ is odd.

Step 3: the contradiction. Suppose, for contradiction, that $H$ is an integer. Then $M H$ is an integer. But

M H = \sum_{i \neq 2^{k}} \frac{M}{i} + \frac{m}{2}

where the sum is an integer, say $S$ , by Step 2. So $\frac{m}{2} = M H - S$ is an integer, and $m$ is even, contradicting that $m$ is a product of odd numbers. Hence $H$ is not an integer.

For example, with $n = 6$ , $k = 2$ , $m = 1 \times 3 \times 5 = 15$ and $M = 30$ , and $30 H = 30 + 15 + 10 + 7.5 + 6 + 5 = 73.5$ : every term is an integer except the one from $\frac{1}{4}$ .

14. Prove that every sequence of $n^{2} + 1$ different real numbers contains an increasing subsequence of length $n + 1$ or a decreasing subsequence of length $n + 1$ . Show that $n^{2} + 1$ cannot be replaced by $n^{2}$ .

Hint

Label each term with a pair of numbers: the length of the longest increasing subsequence that starts at that term, and the length of the longest decreasing one. If the claim failed, how many different labels would there be?

Solution

Let $a_{1}, a_{2}, \dots, a_{n^{2} + 1}$ be different real numbers. A subsequence is a choice of terms $a_{i_{1}}, a_{i_{2}}, \dots, a_{i_{r}}$ with $i_{1} < i_{2} < \dots < i_{r}$ , kept in order; it is increasing if $a_{i_{1}} < a_{i_{2}} < \dots < a_{i_{r}}$ and decreasing if the inequalities are reversed. For each position $i$ , let $u_{i}$ be the length of the longest increasing subsequence that starts with $a_{i}$ , and $d_{i}$ the length of the longest decreasing subsequence that starts with $a_{i}$ . Both are at least $1$ , since $a_{i}$ alone is such a subsequence.

Suppose, for contradiction, that there is no increasing and no decreasing subsequence of length $n + 1$ . Then $1 \leq u_{i} \leq n$ and $1 \leq d_{i} \leq n$ for every $i$ , so each pair $(u_{i}, d_{i})$ is one of the $n^{2}$ pairs of numbers from $1$ to $n$ . There are $n^{2} + 1$ positions, so by the pigeonhole principle two positions $i < j$ have the same pair: $u_{i} = u_{j}$ and $d_{i} = d_{j}$ .

Since the terms are different, $a_{i} < a_{j}$ or $a_{i} > a_{j}$ . If $a_{i} < a_{j}$ , put $a_{i}$ in front of a longest increasing subsequence starting with $a_{j}$ . Since $i < j$ and $a_{i} < a_{j}$ , the result is an increasing subsequence starting with $a_{i}$ , of length $u_{j} + 1$ , so $u_{i} \geq u_{j} + 1 > u_{j}$ , contradicting $u_{i} = u_{j}$ . If $a_{i} > a_{j}$ , the same argument with a longest decreasing subsequence starting at $a_{j}$ gives $d_{i} \geq d_{j} + 1$ , contradicting $d_{i} = d_{j}$ . Either way we have a contradiction, which proves the claim.

For the sharpness, arrange $1, 2, \dots, n^{2}$ in $n$ blocks, each block decreasing and each block entirely above the one before:

n, n - 1, \dots, 1, 2 n, 2 n - 1, \dots, n + 1, \dots, n^{2}, n^{2} - 1, \dots, n^{2} - n + 1

An increasing subsequence can take at most one term from each block, since each block decreases, so it has length at most $n$ . A decreasing subsequence cannot use two blocks, since every term of a later block is larger than every term of an earlier one, so it has length at most $n$ . For $n = 2$ this is the sequence $2, 1, 4, 3$ .

The theorem was proved by Paul Erdős and George Szekeres in 1935. It is a typical pigeonhole argument in that the boxes are not visible in the problem: the labels $(u_{i}, d_{i})$ had to be invented.

15. Prove that any set of ten different two-digit numbers (integers from $10$ to $99$ ) contains two disjoint non-empty subsets with the same sum.

Hint

Count the non-empty subsets, and count the possible sums. Then make two subsets with equal sums disjoint without changing the fact that their sums are equal.

Solution

Let $X$ be a set of ten different two-digit numbers. A set of ten elements has $2^{10} = 1024$ subsets, of which $1023$ are non-empty. The sum of a non-empty subset is at least $10$ and at most the sum of all ten elements, which is less than $10 \times 100 = 1000$ . So the sums of the non-empty subsets lie among the integers from $10$ to $999$ , which are $990$ values. Since $1023 > 990$ , the pigeonhole principle gives two different non-empty subsets $A$ and $B$ of $X$ with the same sum.

Now remove their common elements: let $A' = A ∖ B$ and $B' = B ∖ A$ , the elements of $A$ not in $B$ and the elements of $B$ not in $A$ . They are disjoint, and removing the same elements, those of $A \cap B$ , from both subsets reduces both sums by the same amount, so $A'$ and $B'$ still have equal sums.

It remains to check that neither is empty. Suppose, for contradiction, that $A'$ is empty. Then every element of $A$ is in $B$ , and since $A \neq B$ , $B$ has some element not in $A$ . Every element of $X$ is positive, so the sum of $B$ exceeds the sum of $A$ , contradicting that the sums are equal. So $A'$ is not empty, and by the same argument with $A$ and $B$ exchanged neither is $B'$ .

This was Problem 1 of the International Mathematical Olympiad of 1972. The count shows that the argument has room to spare; it works for any ten positive integers below $100$ , and the actual sums are never found.