WMA12/01 October 2024 Question 11: Proof by Exhaustion and Counter-example

Question 1

Give one prime value of n for which 3ⁿ + 2 is not prime, showing the resulting number is composite.

Accepted Answer

Try the prime n = 5 3⁵ + 2 = 243 + 2 = 245 245 = 5 × 49, so 245 is not prime So the statement is false Answer: Counter-example: n = 5 is prime but 3⁵ + 2 = 245 = 5 × 49 is not prime, so the statement is false

Question 2

Consider the two cases of m not divisible by 3, showing in each that m² − 1 is divisible by 3.

Accepted Answer

If m is not divisible by 3, then m = 3k + 1 or m = 3k + 2 for some integer k m = 3k + 1: m² − 1 = 9k² + 6k + 1 − 1 = 9k² + 6k = 3(3k² + 2k) m = 3k + 2: m² − 1 = 9k² + 12k + 4 − 1 = 9k² + 12k + 3 = 3(3k² + 4k + 1) Both are multiples of 3, so m² − 1 is divisible by 3 whenever m is not divisible by 3 Answer: Shown: m = 3k + 1 gives m² − 1 = 3(3k² + 2k); m = 3k + 2 gives m² − 1 = 3(3k² + 4k + 1); both are multiples of 3

WMA12/01 Oct 2024, Question 11: Proof by Exhaustion and Counter-example

The question, in short

Part (i) · 2 marks

Part (ii) · 4 marks

Practise more proof by exhaustion and counter-example questions

More past-paper questions on proof by exhaustion and counter-example