Edexcel International A Level Maths
Proof by contradiction
Total 27 marks
Name
Class
Date
- 1A student begins a proof by contradiction that is irrational.(a)Which assumption should the proof begin with?[1 mark]
- A is irrational
- B, where and are integers with no common factor other than 1 and
- C is an integer
- D, where and are both even
Show the mark scheme
Mark scheme
Answer: B(b)The assumption leads to . Which deduction follows directly?[1 mark]- A is a prime number
- B is even and is odd
- C and are both odd
- D is even, so is even
Show the mark scheme
Mark scheme
Answer: D(c)Given that and so is even, complete the proof.[2 marks]Show the mark scheme
Mark scheme
M1: , so and , so is even
A1: and both even contradicts 'no common factor', so is irrationalTotal for question 1: 4 marks
- 2Euclid's proof that there are infinitely many primes begins by assuming that there are only finitely many primes, . Let .(a)What is the remainder when is divided by any one of the primes ?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: A(b)Which conclusion completes the argument?[1 mark]- A must itself be prime
- B is divisible by every
- C has a prime factor that is not in the list, contradicting the assumption that the list contains every prime
- D
Show the mark scheme
Mark scheme
Answer: C(c)A student takes the first six primes, , so . Show that is not prime, and state what this shows about Euclid's argument.[2 marks]Show the mark scheme
Mark scheme
M1:
A1: need not be prime; the argument only needs a prime factor not in the list ( and are not among )Total for question 2: 4 marks
- 3In a proof by contradiction you assume that the statement is false and show that this leads to an impossible result.(a)Prove by contradiction that there are no integers and such that .[3 marks]
Show the mark scheme
Mark scheme
B1: assumes that integers and exist with
M1:
R1: is an integer, so the left-hand side is a multiple of 7 but 1 is not (or , not an integer): contradiction(b)Prove by contradiction that is irrational.[4 marks]Show the mark scheme
Mark scheme
B1: assumes with , positive integers
M1: , so
A1: is even but is odd
R1: contradiction, so is irrationalTotal for question 3: 7 marks
- 4Use proof by contradiction in each part. You may use the fact that is irrational.(a)Prove that is irrational.[6 marks]
Show the mark scheme
Mark scheme
B1: assumes , where is rational and
M1: , then squares both sides
A1: , so
M1:
A1: this is rational (a ratio of rationals, )
R1: contradicts the fact that is irrational, so is irrational(b)Prove that the equation has no solutions in which and are both integers.[6 marks]Show the mark scheme
Mark scheme
B1: assumes integers and exist with
M1:
M1: and have the same parity, because their difference is even
A1: the product is even, so both factors are even
A1: the product is then a multiple of 4, e.g.
R1: 2 is not a multiple of 4: contradiction, so there are no integer solutionsTotal for question 4: 12 marks
End of questions