Maths › Proof › Disproof and proof by contradiction
Disproof and proof by contradiction
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.
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 the primes never run out.
- Apply contradiction to a statement you have never seen before.
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 one case where it fails is enough to disprove it. That is disproof by counter example, and it is the only place in this unit where 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 does start well, giving 3, 7 and 13 at n = 2, 3 and 4. A promising run tempts you into believing the claim, and that is precisely why a promising run proves nothing.
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. Sound reasoning cannot turn a truth into an absurdity, so the faulty ingredient was the assumption, and the original statement stands. Two classics are named in the specification and you should be able to write out either one 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 was legitimate, so the assumption is what has to go. No such fraction exists. Last lesson's odd-times-odd result is what justifies the middle step.
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. ∎
A common slip is to claim that N itself must be prime. It need not be. 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30 031 = 59 × 509. What the proof needs is only that N's prime factors are new ones, and the remainder argument delivers that much.
Making it yours
The examiners' phrase is “application to unfamiliar proofs”. The two classics are templates, and the technique transfers whenever assuming the opposite gives you something concrete 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. ∎
Tiny, and yet it has the full structure. The negation gives you 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. ∎
Unfamiliar statement, familiar method. The negation produced an equation between integers, and a parity argument finished it, as it did for √2.
ASSESSMENT FOCUS
- A disproof needs one counter example shown in full. Give the value, evaluate the expression, and demonstrate the failure by factorising or by whatever the claim calls for. "It 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." That lowest-terms clause is load-bearing, because it is where the contradiction eventually lands.
- Both named proofs are quotable questions and they do come up. Learn them as arguments, not as scripts. Markers follow your logic and are indifferent to your wording.
- In the primes proof, never claim N is prime. Claim only that its prime factors cannot be on the list. The number 30 031 exists in mark schemes to catch that exact sentence.
- Close the loop out loud. "This contradicts the assumption, so the assumption is false and the statement is true." That sentence carries a mark of its own.
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 one common factor was enough to rule it out. Spotting which impossibility the assumption leads to is the main skill in these questions.
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.
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 the primes never run out.
- Apply contradiction to a statement you have never seen before.
Open the full revision checklist to see every objective in the course in one place.