Maths › Proof › Disproof and proof by contradiction
Disproof and proof by contradiction
A universal statement can be disproved by a single counter example. Proof by contradiction works the other way round: the negation of the claim is assumed, its consequences are followed to an impossibility, and the claim itself must therefore hold.
Builds on The structure of proof: deduction and exhaustion.
IN THIS TOPIC
- Disprove a universal claim with a single counter example, sought where the claim is most likely to fail.
- Reproduce the contradiction proof that √2 is irrational.
- Reproduce the contradiction proof that there are infinitely many primes.
- Apply proof by contradiction to an unfamiliar statement.
COMMON MISCONCEPTION
To disprove a claim you must show it fails every time.
One counter example is enough. A universal claim says something about every case, so a single case where it fails disproves it: n2 − n + 1 is prime at n = 2, 3 and 4, but at n = 5 it is 21, which is 3 × 7. Give the value, evaluate the expression and show the failure in writing.
One counter example is enough
A universal claim says something about every case, so one case where it fails is enough to disprove it. That is disproof by counter example, and it is the one method for which checking numbers is the whole of the work. Choosing where to look is the skill. Boundary values, negatives, zero and numbers with awkward factorisations are the usual places to try.
WORKED EXAMPLE
A prime-generating formula, allegedly
Show that the statement “n2 − n + 1 is a prime number for all values of n” is untrue.
Try n = 5. Then 25 − 5 + 1 = 21, and 21 = 3 × 7, so it is not prime.
One counter example, evaluated and factorised in writing. The disproof is finished. ∎
The formula gives the primes 3, 7 and 13 at n = 2, 3 and 4. Those values are evidence for the claim and do not establish it, because the claim covers every n.
Proof by contradiction
Some statements are hard to prove directly. Proof by contradiction approaches them the other way round. Assume the statement is false, reason correctly from that assumption, and arrive at something impossible. Correct reasoning from a true statement cannot give an impossibility, so the assumption is false and the original statement holds. Edexcel 9MA0 1.1 names two such proofs, the irrationality of √2 and the infinitude of the primes; both should be reproducible from memory.
WORKED EXAMPLE
√2 is irrational
Prove that √2 cannot be written as a fraction of integers.
Assume that it can, so √2 = a/b with a and b integers sharing no common factor. Any fraction can be put in that lowest form, so the assumption costs nothing.
Square both sides. 2 = a2/b2, so a2 = 2b2 and a2 is even. Odd times odd is odd, so a itself must be even, say a = 2c.
Substituting, (2c)2 = 2b2 gives b2 = 2c2, so b is even too. Now a and b share the factor 2, which the lowest-form assumption forbade. ∎
Every step after the assumption is valid, so the assumption is false and no such fraction exists. The middle step uses the result that a product of two odd numbers is odd.
WORKED EXAMPLE
There are infinitely many primes
Prove that the list of primes never ends.
Assume that it does. Let the complete list be p1, p2, …, pn, and build N = p1p2…pn + 1.
Divide N by any prime on the list and the remainder is 1, so no listed prime divides N. Every integer above 1 has at least one prime factor, so N has one, and it is missing from a list that was supposed to be complete. ∎
The argument does not claim that N is itself prime, and N need not be: 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30 031 = 59 × 509. The proof requires only that every prime factor of N is absent from the list, which the remainder argument establishes.
One fact underlies both arguments. The fundamental theorem of arithmetic says that an integer greater than 1 is a product of primes, and that up to the order of the factors there is one such product and no other, so 360 comes out as 23 × 32 × 5 whichever factor you happen to pull out first. The primes proof used the first half when it said that N has a prime factor. The second half gives another route to √2: in a2 the prime 2 occurs an even number of times, and in 2b2 an odd number, so those two numbers differ. The theorem is quotable at this level; its proof is not asked for.
Applying contradiction to an unfamiliar statement
Edexcel 9MA0 1.1 lists application to unfamiliar proofs. The two named proofs are templates, and the method transfers whenever the negation supplies a concrete object or equation to work with. Assume the negation, derive an impossibility, state the conclusion: those three steps are the structure of every proof of this kind.
GUIDED PRACTICE
No largest even number
Prove by contradiction that there is no largest even number, before opening the working.
Show the working
Assume there is one. Call it E, an even number with no even number larger.
Then E + 2 is even and E + 2 > E, so there is an even number larger than the largest even number. Contradiction, so no largest even number exists. ∎
The proof is short but has the full structure: the negation supplies a concrete object, and that object leads directly to the contradiction.
INDEPENDENT PRACTICE
A logarithm that cannot be a fraction
Prove by contradiction that log2 3 is irrational.
Show the working
Assume log2 3 = a/b with a and b integers. Since log2 3 > 0, both may be taken positive. Then 2a/b = 3, so 2a = 3b.
The left side is even, because a ≥ 1. The right side is a product of odd numbers, so it is odd. An even number cannot equal an odd one. ∎
The negation produced an equation between integers, and a parity argument completed the proof, as in the argument for √2.
ASSESSMENT FOCUS
- A disproof requires one counter example shown in full: give the value, evaluate the expression, and demonstrate the failure, by factorising or by whatever the claim requires. A statement that the claim "does not work" is not a demonstration.
- Open a contradiction proof by writing the assumption out: "Assume √2 is rational, so √2 = a/b in lowest terms." The lowest-terms clause is what the final contradiction contradicts, so include it.
- Learn both named proofs as arguments rather than as fixed wording. Any correct chain of reasoning from the assumption to the impossibility is a valid proof.
- In the primes proof, state that no prime on the list divides N, so N has a prime factor outside the list. N itself need not be prime, as 30 031 = 59 × 509 shows.
- End with the conclusion in words: "This contradicts the assumption, so the assumption is false and the statement is true." A complete proof includes that sentence.
CHECK YOURSELF
Prove by contradiction that there are no positive integers a and b with 21a + 14b = 1.
Show a hint
Look for a common factor on the left that the right cannot match.
Show the answer
Assume such integers exist, so 21a + 14b = 1 with a and b positive integers.
The left side is 7(3a + 2b), a multiple of 7. The right side is 1, which is not. Contradiction. ∎
So no such integers exist. The negation produced an equation, and a common factor on one side that the other side does not have was enough to rule it out.
One counter example is enough to disprove a universal claim.
Assume the opposite, reason correctly until you reach an impossibility, and the original statement is proved.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
Or read them with their worked answers on the disproof and proof by contradiction questions page.
USED LATER IN
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Disprove a universal claim with a single counter example, sought where the claim is most likely to fail.
- Reproduce the contradiction proof that √2 is irrational.
- Reproduce the contradiction proof that there are infinitely many primes.
- Apply proof by contradiction to an unfamiliar statement.
Open the full revision checklist to see every objective in the course in one place.