What must you do first in a contradiction proof?

State the assumption: the opposite of what you want to prove.

Define a rational number.

A number that can be written as \frac{a}{b} with a,b integers and b\neq0.

Why assume \frac{a}{b} is in lowest terms?

So that 'a and b both have a factor 2' is a genuine contradiction.

If a^2 is even, what follows?

a is even, since the square of an odd number is odd.

Start of the proof that \sqrt2 is irrational?

Assume \sqrt2=\frac{a}{b} in lowest terms, so a^2=2b^2.

What contradiction arises for \sqrt2?

a and b are both even, contradicting lowest terms.

If a^2 is a multiple of 3, what follows?

a is a multiple of 3, as (3k\pm1)^2 is never a multiple of 3.

Why does N give a contradiction?

N is prime or has a prime factor, and in each case that prime is not in the list.

State the opposite of 'there are infinitely many primes'.

There are finitely many primes.

What are typical contradictions?

Even equals odd; fraction not in lowest terms; a multiple of 5 equals 1.

Is N always prime in Euclid's proof?

No. 2\times3\times5\times7\times11\times13+1=59\times509.

Proof by contradictionEdexcel A-Level Maths: Flashcards

Card 1 of 140 of 14 known

Question

What is proof by contradiction?

Tap or press Space to reveal

Tap card or press Space to flip

See all 14 cards

What is proof by contradiction?: Assume the statement is false, then show this leads to something impossible, so the statement must be true.
What must you do first in a contradiction proof?: State the assumption: the opposite of what you want to prove.
Define a rational number.: A number that can be written as $\frac{a}{b}$ with $a,b$ integers and $b\neq0$ .
Why assume $\frac{a}{b}$ is in lowest terms?: So that 'a and b both have a factor 2' is a genuine contradiction.
If $a^2$ is even, what follows?: $a$ is even, since the square of an odd number is odd.
Start of the proof that $\sqrt2$ is irrational?: Assume $\sqrt2=\frac{a}{b}$ in lowest terms, so $a^2=2b^2$ .
What contradiction arises for $\sqrt2$ ?: $a$ and $b$ are both even, contradicting lowest terms.
If $a^2$ is a multiple of 3, what follows?: $a$ is a multiple of 3, as $(3k\pm1)^2$ is never a multiple of 3.
Define $N$ in the proof of infinitely many primes.: $N=p_1p_2\cdots p_n+1$ .
What is the remainder when $N$ is divided by any listed prime?: 1
Why does $N$ give a contradiction?: $N$ is prime or has a prime factor, and in each case that prime is not in the list.
State the opposite of 'there are infinitely many primes'.: There are finitely many primes.
What are typical contradictions?: Even equals odd; fraction not in lowest terms; a multiple of 5 equals 1.
Is $N$ always prime in Euclid's proof?: No. $2\times3\times5\times7\times11\times13+1=59\times509$ .

Exam questions on Proof by contradiction

A student begins a proof that $\sqrt{2}$ is irrational by assuming that $\sqrt{2}=\frac{a}{b}$ , where $a$ and $b$ are integers and $b\neq0$ .
Given that $a^2=2b^2$ and that $a$ is even, complete the proof that $\sqrt{2}$ is irrational.2 marks
Euclid's proof that there are infinitely many primes begins by assuming that there is a finite number of primes, $p_1,p_2,\ldots,p_n$ , and then considers $N=p_1p_2\cdots p_n+1$ .
Complete the proof that there are infinitely many primes.2 marks
Assume, for a contradiction, that $\log_2 3=\frac{p}{q}$ , where $p$ and $q$ are positive integers.
Show that $3^q=2^p$ .3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).