All subjects · Mathematics · WMA14 (P4)

Proof by contradiction

In a proof by contradiction you assume the statement is false and show that this leads to something impossible. So the statement must be true.

The method

1. Assume the opposite (the negation) of what you want to prove.

2. Reason logically from that assumption.

3. Reach a contradiction: something that cannot be true.

4. Conclude that the assumption was false, so the original statement is true.

sqrt(2) is irrational

Assume sqrt(2) = a/b, where a and b are integers with no common factor. Then 2b2 = a2, so a2 is even and a is even. Write a = 2k: 2b2 = 4k2, so b2 = 2k2 and b is even. Now a and b share the factor 2: a contradiction.

Infinitely many primes

Assume there are finitely many primes p_1, p_2, ..., p_n. Let N = p_1 p_2 ... p_n + 1. Dividing N by any p_i leaves remainder 1, so N has a prime factor not in the list (or is prime itself). This contradicts the list being complete.

Worked example

Prove that there are no integers a and b with 21a + 14b = 1.

  1. Assume there are integers a and b with 21a + 14b = 1.
  2. 21a + 14b = 7(3a + 2b), and 3a + 2b is an integer, so the left side is a multiple of 7.
  3. 1 is not a multiple of 7: a contradiction.

Answer: So no such integers exist.

Key idea: Assume the negation, reason to an impossibility, then conclude the original statement is true.

Check yourself

  1. How should a proof by contradiction that sqrt(3) is irrational begin?
    • Assume sqrt(3) is irrational
    • Assume sqrt(3) = a/b, where a, b are integers with no common factor
    • Show that sqrt(3) = 1.732...
    • Assume a/b is irrational
    Show answer

    Assume sqrt(3) = a/b, where a, b are integers with no common factor. You assume the opposite of what you want to prove: that sqrt(3) is rational.

  2. What is the negation of 'there are infinitely many prime numbers'?
    • There are no prime numbers
    • Every number is prime
    • There are infinitely many composite numbers
    • There are finitely many prime numbers
    Show answer

    There are finitely many prime numbers. The opposite of infinitely many is finitely many.

  3. In the proof that sqrt(2) is irrational, you reach 2b2 = a2. What do you deduce next?
    • a is odd
    • a2 is even, so a is even
    • b is even, so a is odd
    • a = 2b
    Show answer

    a2 is even, so a is even. a2 equals 2 times an integer, so a2 is even. If a were odd, a2 would be odd, so a is even.

  4. In the proof that there are infinitely many primes, N = p_1 p_2 ... p_n + 1. What is the remainder when N is divided by any of p_1 to p_n?
    • 0
    • p_n
    • 1
    • N - 1
    Show answer

    1. N is one more than a multiple of each p_i.

  5. To prove 'if n2 is even then n is even' by contradiction, what do you assume?
    • n2 is even and n is odd
    • n2 is odd and n is even
    • n is even
    • n2 is odd
    Show answer

    n2 is even and n is odd. The statement is false only if n2 is even but n is not even.

  6. Using the first four primes, find N = 2 × 3 × 5 × 7 + 1.
    Show answer

    211. 2 × 3 × 5 × 7 = 210, so N = 211.

  7. 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30031 = 59 × 509. Does this break the proof that there are infinitely many primes?
    • No: 59 and 509 are primes that were not in the list
    • Yes: N should always be prime
    • Yes: 30031 is divisible by 13
    • No: 30031 is prime
    Show answer

    No: 59 and 509 are primes that were not in the list. The proof only needs N to have a prime factor not in the list. It does not claim N itself is prime.

Practise with instant feedback

Sources

Last updated 7 November 2026. Spotted a mistake? Tell us.