Class 9 Mathematics · chapter 15: Proofs in Mathematics · lesson 44 of 44

Proof by contradiction

About 40 minutes

Why this matters

Proof by contradiction is the method behind the famous result that √2 is irrational, a proof asked in the Class 9 and Class 10 papers for four marks, and behind "there are infinitely many primes". The exam also asks one-mark questions on what the first step of such a proof is. Learning the shape once gives you all of these proofs together.

The idea

Proof by contradiction is a method of proof in which we assume that the statement to be proved is false, reason correctly from that assumption, and arrive at something impossible; since correct reasoning cannot lead from a true assumption to an impossibility, the assumption must be false, and so the original statement is true.

The method has a fixed shape.

  1. State clearly what is to be proved.
  2. Assume the opposite (the negation).
  3. Reason step by step, using axioms, definitions and known theorems.
  4. Reach a contradiction: a statement that conflicts with the assumption, with a known fact, or with itself.
  5. Conclude that the assumption was wrong, so the original statement holds.

Two facts are used inside the standard proofs. A rational number is a number that can be written as p/q with p and q integers and q ≠ 0, and every rational number can be written with p and q having no common factor other than 1. Also, if the square of an integer is even, then the integer itself is even; this follows because the square of an odd number is odd (proved in the previous lesson).

Statement to proveAssumption madeContradiction reached
√2 is irrational√2 = p/q in lowest termsp and q both even
Infinitely many primesonly finitely many primesa new prime not in the list
rational + irrational is irrationalthe sum is rationalthe irrational number is rational

Proof by contradiction is different from disproving by counterexample. A counterexample shows a general statement is false; contradiction shows a statement is true by ruling out its opposite.

Worked examples

Example 1: √2 is irrational

Question: Prove that √2 is an irrational number.

  1. Assume the opposite: √2 is rational, so √2 = p/q where p and q are integers with no common factor and q ≠ 0.
  2. Squaring, 2 = p²/q², so p² = 2q². Hence p² is even, and therefore p is even. Write p = 2m.
  3. Then (2m)² = 2q², so 4m² = 2q², giving q² = 2m². Hence q² is even, so q is even.
  4. Now p and q are both even, so they have the common factor 2. This contradicts the choice of p and q with no common factor.
  5. The assumption was wrong.

Answer: √2 is irrational.

Example 2: Sum of a rational and an irrational number

Question: Prove that if a is rational and b is irrational, then a + b is irrational.

  1. Assume a + b is rational, say a + b = r with r rational.
  2. Then b = r − a.
  3. The difference of two rational numbers is rational, so b is rational.
  4. This contradicts the given fact that b is irrational.

Answer: a + b is irrational. (For example 3 + √2 is irrational.)

Example 3: Infinitely many primes

Question: Prove that there is no largest prime number.

  1. Assume there is a largest prime, so the primes form a finite list p₁, p₂, ..., pₙ.
  2. Form N = p₁ × p₂ × ... × pₙ + 1.
  3. Dividing N by any prime in the list leaves remainder 1, so no prime in the list divides N.
  4. But every integer greater than 1 has at least one prime factor, so N has a prime factor that is not in the list.
  5. This contradicts the assumption that the list contained every prime.

Answer: There is no largest prime; the primes are infinite in number.

Common mistakes

  • Assuming the statement itself instead of its negation. The proof of √2 begins with "suppose √2 is rational", not "suppose √2 is irrational".
  • Forgetting the "no common factor" condition. Without it, finding that p and q are both even is not a contradiction.
  • Jumping from "p² is even" to "p is even" without a reason. Say: because the square of an odd number is odd.
  • Ending without stating the conclusion. Finish with "hence our assumption is false, so √2 is irrational".

Try it yourself

  1. Outline the proof that √3 is irrational.
  2. Prove by contradiction that if n² is odd, then n is odd.
  3. What is the first step of every proof by contradiction?

Answers: 1. Assume √3 = p/q in lowest terms; then p² = 3q², so 3 divides p, write p = 3m, then 3q² = 9m², so q² = 3m² and 3 divides q, contradicting lowest terms. 2. Assume n is even, n = 2m; then n² = 4m² = 2(2m²) is even, contradicting that n² is odd; so n is odd. 3. Assume that the statement to be proved is false.

Quiz

Five questions built from this lesson. Start at Core; the level adapts to your score.

Flashcards

Turn the key terms of this lesson into cards that come back just before you forget them.