AQA A-Level Maths
Proof by contradiction
Total 27 marks
Name
Class
Date
- 1A student wishes to prove by contradiction that is irrational.(a)Which of these is the correct first line of the proof?[1 mark]
- AAssume that is irrational.
- BAssume that , where and are integers with and no common factor greater than .
- CAssume that is an integer.
- DAssume that , where and are both multiples of .
Show the mark scheme
Mark scheme
Answer: B(b)Squaring gives . What can be deduced about ?[1 mark]- A is a multiple of .
- B is a multiple of .
- C is even.
- D.
Show the mark scheme
Mark scheme
Answer: A(c)Given that and is a multiple of , complete the proof that is irrational.[2 marks]Show the mark scheme
Mark scheme
M1: , so and
R1: is a multiple of , so is a multiple of ; both and have a factor , contradicting 'no common factor', so is irrationalTotal for question 1: 4 marks
- 2Claim: there are no positive integers and such that .(a)Which is the correct first line of a proof by contradiction of the claim?[1 mark]
- AAssume that for all positive integers and .
- BAssume that .
- CAssume that and are both even.
- DAssume that there exist positive integers and such that .
Show the mark scheme
Mark scheme
Answer: D(b)Given that with and positive integers, which statement must be true?[1 mark]- A and
- B and
- C and
- D and
Show the mark scheme
Mark scheme
Answer: C(c)Complete the proof that no such integers exist.[2 marks]Show the mark scheme
Mark scheme
M1: and (both factors are positive integers with product ), so and
R1: is not positive, a contradiction, so no such positive integers existTotal for question 2: 4 marks
- 3Euclid's proof that there are infinitely many prime numbers begins by assuming that there are only finitely many, say , and then considers the number .(a)Show that leaves remainder when divided by each of , and state what this means for the divisibility of .[3 marks]
Show the mark scheme
Mark scheme
M1:
A1: so remainder when divided by any
R1: so none of divides (as )
AG(b)Hence complete the proof by contradiction that there are infinitely many primes.[4 marks]Show the mark scheme
Mark scheme
B1: , so is either prime or has a prime factor
M1: this prime is not in the list , since none of them divides (part (a))
R1: this contradicts the assumption that the list contains all the primes
R1: so the assumption is false and there are infinitely many primesTotal for question 3: 7 marks
- 4In this question a rational number is one that can be written as where and are integers and ; any other real number is irrational. You may quote that is irrational.(a)Prove by contradiction that is irrational.[6 marks]
Show the mark scheme
Mark scheme
M1: assumes with , positive integers (positive as )
A1: , so
A1: is odd
A1: is even, since
R1: an odd number cannot equal an even number, a contradiction
R1: so is irrational(b)Prove by contradiction that is irrational.[6 marks]Show the mark scheme
Mark scheme
M1: assumes with , integers,
M1: rearranges to
A1:
R1: and are integers with , so would be rational
R1: this contradicts the fact that is irrational
R1: so the assumption is false and is irrationalTotal for question 4: 12 marks
End of questions