Questions on disproof and proof by contradiction

Question 1

Disprove the statement “2ⁿ + 1 is prime for every positive integer n”.

Accepted Answer

Try n = 3: 2³ + 1 = 9 = 3 × 3, which is not prime. B1 for the counter example, B1 for evaluating and factorising it. The claim survives n = 1 and n = 2 (giving 3 and 5), which is exactly why it looks safe.

Question 2

Disprove the statement “if a² = b² then a = b”.

Accepted Answer

Take a = −2 and b = 2. Then a² = 4 = b² 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.

Question 3

A proof by contradiction of “√3 is irrational” must begin with an assumption. Write down that assumption in full.

Accepted 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 final contradiction is with the lowest-terms clause.

Question 4

Disprove the statement “if a divides bc then a divides b or a divides c”, where a, b and c are positive integers.

Accepted Answer

Take a = 4, b = 2 and c = 6. Then bc = 12 and 4 divides 12, but 4 divides neither 2 nor 6. B1 for a counter example, B1 for checking all three divisions. The claim is true whenever a is prime, which is why a composite a is needed to break it; the result about n² divisible by 3 later in this bank is a case of the prime version.

Question 5

Prove by contradiction that √3 is irrational. You may use the fact that if a² is divisible by 3 then a is divisible by 3.

Accepted Answer

Assume √3 = a/b in lowest terms. Squaring: 3 = a²/b², so a² = 3b². Then a² is divisible by 3, so a is too: write a = 3c. Substituting, 9c² = 3b², so b² = 3c², 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 a² = 3b², A1 for a = 3c, M1 for substituting to get b² = 3c², A1 for the contradiction and the conclusion.

Question 6

Prove by contradiction that there are no integers a and b with 6a + 9b = 1.

Accepted 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 equation 21a + 14b = 1 fails in the same way, with the factor 7. Note that 2a + 3b must be declared an integer for the argument to close.

Question 7

Disprove the statement “the sum of any two prime numbers is even”.

Accepted Answer

Take the primes 2 and 3. Their sum is 5, which is odd. B1 for the counter example, B1 for evaluating the sum, B1 for identifying why it works: 2 is the only even prime, so it is the one case where “prime plus prime” can fail to be “even plus even”. Every other pair of primes is odd plus odd, which is even, so 2 is the whole exception the claim misses.

Question 8

Disprove the statement “if a and b are irrational then a + b is irrational”.

Accepted Answer

Take a = √2 and b = 2 − √2. B1 for the pair. Then a + b = √2 + 2 − √2 = 2, which is rational. M1 for the sum. Both a and b are irrational: √2 is irrational, and if 2 − √2 were rational then √2 = 2 − (2 − √2) would be rational too, which it is not. B1 for that justification. So two irrational numbers with a rational sum exist, and the claim is disproved. A1 for the conclusion. The pair was chosen so the irrational parts cancel; that is the pattern behind every counter example to this claim.

Question 9

Prove by contradiction that there is no smallest positive rational number.

Accepted Answer

Assume there is one, and call it r. B1 for the assumption. Then r/2 is also rational, and 0 < r/2 < r since r is positive, so r/2 is a smaller positive rational number. M1 for constructing r/2. That contradicts r being the smallest, so no smallest positive rational number exists. A1 for the contradiction and the conclusion. The same halving argument fails for the positive integers, because 1/2 is not an integer: 1 really is the smallest positive integer.

Question 10

Disprove the statement “if p and q are prime then pq + 1 is prime”.

Accepted Answer

Take p = 3 and q = 5. B1 for the counter example. Then pq + 1 = 15 + 1 = 16 = 2 × 8, which is not prime. B1 for evaluating and factorising it. B1 for noting the claim does hold for some pairs, such as p = 2, q = 3 giving 7, which is exactly why a single tested pair cannot stand in for a proof.

Question 11

Disprove the statement “n² > n for every positive integer n”.

Accepted Answer

Take n = 1: 1² = 1, which is not greater than 1. B1 for the counter example, B1 for evaluating it. The claim holds for every integer n ≥ 2, so n = 1 is the one boundary case worth checking before trusting a claim that starts “for every positive integer”.

Question 12

Prove by contradiction that if n² is even then n is even.

Accepted Answer

Assume the conclusion fails: n² is even but n is odd, so n = 2k + 1. Then n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd. That contradicts n² being even, so n must be even. B1 for assuming n odd, M1 for squaring n = 2k + 1, A1 for 2(2k² + 2k) + 1, A1 for the contradiction and the conclusion. It is the fact the √2 proof relies on. Assuming n² even and n odd is the correct negation of the implication.

Question 13

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.

Accepted 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.

Question 14

Prove by contradiction that if n² is divisible by 3 then n is divisible by 3.

Accepted Answer

Assume the conclusion fails: n² is divisible by 3 but n is not, so n = 3k + 1 or n = 3k + 2 for some integer k. B1 for the two-case assumption. If n = 3k + 1, n² = 9k² + 6k + 1 = 3(3k² + 2k) + 1, one more than a multiple of 3. M1 for squaring this case, A1 for regrouping to 3(3k² + 2k) + 1. If n = 3k + 2, n² = 9k² + 12k + 4 = 3(3k² + 4k + 1) + 1, also one more than a multiple of 3. A1 for the second case. Both cases give n² leaving remainder 1, contradicting n² being divisible by 3, so n must be divisible by 3. A1 for the contradiction and the conclusion. This is the fact the √3 proof borrows without proving it; splitting into two cases rather than one is what the negation of “n is a multiple of 3” actually requires.

Question 15

Prove by contradiction that √2 + √3 is irrational.

Accepted Answer

Assume √2 + √3 = r for some rational r; since both surds are positive, r > 0. M1 for the assumption with r > 0. Rearranging, √3 = r − √2, and squaring gives 3 = r² − 2r√2 + 2. M1 for squaring the rearranged equation. So 2r√2 = r² − 1, and, since r > 0, √2 = (r² − 1)/(2r). A1 for isolating √2 this way. The right side is rational, being built from the rational number r by arithmetic alone, but √2 is irrational. M1 for identifying the right side as rational, A1 for the contradiction. So the assumption is false, and √2 + √3 is irrational. B1 for the conclusion. Squaring once was not enough to clear both surds at once, so the method isolates one of them first.