Proof by Contradiction

Main idea

To prove something is true, pretend it's false and follow the consequences until you hit something impossible. Since honest reasoning can't lead to nonsense, the pretending was the problem. That's how we know √2 isn't a fraction and the primes never run out.

Euclid: there are infinitely many primes

{\htmlData{sym=0}{N}} = {\htmlData{sym=1}{p_1}} p_2 \cdots {\htmlData{sym=2}{p_k}} + 1

What the symbols mean

$N$
Euclid's number
One more than the product of all the supposed primes.
$p_1$
First prime
The smallest prime, 2.
$p_k$
Last prime
The supposedly largest prime.

Explanation

A proof by contradiction is simply this: to show something is true, pretend for a moment that it's false, and follow that pretend world until something breaks. Its old Latin name, reductio ad absurdum, means "reduction to absurdity," which describes it nicely: you reduce the opposite claim to nonsense. It's the tool to reach for when a statement says something can't happen or never ends, which is hard to show head-on. The formula above is Euclid's famous trick, and it's only two pieces: $p_1 p_2 \cdots p_k$ (multiply together every prime on a supposedly complete list) and $+ 1$ (add one). That's it; bear with the subscripts.

The pattern: assume the negation of what you want, reason correctly, and arrive at a contradiction (a statement that is both true and false, like " $n$ is even and odd"). Think about why that settles it. Correct reasoning can't produce a contradiction from true assumptions, and every step you took was correct, so the only thing left to blame is the assumption. It must be false, which makes the original statement true.

Euclid's proof. Suppose there were only finitely many primes, $p_1, p_2, \dots, p_k$ . Let $N = p_1 p_2 \cdots p_k + 1$ . Dividing $N$ by any $p_i$ leaves remainder 1, since $N$ is a multiple of $p_i$ plus 1, so no $p_i$ divides $N$ . But $N > 1$ has some prime factor, and that prime isn't on the list. Contradiction: the list wasn't complete.

A common mistake. It's tempting to think the proof shows that $N$ itself is a new prime, because it isn't divisible by anything on the list. It doesn't, and $N$ needn't be prime: $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$ . All the proof needs is that $N$ has some prime factor missing from the list.

$\sqrt{2}$ is irrational. Suppose $\sqrt{2} = a/b$ in lowest terms. Squaring, $a^2 = 2b^2$ , so $a^2$ is even, and by the last lesson that means $a$ is even: $a = 2c$ . Then $4c^2 = 2b^2$ , so $b^2 = 2c^2$ and $b$ is even too, by the same reasoning. But a fraction in lowest terms can't have both parts even. That's the contradiction.

See it

If √2 were a fraction a/b, the line y = √2·x would pass exactly through the whole-number point (b, a). As you can see, the best fractions, 1/1, 3/2, 7/5 and 17/12, get closer and closer to the line, but a² − 2b² keeps bouncing between −1 and 1 and never reaches 0. The proof shows no fraction ever lands exactly on it.

Worked examples

Example 1

Use Euclid's construction on the primes $2, 3, 5, 7$ .

1
Multiply the list and add 1: $N = 2 \cdot 3 \cdot 5 \cdot 7 + 1 = 211$ .

Practice

Type your answer and check it. Solve them all to complete the lesson.

Problem 1+5 XP

Euclid's number for the primes $2, 3, 5$ is:

Problem 2+5 XP

Why can't any of $p_1, \dots, p_k$ divide $N = p_1 \cdots p_k + 1$ ?

Problem 3+5 XP

In the proof that $\sqrt 2$ is irrational, what do we show about $a$ and $b$ after writing $\sqrt 2 = a/b$ in lowest terms?

Problem 4+5 XP

Is $30031 = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1$ prime?

Problem 5+5 XP

A report claims that five test scores average 82, and also that every score was below 80. Assume both and look for a contradiction: if all five scores are below 80, their sum is below what number?

Problem 6+5 XP

To prove "there is no largest even number" by contradiction, what do you assume?

Challenge problem+25 XP

The hardest one here. Get it, and you've got this lesson.

Prove that $\log_2 3$ is irrational. Suppose $\log_2 3 = \frac ab$ with positive integers $a$ and $b$ . Then $2^{a/b} = 3$ , so $2^a = 3^b$ . Why is that impossible?

Where it's used

Security proofs in cryptography often argue by contradiction: if an attacker could break the system, they could also solve a problem believed to be impossibly hard.

Direct Proof and Proof by Contrapositive Mathematical Induction