Proof by contradiction

Proof by contradiction Test

Spec A1 · AQA 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

AQA A-Level Maths

Proof by contradiction

Total 27 marks

Name

Class

Date

  1. 1
    A student wishes to prove by contradiction that 3\sqrt3 is irrational.
    (a)
    Which of these is the correct first line of the proof?
    [1 mark]
    • AAssume that 3\sqrt3 is irrational.
    • BAssume that 3=pq\sqrt3=\frac{p}{q}, where pp and qq are integers with q≠0q\neq0 and no common factor greater than 11.
    • CAssume that 3\sqrt3 is an integer.
    • DAssume that 3=pq\sqrt3=\frac{p}{q}, where pp and qq are both multiples of 33.
    Show the mark scheme

    Mark scheme

    Answer: B
    (b)
    Squaring 3=pq\sqrt3=\frac{p}{q} gives p2=3q2p^2=3q^2. What can be deduced about pp?
    [1 mark]
    • App is a multiple of 33.
    • Bqq is a multiple of 33.
    • Cpp is even.
    • Dp=3p=3.
    Show the mark scheme

    Mark scheme

    Answer: A
    (c)
    Given that p2=3q2p^2=3q^2 and pp is a multiple of 33, complete the proof that 3\sqrt3 is irrational.
    [2 marks]
    Show the mark scheme

    Mark scheme

    M1: p=3kp=3k, so 9k2=3q29k^2=3q^2 and q2=3k2q^2=3k^2
    R1:
    q2q^2 is a multiple of 33, so qq is a multiple of 33; both pp and qq have a factor 33, contradicting 'no common factor', so 3\sqrt3 is irrational

    Total for question 1: 4 marks

  2. 2
    Claim: there are no positive integers aa and bb such that a2−b2=1a^2-b^2=1.
    (a)
    Which is the correct first line of a proof by contradiction of the claim?
    [1 mark]
    • AAssume that a2−b2≠1a^2-b^2\neq1 for all positive integers aa and bb.
    • BAssume that a=b+1a=b+1.
    • CAssume that aa and bb are both even.
    • DAssume that there exist positive integers aa and bb such that a2−b2=1a^2-b^2=1.
    Show the mark scheme

    Mark scheme

    Answer: D
    (b)
    Given that (a−b)(a+b)=1(a-b)(a+b)=1 with aa and bb positive integers, which statement must be true?
    [1 mark]
    • Aa−b=−1a-b=-1 and a+b=−1a+b=-1
    • Ba−b=2a-b=2 and a+b=12a+b=\frac12
    • Ca−b=1a-b=1 and a+b=1a+b=1
    • Da−b=0a-b=0 and a+b=1a+b=1
    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: a−b=1a-b=1 and a+b=1a+b=1 (both factors are positive integers with product 11), so 2a=22a=2 and b=0b=0
    R1:
    b=0b=0 is not positive, a contradiction, so no such positive integers exist

    Total for question 2: 4 marks

  3. 3
    Euclid's proof that there are infinitely many prime numbers begins by assuming that there are only finitely many, say p1,p2,…,pnp_1,p_2,\ldots,p_n, and then considers the number N=p1p2⋯pn+1N=p_1p_2\cdots p_n+1.
    (a)
    Show that NN leaves remainder 11 when divided by each of p1,p2,…,pnp_1,p_2,\ldots,p_n, and state what this means for the divisibility of NN.
    [3 marks]
    Show the mark scheme

    Mark scheme

    M1: N=pi×(product of the other primes)+1N=p_i\times(\text{product of the other primes})+1
    A1: so remainder
    11 when divided by any pip_i
    R1: so none of
    p1,…,pnp_1,\ldots,p_n divides NN (as 1≠01\neq0)
    AG
    (b)
    Hence complete the proof by contradiction that there are infinitely many primes.
    [4 marks]
    Show the mark scheme

    Mark scheme

    B1: N>1N>1, so NN is either prime or has a prime factor
    M1: this prime is not in the list
    p1,…,pnp_1,\ldots,p_n, since none of them divides NN (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 primes

    Total for question 3: 7 marks

  4. 4
    In this question a rational number is one that can be written as ab\frac{a}{b} where aa and bb are integers and b≠0b\neq0; any other real number is irrational. You may quote that 2\sqrt2 is irrational.
    (a)
    Prove by contradiction that log⁡23\log_2 3 is irrational.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: assumes log⁡23=pq\log_23=\frac{p}{q} with pp, qq positive integers (positive as log⁡23>0\log_23>0)
    A1:
    3=2p/q3=2^{p/q}, so 3q=2p3^q=2^p
    A1:
    3q3^q is odd
    A1:
    2p2^p is even, since p≥1p\geq1
    R1: an odd number cannot equal an even number, a contradiction

    R1: so
    log⁡23\log_23 is irrational
    (b)
    Prove by contradiction that 3+223+2\sqrt2 is irrational.
    [6 marks]
    Show the mark scheme

    Mark scheme

    M1: assumes 3+22=ab3+2\sqrt2=\frac{a}{b} with aa, bb integers, b≠0b\neq0
    M1: rearranges to
    22=ab−32\sqrt2=\frac{a}{b}-3
    A1:
    2=a−3b2b\sqrt2=\frac{a-3b}{2b}
    R1:
    a−3ba-3b and 2b2b are integers with 2b≠02b\neq0, so 2\sqrt2 would be rational
    R1: this contradicts the fact that
    2\sqrt2 is irrational
    R1: so the assumption is false and
    3+223+2\sqrt2 is irrational

    Total for question 4: 12 marks

End of questions

Subtopic tests