A1 - Proof by contradiction | AQA A-Level Mathematics

Some claims are easier to prove by asking what would happen if they were false. You will negate claims precisely, derive an impossibility and complete proofs by contradiction. This will establish the irrationality of the square root of two, the infinity of primes and unfamiliar claims about numbers and intervals.

Negating a claim precisely

Could there be a smallest positive rational number, so small that no other positive fraction lies below it?

The fraction $\frac{1}{1000000}$ is small, but $\frac{1}{2000000}$ is smaller and still positive. Repeating that observation suggests an answer. To prove it, you must rule out every possible candidate, including one you have not named.

You already know

A claim includes its domain and assumptions. A counterexample to “if $p$ , then $q$ ” must make $p$ true and $q$ false. Integer parity and general rational fractions let you reason beyond particular examples.

In a contradiction proof, keep the original assumptions and temporarily suppose that the desired conclusion is false. That supposition is the claim's negation.

Proof by contradiction

Assume the negation of the claim to be proved. If valid deductions from this assumption and established facts produce an impossibility, the negation is false and the original claim is true. For example, an integer cannot be both even and odd. An inconvenient fraction, by itself, is not a contradiction.

Negation must include every way the original claim could fail. “Not every” means that at least one case fails; it does not mean that all cases fail.

Claim	Precise negation
Every integer has property $P$ .	There is an integer without property $P$ .
There is an integer with property $P$ .	No integer has property $P$ .
At least one of $a$ or $b$ is irrational.	Both $a$ and $b$ are rational.
$x>3$ .	$x\le3$ .
There are infinitely many primes.	There are only finitely many primes.

For an implication, the premise survives. To prove “if $n^2$ is odd, then $n$ is odd” by contradiction, assume that some integer has an odd square but is even. Assuming instead that every integer is even would change the claim. Negating $x>3$ as $x<3$ would also miss the equality case.

Here is a small complete contradiction. Suppose an integer $n$ satisfies $n^2+n=1$ . Its left side is $n(n+1)$ , a product of consecutive integers. One factor is even, so the product is even. The right side is odd: the same integer would be both even and odd. Therefore no integer satisfies the equation. The argument fails for a real domain because a real number need not have integer parity.

The contradiction principle and the parity result used here are not in the formula booklet: learn the logic and justify the mathematical consequence. In AQA questions, “Use proof by contradiction” fixes the method. State the negated conclusion, identify the precise incompatibility, then conclude the original claim.

Key idea

Negate the conclusion while keeping the premises and domain. Every deduction must be valid before the resulting impossibility can prove anything.

The next check targets a frequent error: negating “at least one” as “at least one” again.

Why the square root of two is irrational

A fraction chosen in lowest terms turns the square-root argument into a contradiction.

The rational fraction $\frac26=\frac13$ has an even numerator and denominator in its first representation. There is nothing impossible about that. The impossibility comes only if you chose a representation with no common factor and then proved that a common factor must exist.

Rational and irrational numbers

A rational number can be written as $a/b$ , where $a\in\mathbb Z$ and $b$ is a positive integer. A real number is irrational if no such representation exists. Lowest terms means that numerator and denominator have no common factor greater than $1$ . For example, $\frac13$ is in lowest terms; $\frac26$ is not.

Any rational fraction can be simplified to lowest terms. We also need both directions of the integer parity fact. If $m=2k$ , then $m^2=2(2k^2)$ is even. If $m=2k+1$ , then $m^2=2(2k^2+2k)+1$ is odd. These exhaustive even/odd cases establish the reverse implication too: an even square cannot come from an odd integer.

Parity of an integer square

For $m\in\mathbb Z$ ,

m\text{ is even}\Leftrightarrow m^2\text{ is even}

Not in the formula booklet: learn it.

The reverse direction has been proved, not obtained by simply reversing an arrow. You can now use it on the numerator and denominator of an assumed rational square root.

Worked example 1: the irrationality of the square root of two

Question. Prove by contradiction that $\sqrt2$ is irrational.

Plan. Assume a rational representation in lowest terms and show that both its numerator and denominator must be even.

Assume $\sqrt2=a/b$ , where $a,b$ are positive integers with no common factor greater than $1$ . Then

\begin{aligned} \sqrt2 &= \frac ab && \text{assumed rational form} \\ a^2 &= 2b^2 && \text{square and multiply by }b^2 \end{aligned}

Thus $a^2$ is even, so $a$ is even. Write $a=2k$ , where $k\in\mathbb Z$ . Substituting gives

\begin{aligned} 4k^2 &= 2b^2 && \text{substitute }a=2k \\ b^2 &= 2k^2 && \text{divide by }2 \end{aligned}

Hence $b^2$ and therefore $b$ are even too.

Why this step? Choosing lowest terms makes the shared factor $2$ incompatible with the starting representation. Without that choice, both integers being even would be harmless.

Answer. Both $a$ and $b$ have a common factor of $2$ , contradicting lowest terms. Therefore the rationality assumption is false and $\sqrt2$ is irrational.

Check. Substituting $a=2k$ into $a^2=2b^2$ gives exactly $4k^2=2b^2$ ; division is valid because $2\ne0$ . The contradiction concerns all possible reduced fractions, so a decimal approximation is unnecessary.

Worked example 2 changes the radicand from $2$ to $6$ . The same parity strategy works, but the extra odd factor $3$ must be handled explicitly.

Worked example 2: keeping track of an odd factor

Question. Prove by contradiction that $\sqrt6$ is irrational.

Plan. Assume a lowest-terms fraction, force its numerator to be even and use the remaining odd factor to force its denominator to be even.

Assume $\sqrt6=a/b$ , with positive integers $a,b$ in lowest terms. Then

\begin{aligned} a^2 &= 6b^2 && \text{square the assumption} \\ a &= 2k && a^2\text{ is even, so }a\text{ is even} \\ 4k^2 &= 6b^2 && \text{substitute} \\ 2k^2 &= 3b^2 && \text{divide by }2 \end{aligned}

The left side is even, so $3b^2$ is even. If $b^2$ were odd, its product with the odd integer $3$ would be odd. Therefore $b^2$ , and hence $b$ , is even.

Here $k$ is an integer because it represents half the even integer $a$ .

Why this step? Evenness of a product does not force every factor to be even. Here $3$ is known to be odd, which forces the evenness into $b^2$ .

Answer. Both $a$ and $b$ are even, contradicting lowest terms. Therefore $\sqrt6$ is irrational.

Check. The final relation is $2k^2=3b^2$ , not $b^2=2k^2$ . Its two sides still force an even $b$ by the odd-factor argument.

Neither irrationality result is in the formula booklet: be able to give the proof. A calculator showing many decimal places cannot establish irrationality, because every display is finite and rational numbers can also have long decimal expansions.

Watch out

Wrong: “Both numerator and denominator are even, which is impossible.” The fraction $\frac26$ shows that it is possible. Right: “Both are even, contradicting the initial choice of a fraction in lowest terms.”

The next question changes the radicand to $10$ . The odd factor remaining after division by $2$ changes accordingly.

Why there are infinitely many primes

A number built from a supposedly complete list of primes forces a prime outside that list.

First try the list $2,3,5$ . Its product plus one is $31$ . Every listed prime divides the product, so none divides the number one greater. This suggests a construction that will work for any proposed finite complete list.

Prime number

A prime is an integer greater than $1$ with exactly two positive divisors: $1$ and itself. For example, $2$ is prime. The number $1$ is not prime because it has only one positive divisor.

Every integer $N>1$ has a prime divisor, whether or not $N$ itself is prime. One justification is to take its smallest divisor $d>1$ . If $d$ were composite, one of its factors strictly between $1$ and $d$ would divide $N$ , contradicting minimality. Thus $d$ is prime. This prime-divisor result is not in the formula booklet: understand why it applies to composite numbers too.

Worked example 3: a proposed finite list

Question. Suppose a student claims that $2,3,5,7$ is the complete list of prime numbers. Use their product plus one to show that the list cannot be complete, without assuming the constructed number is prime.

Plan. Construct the number, exclude each listed prime as a divisor and use the existence of a prime divisor.

\begin{aligned} N &= 2\times3\times5\times7+1 && \text{product plus one} \\ &= 211 && \text{evaluate} \\ 211 &= 2(105)+1=3(70)+1 && \text{remainder }1 \\ 211 &= 5(42)+1=7(30)+1 && \text{remainder }1 \end{aligned}

Since $211>1$ , it has a prime divisor $q$ . None of $2,3,5,7$ divides $211$ , so $q$ is absent from the list.

Why this step? Finding a prime divisor is enough. Establishing whether $211$ itself is prime would add work the argument does not need.

Answer. The claimed complete list omits the prime $q$ , a contradiction. Therefore the list is not complete.

Check. Subtracting $1$ gives $210$ , a multiple of every listed prime. Adding $1$ therefore gives the required remainder for all four.

Worked example 4 changes the list from a particular list to an arbitrary supposedly complete finite list. The product-plus-one construction stays the same; this is what rules out every finite list.

Worked example 4: ruling out every finite complete list

Question. Prove by contradiction that there are infinitely many primes.

Plan. Assume a finite complete list, then construct an integer with a prime divisor outside it.

Assume there are finitely many primes and list all of them as $p_1,p_2,\ldots,p_k$ . The list is nonempty because $2$ is prime. Form

N=p_1p_2\cdots p_k+1>1

For any listed prime $p_i$ ,

\begin{aligned} p_1p_2\cdots p_k &= p_i m && m\in\mathbb Z \\ N &= p_i m+1 && \text{remainder }1 \end{aligned}

Thus no listed prime divides $N$ . Yet $N>1$ , so it has a prime divisor $q$ , which cannot be any $p_i$ .

Why this step? The list was assumed to contain every prime. Producing a prime outside it contradicts that assumption, even if $N$ is composite.

Answer. The supposedly complete finite list omits $q$ . Therefore there cannot be finitely many primes: there are infinitely many.

Check. If a listed prime divided both the product and $N$ , it would divide their difference $1$ , which no prime can do. This confirms the remainder argument without needing a value for $q$ .

The infinity of primes and this construction are not supplied in the formula booklet: be able to explain the proof. There is a useful surprise hidden in the construction. Multiplying the first six primes and adding one gives

2\times3\times5\times7\times11\times13+1=30031=59\times509

The constructed number is composite. The proof works because its prime divisors are missing from the original list, not because the constructed number must be prime.

Watch out

Wrong: “The product of all the listed primes plus one is prime.” The construction guarantees the remainders, not primality; the number can be composite. Right: it is greater than $1$ , so it has a prime divisor, and none of the listed primes can be that divisor.

The next check enlarges the proposed finite list. Use its product structure rather than performing separate long divisions.

Adapting contradiction to unfamiliar claims

An unfamiliar contradiction proof becomes manageable when you identify the exact property that an assumed object would have to satisfy.

For the opening question, suppose $x$ is the smallest positive rational number. Write $x=p/q$ , with positive integers $p,q$ . Then

\frac x2=\frac{p}{2q}\in\mathbb Q \qquad\text{and}\qquad 0<\frac x2<x

This is a smaller number in the same domain, contradicting the claimed smallest value. Therefore there is no smallest positive rational number. Halving would not establish the analogous statement about positive integers, because $\frac12$ is not an integer. In fact, $1$ is the smallest positive integer.

For rational-number proofs, make closure under arithmetic explicit. If $a/b$ and $c/d$ are rational, with integer numerators and positive integer denominators, their sum and difference are $(ad\pm bc)/(bd)$ , and their product is $ac/(bd)$ . Each is rational because the numerator is an integer and the denominator is nonzero. A quotient is rational when its divisor is nonzero:

\frac{a/b}{c/d}=\frac{ad}{bc}\qquad(c\ne0)

For example, let $r\ne0$ be rational and $t$ irrational. If $s=rt$ were rational, then $t=s/r$ would be rational, a contradiction. Therefore $rt$ is irrational. The restriction matters: $0t=0$ is rational. These closure results, the irrational-product result and the smallest-number result are not in the formula booklet: justify the domain and arithmetic when using them.

For an interval, halving can leave the domain. Instead, construct the midpoint between your proposed extreme value and the relevant endpoint. For instance, if a candidate largest value in $(2,5)$ were $x=3$ , its midpoint with the upper endpoint would be $4$ , still inside the interval and larger.

A midpoint inside an open interval gives a value greater than the proposed largest value

Worked example 5: an interval with no smallest real number

Question. Use proof by contradiction to prove that there is no smallest real number in the interval $2<x<5$ .

Plan. Assume a smallest value and construct the midpoint between it and the lower endpoint.

Suppose $x$ is the smallest real number in $(2,5)$ , and define $y=(2+x)/2$ . Then

\begin{aligned} y-2 &= \frac{x-2}{2}>0 && x>2 \\ x-y &= \frac{x-2}{2}>0 && x>2 \\ 2 &< y<x<5 && \text{combine the inequalities} \end{aligned}

Why this step? The inequalities establish both jobs: $y$ belongs to the original interval and is smaller than the alleged smallest value.

Answer. The real number $y$ lies in $(2,5)$ below $x$ , contradicting minimality. Therefore the interval has no smallest real number.

Check. If $x=3$ , the construction gives $y=\frac52$ , which satisfies $2<\frac52<3$ . The proof itself works for every possible proposed $x$ .

Worked example 6 changes only the proposed extreme, from smallest to largest. Use the upper endpoint in the midpoint construction.

Worked example 6: an interval with no largest real number

Question. Use proof by contradiction to prove that there is no largest real number in the interval $2<x<5$ .

Plan. Assume a largest value and construct the midpoint between it and $5$ .

Suppose $x$ is the largest real number in $(2,5)$ . Define $y=(x+5)/2$ . Then

\begin{aligned} y-x &= \frac{5-x}{2}>0 && x<5 \\ 5-y &= \frac{5-x}{2}>0 && x<5 \\ 2 &< x<y<5 && \text{combine the inequalities} \end{aligned}

Why this step? Showing only $y>x$ would leave a gap: a number outside the interval cannot challenge its largest member. The upper inequality keeps $y$ inside.

Answer. The value $y$ is in $(2,5)$ and exceeds $x$ , contradicting maximality. Therefore the interval has no largest real number.

Check. At $x=3$ , the construction gives $y=4$ , as in the diagram, with $2<3<4<5$ .

These interval results and midpoint constructions are not in the formula booklet: derive the required inequalities. In AQA's interval proofs, explicitly state the interval in the assumption and show that the new value remains in it. The word “contradiction” cannot replace those facts.

Watch out

Wrong: assume a smallest $x\in(2,5)$ and claim that $x/2$ is a smaller member. For $x=3$ , it equals $1.5$ , outside the interval. Right: use $(2+x)/2$ , then prove $2<(2+x)/2<x$ .

When critiquing a proof, identify the first unjustified step: a wrong negation, a missing lowest-terms condition, division by a possible zero, a constructed value outside the domain, or an unproved claim that product plus one is prime. A repaired proof must supply the missing mathematical link.

The next question changes the interval endpoints. The midpoint must change with them.

Quick Recap

Negate the conclusion precisely while retaining the original domain and premises.
For square-root irrationality, choose a fraction in lowest terms and derive a common factor.
For infinitely many primes, product plus one has a prime divisor missing from any supposed finite complete list; it need not itself be prime.
In unfamiliar proofs, show that the constructed object satisfies every condition needed for the contradiction.

There is no smallest positive rational number: halving any proposed one produces a smaller positive rational number, contradicting its supposed minimality.

Last Accessed

Pure Mathematics

Mechanics

Statistics

A1 - Proof by contradiction

Negating a claim precisely

Why the square root of two is irrational

Why there are infinitely many primes

Adapting contradiction to unfamiliar claims

Quick Recap

Learn faster with Nova