Hersi Maths WhatsApp me

Understand · explore · practise

Proof by contradiction

Learn A-level proof by contradiction: negate a claim, prove parity and irrationality results, and check each logical step. Interactive diagrams and practice with worked solutions.

Before you startInteger parity, expanding brackets and fractions in lowest terms

01 / The method

Assume the claim is false, then follow the consequences.

A contradiction is a conclusion that cannot be true alongside an established fact or an assumption you are using. To prove a claim, temporarily assume its exact opposite. If valid reasoning leads to a contradiction, that opposite must be false, so the original claim is true.

Opposite assumption → valid deductions → contradiction

State what the contradiction is, then return to the claim you were asked to prove.

  1. Set the domain. Are the numbers integers, rationals or reals?
  2. Assume the negation. Keep any given conditions.
  3. Deduce carefully. Each line needs a reason; avoid dividing by a value that could be zero.
  4. Identify the clash. For example, an integer cannot be both even and odd.
  5. Conclude. Reject the opposite assumption and state the original result.

A surprising decimal or a picture that looks wrong is not a contradiction. You need an explicit impossibility.

02 / Choose the opposite

“Not all” does not mean “none”.

Negate the whole statement. The opposite of “every” is “at least one counterexample”; the opposite of “there exists” is “there are none”. Keep the same domain.

Three useful patternsWorked example

Every member has property P.

Opposite: at least one member does not have P.

At least one member has property P.

Opposite: no member has P.

If A holds, then B holds.

Opposite: A holds and B fails. Do not assume A fails.

For real x, the opposite of x > 4 is x ≤ 4, not x < 4. The boundary matters. The opposite of “there is exactly one solution” is “there are zero solutions or at least two”.

Try a conditional claim

To prove “if n² is even, then n is even” for integer n, assume n² is even and n is odd. Keep the given condition about n².

03 / Parity proof

An even square cannot come from an odd integer.

Claim: if n is an integer and n² is even, then n is even.

  1. Keep the premise that n² is even. Assume, for a contradiction, that n is odd.
  2. Then n = 2k + 1 for some integer k.

  3. n² = (2k + 1)²
    = 4k² + 4k + 1
    = 2(2k² + 2k) + 1

  4. Because 2k² + 2k is an integer, this says n² is odd. That contradicts the given evenness of n².
  5. Therefore n cannot be odd. Every integer is even or odd, so n is even.

The diagram illustrates the expansion; the integer argument proves it for all n. Checking five or even five million numbers would not prove a claim about every integer.

How is this different from a contrapositive proof?

The contrapositive proves “n odd implies n² odd” directly. The contradiction proof uses that same calculation while also retaining the premise that n² is even, then names the clash.

An odd square has one extra tileExplore
A square with side 2k + 1 A 2k by 2k block, two strips of 2k tiles, and one corner. The block and strips have even areas; the last corner makes the total odd. 16 4 4 1 2k = 4 1

k = 2: 5² = 16 + 4 + 4 + 1 = 25. Even + even + even + 1 is odd.

The areas change to scale. This picture uses positive k; the algebra beside it covers every integer k, including zero and negative values.

Watch the even blocks leave one extra tile

Pause, replay or seek freely. The notes explain the same idea and stay in view.

04 / Irrationality

Lowest terms gives the contradiction something to clash with.

Claim: √5 is irrational. Rational means expressible as a/b for integers a and b with b ≠ 0. We may choose b > 0 and cancel all common factors first.

  1. Assume √5 = a/b, where a and b are coprime integers and b > 0.
  2. Squaring and multiplying by b² gives a² = 5b², so 5 divides a².
  3. The remainder check beside this proof shows that 5 divides a. Write a = 5c for an integer c.

  4. 25c² = 5b² ⇒ b² = 5c²

    The same remainder argument shows that 5 divides b.
  5. Both a and b have factor 5. This contradicts our choice of a/b in lowest terms.
  6. Therefore √5 is irrational.

Simply discovering a common factor is not impossible for an arbitrary fraction. The contradiction depends on having chosen a reduced fraction at the start.

Why 5 | a² implies 5 | aWorked example

a has remainder 0, 1, 2, 3 or 4
when divided by 5.

This covers every integer, including negative integers.

a² has remainder 0, 1, 4, 4 or 1
respectively.

Square each possible remainder, then take its remainder modulo 5.

Only remainder 0 produces
a square divisible by 5.

So a itself is divisible by 5. This implication is not true for every divisor: 4 divides 2² but not 2.

05 / Use a known result

An irrational number cannot secretly become a rational fraction.

Once you know √5 is irrational, use it as an established fact. You do not need to repeat the lowest-terms proof every time.

Prove (3 + √5)/2 is irrationalWorked example

Assume r = (3 + √5)/2
is rational.

We aim for a contradiction with the result in the previous section.

√5 = 2r − 3

Rearrange the assumed equality.

If r = u/v, then
2r − 3 = (2u − 3v)/v.

For integers u, v with v ≠ 0, this is rational.

But √5 is irrational.

Contradiction. Hence (3 + √5)/2 is irrational.

06 / Existence claims

A supposed smallest value can be beaten.

Claim: there is no smallest positive rational number.

Assume a smallest positive rational r exists. Let s = r/3. Since r is rational, s is rational. Since r > 0, we have 0 < s < r. This is a smaller positive rational, contradicting the assumed minimality of r. So no smallest positive rational exists.

r > 0 ⇒ 0 < r/3 < r

The same reasoning fails for positive integers: r/3 might not be an integer. The positive integers do have a smallest member, 1. Always check that your constructed counterexample remains in the required set.

Does the set need a smallest element to have a lower bound?

No. Zero is a lower bound for all positive rational numbers, but is not a member of that set. A bound need not be an attained minimum.

07 / Infinite primes

A finite list cannot contain every prime.

Assume there are only finitely many primes, listed as p₁, p₂, …, pₘ. Form N = p₁p₂⋯pₘ + 1. This is an integer greater than 1.

Every listed prime divides the product, so division of N by any listed prime leaves remainder 1. None can divide N. Yet every integer greater than 1 has a prime divisor. That divisor is missing from our supposedly complete list: a contradiction. Therefore there are infinitely many primes.

Why must an integer greater than 1 have a prime divisor?

Take its smallest divisor d greater than 1. If d were composite, it would have a divisor e with 1 < e < d, and e would also divide the original integer. This contradicts the choice of d. So d is prime.

The new number need not be primeWorked example

N = 2 × 3 × 5 × 7 × 11 × 13 + 1
= 30,031

This example illustrates the construction; it is not the proof of the infinite claim.

30,031 = 59 × 509

N is composite. Its prime factors are absent from this particular list.

New prime divisor ≠ necessarily N

The proof needs a prime divisor missing from the list. Claiming N is always prime is an error.

08 / Check a proof

Find the precise invalid step.

Proposed argument: choose a = b = 3. Then a² = ab, so a² − b² = ab − b². Factor and cancel a − b to obtain a + b = b. This gives 6 = 3.

Does that prove that a and b cannot be equal?

No. The factorisation is valid, but cancellation divides by a − b = 0. The impossible conclusion came from an invalid step, so it proves nothing about the original equality.

A valid geometric contradiction: assume a non-degenerate Euclidean triangle has two right angles. Its angles would sum to 90° + 90° + θ with θ > 0, exceeding 180°. This contradicts the triangle angle sum, so such a triangle cannot exist.

The geometry argument states its setting and uses an established theorem. A sketch alone would not rule out every triangle.

09 / Your turn

Write the assumption, the clash and the conclusion.

Attempt each argument before opening the hint. Explain why constructed quantities stay in their domain, and name the exact contradiction.

01 · Negate precisely

Negate: (a) Every real x satisfies x² ≥ x. (b) There exists a positive integer n with n² = 12. (c) If integer n is divisible by 8, then it is even.

Hint

“Every” becomes “there exists a counterexample”. A conditional fails when its premise holds and conclusion fails.

Worked solution

(a) There exists a real x with x² < x. (b) No positive integer n has n² = 12. (c) There exists an integer divisible by 8 which is odd. These are negations, whether or not the original claims are true.

02 · Odd sum

Prove by contradiction that if integers a and b have an odd sum, they cannot both be odd.

Hint

Assume both can be written as twice an integer plus one.

Worked solution

Assume a = 2r + 1 and b = 2s + 1 for integers r and s. Then a + b = 2(r + s + 1) is even, contradicting the given odd sum. Therefore a and b cannot both be odd.

03 · Consecutive squares

Prove that the squares of consecutive integers cannot have the same parity.

Hint

The difference of two integers with the same parity is even.

Worked solution

Assume n² and (n + 1)² have the same parity for an integer n. Their difference would be even. But (n + 1)² − n² = 2n + 1 is odd. Contradiction, so the two squares have different parity.

04 · Rational multiplier

Given that √5 is irrational, prove that 7√5 − 4 is irrational.

Hint

Assume the whole expression is rational and rearrange for √5.

Worked solution

Assume r = 7√5 − 4 is rational. Then √5 = (r + 4)/7 is rational because adding an integer and dividing by a nonzero integer preserves rationality. This contradicts the given irrationality of √5. Hence 7√5 − 4 is irrational.

05 · A faulty generalisation

A student claims: “If d divides a², then d divides a, for all positive integers d and a.” Disprove the claim and explain why it cannot be used in every irrationality proof.

Hint

Try a composite d.

Worked solution

Take d = 9 and a = 3. Then 9 divides a² = 9 but does not divide 3. The implication needs justification for the chosen divisor; it holds for prime divisors, but not for arbitrary composite divisors.

06 · No largest value in an interval

Prove that the rational numbers strictly between 0 and 1 have no largest member.

Hint

Given a proposed largest r, examine (r + 1)/2.

Worked solution

Assume r is the largest rational with 0 < r < 1. Let s = (r + 1)/2, which is rational. Then s − r = (1 − r)/2 > 0 and 1 − s = (1 − r)/2 > 0. Hence 0 < r < s < 1, contradicting maximality. There is no largest member.

07 · Finish the prime argument

A proposed complete list of primes is 2, 3, 5, 7. Construct the product plus one and show that a prime divisor is missing. Explain why this numerical example is not itself a proof of infinitely many primes.

Hint

The new number is 211. Test prime divisors up to its square root.

Worked solution

N = 2 × 3 × 5 × 7 + 1 = 211. No prime 2, 3, 5, 7, 11 or 13 divides it; since √211 < 15, it is prime. So 211 is missing. This refutes only this particular list. The general proof must work for any proposed finite complete list, even when its product plus one is composite.

08 · Irrational reciprocal

Prove that 1/√5 is irrational, using the established irrationality of √5.

Hint

The reciprocal of a nonzero rational number is rational.

Worked solution

Assume r = 1/√5 is rational. It is nonzero, so 1/r is rational: if r = u/v with u ≠ 0 and v ≠ 0, its reciprocal is v/u. But 1/r = √5, contradicting its irrationality. Therefore 1/√5 is irrational.

09 · Geometry and assumptions

Prove that a non-degenerate Euclidean triangle cannot have two interior angles greater than or equal to 100°.

Hint

What is the minimum sum of just those two angles?

Worked solution

Assume two interior angles are each at least 100°. Their sum is at least 200°, and the third angle is positive. The total exceeds 180°, contradicting the angle sum of a Euclidean triangle. Therefore the proposed triangle cannot exist.

10 · Find the missing justification

A proof begins “Assume √5 = a/b” and later finds that 5 divides both a and b. It concludes “contradiction”. What must be added?

Hint

Fractions such as 10/15 have common factors without being impossible.

Worked solution

State that a and b are coprime integers and b > 0, choosing a fraction in lowest terms. Then a shared factor 5 contradicts coprimality. Without the reduced-fraction condition, a common factor alone is not a contradiction.

10 / Recap

The conclusion is only as strong as the reasoning.

  • Negate the exact claim while retaining its given conditions.
  • State integer, rational and geometric assumptions.
  • Justify deductions, especially divisibility and cancellation.
  • Name the fact your conclusion contradicts.
  • Finish with the original claim; examples illustrate a general proof but cannot replace it.

Revisit direct proof and counterexamples →

Back to Pure 2 algebraic methods →

Section 1 of 10 · The method