A-level · Proof

Proof by exhaustionExam-style questions

Proving a statement by splitting it into a finite, complete set of cases and checking every one — either a short list of values, or all integers split by parity or remainder. Why the cases must leave no gaps, and why exhaustion only works when the cases really are finite.

Start practising Read the lesson

6 questions · A-level level · mark scheme and worked solution on each · no sign-up to try

DifficultyAllLevel 2Level 3Level 4
  1. 1
    The positive integers aa and bb satisfy

    a<bandab=30a < b \qquad \text{and} \qquad ab = 30

    Prove, by exhaustion, that a+ba + b is always a prime number.

    The table below may be used to set out your cases. You do not have to fill every row.
    aabba+ba + b
    (3 marks)
    Level 2 · 3 marksTry it
  2. 2
    Ayesha is using proof by exhaustion to show that, for every integer nn,

    2n3+n2n^3 + n

    is a multiple of 3

    Her proof so far is shown in the box below.
    Ayesha's proof
    Every integer nn can be written in one of the forms 3k3k, 3k+13k + 1 or 3k+23k + 2, where kk is an integer.
    When n=3k+1n = 3k + 1: 2n3+n=2(27k3+27k2+9k+1)+3k+1=54k3+54k2+21k+3=3(18k3+18k2+7k+1)2n^3 + n = 2(27k^3 + 27k^2 + 9k + 1) + 3k + 1 = 54k^3 + 54k^2 + 21k + 3 = 3(18k^3 + 18k^2 + 7k + 1), which is a multiple of 3
    Complete Ayesha's proof.

    (4 marks)
    Level 3 · 4 marksTry it
  3. 3
    In this question you must show detailed reasoning.

    The integer mm is not a multiple of 3

    Prove by exhaustion, using algebra, that

    2m2+12m^2 + 1

    is a multiple of 3

    (4 marks)
    Level 3 · 4 marksTry it
  4. 4
    Prove that n5−nn^5 - n is divisible by 55 for every integer nn, by exhausting the possible remainders of nn on division by 55.
    Level 3 · 4 marksTry it
  5. 5
    (a) By writing nn in terms of its remainder on division by 33, prove that, for every integer nn, the remainder when n3n^3 is divided by 99 is 00, 11 or 88.

    (4 marks)
    (b) The integers xx, yy and zz are each chosen at random from the set {1,2,3,…,90}\{1, 2, 3, \ldots, 90\}, independently of one another.

    Determine the probability that x3+y3+z3x^3 + y^3 + z^3 is divisible by 99.

    (4 marks)
    Level 4 · 8 marksTry it

1 more question on proof by exhaustion

Free with an account — just an email, no card. The whole bank, every mark scheme and worked solution.

Start free