Proof (deduction, exhaustion, counter-example, contradiction) – A-level Maths exam questions with mark scheme

1StandardCalculator5 marks

(a) Prove that, for all integers $n$ that are not multiples of 3, $n^{2}-1$ is a multiple of 3. [3]

(b) Show, by means of a counter-example, that the statement

'$n^{2}+n+41$ is prime for all positive integers $n$'

is not true. [2]

(a) for writing $n=3k+1$ and $n=3k+2$ (or $3k-1$) and expanding $n^{2}-1$ in at least one case. Alternative: $n^2-1=(n-1)(n+1)$ and $n-1,\ n,\ n+1$ are three consecutive integers, so one is a multiple of 3M1
(a) $(3k+1)^{2}-1=9k^{2}+6k=3(3k^{2}+2k)$, a multiple of 3 (alt: $n$ is not a multiple of 3, so $n-1$ or $n+1$ is)A1
(a) $(3k+2)^{2}-1=9k^{2}+12k+3=3(3k^{2}+4k+1)$, a multiple of 3, with conclusion covering all cases (alt: hence $(n-1)(n+1)=n^2-1$ is a multiple of 3, with conclusion)A1
(b) for substituting a suitable value, e.g. $n=40$ or $n=41$M1
(b) e.g. $n=40$: $1681=41^{2}$ (or $n=41$: $41\times43$), not prime, so statement is falseA1
Answer: (a) both cases give $3\times$ integer (b) e.g. $n=40$ gives $41^{2}$
Examiner tip: Proof by exhaustion must cover every case and end with a conclusion; testing a few numbers is not a proof.

2StandardCalculator4 marks

Prove by contradiction that $\sqrt3$ is irrational.

[You may assume that if $n^{2}$ is a multiple of 3 then $n$ is a multiple of 3.] [4]

Assumes $\sqrt3$ is rational: $\sqrt3=\dfrac{a}{b}$ where $a,b$ are integers with no common factors ($b\neq0$) (allow 'in its simplest form', 'in lowest terms' or 'HCF$(a,b)=1$')B1
Squares and rearranges: $a^{2}=3b^{2}$, so $a^{2}$ is a multiple of 3 and hence $a$ is a multiple of 3M1
Writes $a=3k$: $9k^{2}=3b^{2}\Rightarrow b^{2}=3k^{2}$, so $b$ is also a multiple of 3M1
States that $a$ and $b$ have a common factor 3, contradicting the assumption, so $\sqrt3$ is irrationalA1
Answer: Proof as in mark scheme
Examiner tip: State 'no common factors' in your assumption – without it there is nothing to contradict.

3HardCalculator5 marks

Prove by contradiction that there are infinitely many prime numbers. [5]

Assumes there are finitely many primes and lists them all: $p_{1},p_{2},\ldots,p_{n}$B1
Considers $N=p_{1}p_{2}\cdots p_{n}+1$M1
States that $N$ leaves remainder 1 when divided by each of $p_{1},\ldots,p_{n}$, so none of them is a factor of $N$M1
Deduces that $N$ is either prime itself (and, being larger than every $p_i$, not in the list) or has a prime factor not in the list (allow: $N>1$ so has a prime factor, but no $p_i$ divides $N$)A1
Contradiction with the list containing all primes, so there are infinitely many primesA1
Answer: Proof as in mark scheme
Examiner tip: $N$ need not itself be prime (e.g. $2\cdot3\cdot5\cdot7\cdot11\cdot13+1=30031=59\times509$) – say 'prime or has a new prime factor'.

Stuck on Proof (deduction, exhaustion, counter-example, contradiction)?

We work through your weakest questions on this topic on Zoom. I reply the same day.

4CoreCalculator3 marks

Prove by contradiction that there are no integers $a$ and $b$ such that $$6a+9b=1$$ [3]

Assumes there exist integers $a$ and $b$ with $6a+9b=1$B1
Factorises: $3(2a+3b)=1\Rightarrow 2a+3b=\tfrac13$ (or states that $6a+9b=3(2a+3b)$ is a multiple of 3)M1
$2a+3b$ is an integer but $\tfrac13$ is not (or: 1 is not a multiple of 3) – contradiction, so no such integers existA1
Answer: Proof as in mark scheme
Examiner tip: End with a clear statement of the contradiction and the conclusion – the final mark is for the logic, not the algebra.

Book a free 30-minute session on WhatsApp and we'll find exactly which step is costing you the marks. Or build a timed paper on it.