Practise › Questions › Disproof and proof by contradiction
Disproof and proof by contradiction questions
A universal statement can be disproved by one counter example. A proof by contradiction works the other way round. Assume the negation of the claim, follow the consequences until they produce an impossibility, and conclude that the claim itself must hold.
7 original questions · 23 marks · the disproof and proof by contradiction notes · Proof
Every question here is written for this library rather than taken from a past paper. Write your answer out before opening the worked one: the answers award marks point by point, and the marks are easier to see when you have something of your own to compare against.
Disprove the statement “2n + 1 is prime for every positive integer n”.
Worked answer
Try n = 3: 23 + 1 = 9 = 3 × 3, which is not prime. B1 for the counter example, B1 for evaluating and factorising it. One counter example, evaluated and factorised, finishes the job. The claim survives n = 1 and n = 2 (giving 3 and 5), which is exactly why it looks safe.Disprove the statement “if a2 = b2 then a = b”.
Worked answer
Take a = −2 and b = 2. Then a2 = 4 = b2 but a ≠ b. B1 for the counter example, B1 for showing the squares agree while the numbers do not. Squaring throws away the sign, so equal squares only force a = ±b, and any pair with opposite signs will do. A counter example has to be stated with both values evaluated; explaining in words that negatives exist is not a disproof.A proof by contradiction of “√3 is irrational” must begin with an assumption. Write down that assumption in full.
Worked answer
Assume the statement is false: √3 is rational, so √3 = a/b where a and b are integers, b ≠ 0, and the fraction is in lowest terms, meaning a and b share no common factor. B1 for assuming √3 rational and writing it as a/b, B1 for the lowest-terms condition. The lowest-terms clause is there for a reason; the final contradiction crashes into it.Prove by contradiction that √3 is irrational. You may use the fact that if a2 is divisible by 3 then a is divisible by 3.
Worked answer
Assume √3 = a/b in lowest terms. Squaring: 3 = a2/b2, so a2 = 3b2. Then a2 is divisible by 3, so a is too: write a = 3c. Substituting, 9c2 = 3b2, so b2 = 3c2, and b is also divisible by 3. Now a and b share the factor 3, contradicting lowest terms. The assumption was false, so √3 is irrational. B1 for the assumption in lowest terms, M1 for reaching a2 = 3b2, A1 for a = 3c, M1 for substituting to get b2 = 3c2, A1 for the contradiction and the conclusion.Prove by contradiction that there are no integers a and b with 6a + 9b = 1.
Worked answer
Assume such integers exist. The left side is 3(2a + 3b), a multiple of 3, so 1 would have to be a multiple of 3 as well. It is not, so the assumption fails and no such integers exist. M1 for factorising as 3(2a + 3b), A1 for 1 not being a multiple of 3, A1 for the conclusion. The whole method is spotting the common factor of the coefficients, and 21a + 14b = 1 dies the same death with a factor of 7. Note that 2a + 3b must be declared an integer for the argument to close.Prove by contradiction that if n2 is even then n is even.
Worked answer
Assume the conclusion fails: n2 is even but n is odd, so n = 2k + 1. Then n2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1, which is odd. That contradicts n2 being even, so n must be even. B1 for assuming n odd, M1 for squaring n = 2k + 1, A1 for 2(2k2 + 2k) + 1, A1 for the contradiction and the conclusion. This little fact is the hinge of the √2 proof, and it earns its own question for that reason. Assuming n is odd, rather than assuming the whole implication false, is the correct negation here.In the infinitely-many-primes proof, the number N = 2 × 3 × 5 × 7 × 11 × 13 + 1 is built from the primes up to 13. Show that no prime on that list divides N, and explain why the common claim “so N must be prime” is wrong, using N itself.
Worked answer
Dividing N by any prime on the list leaves remainder 1, because the product part is exactly divisible and the + 1 is not: so none of 2, 3, 5, 7, 11, 13 divides N. But N = 30031 = 59 × 509, so N is composite. M1 for the remainder argument, A1 for no listed prime dividing N, B1 for the factorisation 59 × 509, A1 for N being composite, B1 for the argument needing only a prime factor off the list. The argument only needs some prime factor of N to be missing from the list; here 59 and 509 both are, and either one finishes the proof.
The same practice on paper: the printable workbook for this topic, questions and a worked answer book.
Practise disproof and proof by contradiction one question at a time
The player marks nothing for you. It shows one question, waits, then shows the worked answer so you can mark yourself, and brings a question back sooner when it went badly.