How does a proof by contradiction finish?

Show the assumption leads to an impossible result, so the assumption is false and the original statement is true.

Negation of 'there are no solutions'?

There is at least one solution.

Definition of a rational number?

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

How do you start a proof that \sqrt2 is irrational?

Assume \sqrt2=\frac{p}{q} with p, q integers having no common factor.

Why does p^2=2q^2 make p even?

p^2 is even, and the square of an odd number is odd, so p must be even.

What is the contradiction in the proof for \sqrt2?

Both p and q are even, so they have a common factor 2, contradicting lowest terms.

Why does p^2=3q^2 give p a multiple of 3?

3 is prime and divides p^2, so it divides p.

Is N in Euclid's proof always prime?

No: it is prime or has a prime factor not in the list.

How can you prove \log23 irrational?

Assume \log23=\frac{p}{q}; then 3^q=2^p, an odd number equal to an even number.

Why must the final line state the conclusion?

The proof is only complete once you say the assumption is false, so the original statement is true.

Proof by contradictionAQA A-Level Maths: Flashcards

Card 1 of 130 of 13 known

Question

What do you assume at the start of a proof by contradiction?

Tap or press Space to reveal

Tap card or press Space to flip

See all 13 cards

What do you assume at the start of a proof by contradiction?: The negation of the statement to be proved.
How does a proof by contradiction finish?: Show the assumption leads to an impossible result, so the assumption is false and the original statement is true.
Negation of 'there are no solutions'?: There is at least one solution.
Definition of a rational number?: A number that can be written as $\frac{p}{q}$ with $p$ , $q$ integers and $q\neq0$ .
How do you start a proof that $\sqrt2$ is irrational?: Assume $\sqrt2=\frac{p}{q}$ with $p$ , $q$ integers having no common factor.
Why does $p^2=2q^2$ make $p$ even?: $p^2$ is even, and the square of an odd number is odd, so $p$ must be even.
What is the contradiction in the proof for $\sqrt2$ ?: Both $p$ and $q$ are even, so they have a common factor 2, contradicting lowest terms.
Why does $p^2=3q^2$ give $p$ a multiple of 3?: $3$ is prime and divides $p^2$ , so it divides $p$ .
State Euclid's number.: $N=p_1p_2\cdots p_n+1$
What remainder does $N$ leave on division by each $p_i$ ?: Remainder 1.
Is $N$ in Euclid's proof always prime?: No: it is prime or has a prime factor not in the list.
How can you prove $\log_23$ irrational?: Assume $\log_23=\frac{p}{q}$ ; then $3^q=2^p$ , an odd number equal to an even number.
Why must the final line state the conclusion?: The proof is only complete once you say the assumption is false, so the original statement is true.

Exam questions on Proof by contradiction

A student wishes to prove by contradiction that $\sqrt3$ is irrational.
Given that $p^2=3q^2$ and $p$ is a multiple of $3$ , complete the proof that $\sqrt3$ is irrational.2 marks
Claim: there are no positive integers $a$ and $b$ such that $a^2-b^2=1$ .
Complete the proof that no such integers exist.2 marks
Euclid's proof that there are infinitely many prime numbers begins by assuming that there are only finitely many, say $p_1,p_2,\ldots,p_n$ , and then considers the number $N=p_1p_2\cdots p_n+1$ .
Show that $N$ leaves remainder $1$ when divided by each of $p_1,p_2,\ldots,p_n$ , and state what this means for the divisibility of $N$ .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).