Proof by Contradiction

"...when you have eliminated the impossible, whatever remains, however improbable, must be the truth?" Sherlock Holmes in The Sign of the Four by Sir Arthur Conan Doyle. Holmes was a wonderful detective and he would also have been excellent at carrying out proofs by contradiction, as this is exactly the process we use. To complete a proof by contradiction, we start by assuming the opposite is true. If we show that the consequences of this are impossible, our original statement must be true. This is a challenging topic in the course. The page will prepare you well.


Key Concepts

On this page, you should learn to

  • Carry out proof by contradiction to show irrationality of roots, like \(\sqrt{3}\)
  • Carry out proof by contradiction to show that there are an infinite number of primes

Summary

Print from here

Test Yourself

Here is a quiz to prove that if the square of a positive integer is odd, the number is odd

1

Prove that if the square of a positive integer, n² is odd, then the number n is odd

This is a contradiction n² = 2(2k²) n = 2k, where k is an integer Hence, if n² is odd, then the number n is odd n² is even n is even n² = 4k²

Let n be a positive integer, where n² is odd

Assume the opposite, that

\(\implies\)

\(\implies\)

\(\implies\)

\(\implies\)

You could carry out this proof using a deductive proof, but if the exam question asks you to do a proof by contradiction, then you must do a proof by contradiction!



Here is a quiz to prove that \(\sqrt{5}\) is irrational

1

Complete the following to prove that \(\sqrt {5}\) is irrational

a is divisible by 5 a is divisible by 5 This is a contradiction 5b² = a² a² is divisible by 5 5b² = (5n)² b² = 5n² b is divisible by 5 a and b are divisible by 5

Assume that \(\sqrt {5}\) is rational

\(\sqrt {5}=\frac{a}{b}\quad a,b\in\mathbb{Z}, b\neq0\)

\(\implies\) \(5=\frac {a²}{b²}\)

\(\implies\)

\(\implies\)

\(\implies\)

\(\implies\) a = 5n

Substitute this in 5b² = a²

\(\implies\)

\(\implies\) 5b² = 25n²

\(\implies\)

\(\implies\) b² is divisible by 5

\(\implies\)

This means that both

\(\implies \frac{a}{b}\) has a common factor of 5

\(\implies \sqrt {5}\) is irrational

There are other ways to prove that \(\sqrt{5}\) is irrational, buut this technique is one that you can use for other roots of prime numbers. This quiz is something you can practise several times!



Here is a quiz to prove that there are infinitely many primes

1

Complete the following to prove that there are an infinite number of primes

be divided by p2, or p3, ... or pn

there are an infinite number of primes

(p1 x p2 x p3 x ...x pn) + 1

This is a contradiction that p1 , p2 , p3, ..., pn contains all the primes

p1 , p2 , p3, ..., pn

another prime or divisible by another prime not in our list of primes

by p1 (it leaves a remainder of 1)

finite number of primes

Assume that there are a

We can list all the primes:

Let N =

N cannot be divided

N cannot

N must be

\(\implies\)

Hence,

This is Euclid's classic proof. You should learn how to do this by heart.


Exam-style Questions

Question 1

Prove by contradiction that, if n² is even, then n is even

Hint

Full Solution

 

Question 2

a) Use a deductive proof to prove that even x even = even

b) Similarly prove that odd x odd = odd

c) Hence, use proof by contradiction to prove that \(log_25\) is irrational

Hint

Full Solution

Question 3

Prove by contradiction that a rational number + an irrational number = irrational number.

Hint

Full Solution

 

Question 4

Prove that \(\sqrt{3}\) is irrational

Hint

Full Solution

 

Alternate Solution

 

Question 5

Prove that \(\sqrt[3]{5}\) is irrational

Hint

Full Solution

 

Question 6

Prove by contradiction that the length of the hypotenuse of a right-angled triangle is less than the sum of the other two sides.

Hint

Full Solution

Question 7

Prove that \(\sqrt[n]{p}\) is irrational, given that p is prime.

Hint

Full Solution

Question 8

Prove by contradiction that there are no rational roots to the equation \(x^3+x+1=0\)

Hint

Full Solution

 

MY PROGRESS

How much of Proof by Contradiction have you understood?