Proof by contradiction

Proof by contradiction is a way of proving a statement by assuming it is false and showing that this leads to something impossible. If the opposite of the statement can't be true, the statement must be true. It is the method behind two famous proofs you need for A-level Maths: that √2 is irrational, and that there are infinitely many prime numbers.

What is proof by contradiction?

Every statement is either true or false. Suppose you want to prove a statement S. Instead of proving S directly, you assume the opposite, "S is false", and follow the logic carefully. If you arrive at something that can't possibly be true, such as a number that is both odd and even, or 1 = 0, then your assumption must have been wrong. So S is true.

It is especially useful for statements that say something doesn't exist or can't happen: no largest prime, no fraction equal to √2, no whole numbers that solve an equation. Assuming the thing does exist gives you something concrete to work with.

How to write a proof by contradiction

1. Assume the opposite of what you want to prove, and write it down clearly: "Assume, for contradiction, that ..."
2. Write the assumption as algebra, for example a fraction a/b or an equation with integers.
3. Follow logical steps until you reach a statement that contradicts your assumption or a known fact.
4. Say what the contradiction is and conclude: "This is a contradiction, so the assumption is false and the statement is true."

Writing the opposite correctly

Getting the opposite wrong is the most common way to lose marks. The opposite of "if A then B" is "A is true and B is false", not "if A then not B".

Proof that √2 is irrational

An irrational number can't be written as a fraction a/b of two integers. The proof uses one fact first.

Fact: if n² is even, then n is even

Assume, for contradiction, that n² is even but n is odd. Then n = 2k + 1 for some integer k, and n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd. This contradicts n² being even. So if n² is even, n is even.

The proof

1. Assume, for contradiction, that √2 is rational. Then √2 can be written as a fraction a/b of two whole numbers (b not zero), with the fraction in its simplest form, so a and b have no common factor except 1.
2. Square both sides: 2 = a²/b², so a² = 2b². This means a² is even, so a is even. Write a = 2c.
3. Substitute: (2c)² = 2b², so 4c² = 2b², and b² = 2c². So b² is even, which means b is even.
4. Now a and b are both even, so they have a common factor of 2. This contradicts the fraction being in its simplest form.
5. So the assumption is false, and √2 is irrational.

The same method proves that √3, √5 and √p for any prime p are irrational.

Proof that there are infinitely many primes

This proof is over two thousand years old and appears in Euclid's Elements.

1. Suppose the primes run out, so there is a complete, finite list of them: p₁, p₂, ..., pₙ.
2. Let N = p₁ × p₂ × ... × pₙ + 1.
3. N is greater than 1, so it has at least one prime factor. But dividing N by any prime in the list leaves a remainder of 1, so none of them is a factor of N.
4. So N has a prime factor that isn't in the list. This contradicts the list containing every prime.
5. So the assumption is false, and there are infinitely many primes.

Check your understanding.

More examples of proof by contradiction

Example 1: no smallest positive rational number

Assume, for contradiction, that there is a smallest positive rational number, q. Then q/2 is also rational, it is positive, and q/2 < q. So q is not the smallest, which is a contradiction. Therefore there is no smallest positive rational number.

Example 2: a difference of two squares

Prove that there are no positive integers a and b with a² − b² = 1.

Assume, for contradiction, that there are. Factorise: (a − b)(a + b) = 1. Both brackets are integers, and a + b is positive, so a − b is positive too, and the only way two positive integers multiply to 1 is 1 × 1. So a − b = 1 and a + b = 1. Adding these gives 2a = 2, so a = 1, and then b = 0. But b is a positive integer, which is a contradiction. So no such a and b exist.

Example 3: a parity argument

Prove that x² − y² = 2 has no integer solutions.

Assume, for contradiction, that integers x and y satisfy (x − y)(x + y) = 2. The two brackets differ by 2y, an even number, so they have the same parity. Two odd brackets multiply to an odd number, which cannot be 2. Two even brackets multiply to a multiple of 4, which cannot be 2 either. Either way there is a contradiction, so there are no integer solutions.

Proof by contradiction vs other methods of proof

AQA A-level Maths (A1) lists all four, and names the irrationality of √2 and the infinity of primes as proofs by contradiction you should know, along with applying the method to unfamiliar proofs.

Common mistakes

• Assuming the wrong opposite. The opposite of "irrational" is "rational", and the opposite of "infinitely many" is "finitely many".
• Forgetting "in its simplest form" in the √2 proof. Without it there is no contradiction at the end.
• Saying N is prime in the primes proof. N has a prime factor not in the list.
• Using the result you are proving partway through.
• Not stating the contradiction. Say exactly what clashes with what, then write the conclusion.

Practice questions

1. Write down the assumption you would start with to prove that log₂ 7 is irrational.
2. Prove by contradiction that √7 is irrational. (You may use the fact that when n² divides by 7, so does n.)
3. Prove by contradiction that there is no largest even number.
4. Prove that if n² is odd, then n is odd.

Answers: 1) Assume log₂ 7 is rational, so it equals a fraction a/b of two whole numbers with b not zero. 2) Assume √7 = a/b in simplest form; then a² = 7b², so 7 divides a, a = 7c; then 49c² = 7b², b² = 7c², so 7 divides b; a and b share the factor 7, a contradiction. 3) Assume there is a largest even number, N; then N + 2 is even and larger, a contradiction. 4) Assume n² is odd and n is even, n = 2k; then n² = 4k², which is even, a contradiction.

Practise with a short timed paper

Proof is the first topic in A-level Maths and comes up throughout the pure papers. The daily A-level Maths: Algebra & Functions paper is a short timed paper of 8 questions, with a new one every day.

Read next

Maths · AlgebraArithmetic series formula: Sₙ = n/2(2a + (n − 1)d), proofThe arithmetic series formula Sₙ = n/2[2a + (n − 1)d] and Sₙ = n/2(a + l): the proof, sigma notation, finding n, two-condition problems and examples.