Proof by contradiction

Proof by contradiction Test

Spec 1.1 · Edexcel International A Level Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

Edexcel International A Level Maths

Proof by contradiction

Total 27 marks

Name

Class

Date

  1. 1
    A student begins a proof by contradiction that 2\sqrt2 is irrational.
    (a)
    Which assumption should the proof begin with?
    [1 mark]
    • A2\sqrt2 is irrational
    • B2=pq\sqrt2=\frac{p}{q}, where pp and qq are integers with no common factor other than 1 and q≠0q\neq0
    • C2\sqrt2 is an integer
    • D2=pq\sqrt2=\frac{p}{q}, where pp and qq are both even
    Show the mark scheme

    Mark scheme

    Answer: B
    (b)
    The assumption leads to p2=2q2p^2=2q^2. Which deduction follows directly?
    [1 mark]
    • App is a prime number
    • Bqq is even and pp is odd
    • Cpp and qq are both odd
    • Dp2p^2 is even, so pp is even
    Show the mark scheme

    Mark scheme

    Answer: D
    (c)
    Given that p2=2q2p^2=2q^2 and so pp is even, complete the proof.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: p=2kp=2k, so 4k2=2q24k^2=2q^2 and q2=2k2q^2=2k^2, so qq is even
    A1:
    pp and qq both even contradicts 'no common factor', so 2\sqrt2 is irrational

    Total for question 1: 4 marks

  2. 2
    Euclid's proof that there are infinitely many primes begins by assuming that there are only finitely many primes, p1,p2,…,pnp_1,p_2,\ldots,p_n. Let N=p1p2⋯pn+1N=p_1p_2\cdots p_n+1.
    (a)
    What is the remainder when NN is divided by any one of the primes pip_i?
    [1 mark]
    • A11
    • B00
    • Cpip_i
    • D22
    Show the mark scheme

    Mark scheme

    Answer: A
    (b)
    Which conclusion completes the argument?
    [1 mark]
    • ANN must itself be prime
    • BNN is divisible by every pip_i
    • CNN has a prime factor that is not in the list, contradicting the assumption that the list contains every prime
    • DN=1N=1
    Show the mark scheme

    Mark scheme

    Answer: C
    (c)
    A student takes the first six primes, 2,3,5,7,11,132,3,5,7,11,13, so N=30031N=30031. Show that NN is not prime, and state what this shows about Euclid's argument.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: 30031=59×50930031=59\times509
    A1:
    NN need not be prime; the argument only needs a prime factor not in the list (5959 and 509509 are not among 2,…,132,\ldots,13)

    Total for question 2: 4 marks

  3. 3
    In 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 mm and nn such that 14m+21n=114m+21n=1.
    [3 marks]
    Show the mark scheme

    Mark scheme

    B1: assumes that integers mm and nn exist with 14m+21n=114m+21n=1
    M1:
    7(2m+3n)=17(2m+3n)=1
    R1:
    2m+3n2m+3n is an integer, so the left-hand side is a multiple of 7 but 1 is not (or 2m+3n=172m+3n=\frac17, not an integer): contradiction
    (b)
    Prove by contradiction that log⁡23\log_23 is irrational.
    [4 marks]
    Show the mark scheme

    Mark scheme

    B1: assumes log⁡23=pq\log_23=\frac{p}{q} with pp, qq positive integers
    M1:
    2p/q=32^{p/q}=3, so 2p=3q2^p=3^q
    A1:
    2p2^p is even but 3q3^q is odd
    R1: contradiction, so
    log⁡23\log_23 is irrational

    Total for question 3: 7 marks

  4. 4
    Use proof by contradiction in each part. You may use the fact that 2\sqrt2 is irrational.
    (a)
    Prove that 2+3\sqrt2+\sqrt3 is irrational.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: assumes 2+3=r\sqrt2+\sqrt3=r, where rr is rational and r>0r>0
    M1:
    3=r−2\sqrt3=r-\sqrt2, then squares both sides
    A1:
    3=r2−2r2+23=r^2-2r\sqrt2+2, so 2r2=r2−12r\sqrt2=r^2-1
    M1:
    2=r2−12r\sqrt2=\frac{r^2-1}{2r}
    A1: this is rational (a ratio of rationals,
    r≠0r\neq0)
    R1: contradicts the fact that
    2\sqrt2 is irrational, so 2+3\sqrt2+\sqrt3 is irrational
    (b)
    Prove that the equation x2−y2=2x^2-y^2=2 has no solutions in which xx and yy are both integers.
    [6 marks]
    Show the mark scheme

    Mark scheme

    B1: assumes integers xx and yy exist with x2−y2=2x^2-y^2=2
    M1:
    (x−y)(x+y)=2(x-y)(x+y)=2
    M1:
    x−yx-y and x+yx+y have the same parity, because their difference 2y2y is even
    A1: the product is even, so both factors are even

    A1: the product is then a multiple of 4, e.g.
    (2a)(2b)=4ab(2a)(2b)=4ab
    R1: 2 is not a multiple of 4: contradiction, so there are no integer solutions

    Total for question 4: 12 marks

End of questions

Subtopic tests