Pure 1.1 - Structure of mathematical proof | Edexcel A-Level Mathematics

Learn how to turn a convincing pattern into a proof, and how to spot an argument that falls short. You will use deduction, exhaustion, counterexamples and contradiction, including the proofs that $\sqrt2$ is irrational and that the primes never run out.

What a proof must do

Could you ever finish a list of all the prime numbers, however much time and paper you had?

Start with a small attempt: $2, 3, 5$ . Multiplying the listed primes and adding $1$ gives $2\times3\times5+1=31$ , a prime missing from the list. That defeats this list, but does the same idea defeat every finite list? By the end of the lesson, you will have an argument that settles the question.

First, notice the gap between finding examples and proving a statement. At $n=1, 2, 3$ , the expression $n^2-n$ gives $0, 2, 6$ . All three values are even. The pattern looks promising, but checking three integers leaves infinitely many unchecked.

You already know

An even integer has the form $2k$ , and an odd integer has the form $2k+1$ , where $k\in\mathbb Z$ . Zero is even because $0=2\times0$ . A prime is an integer greater than $1$ with exactly two positive factors: $1$ and itself; $2$ is prime, but $1$ is not.

Instead of choosing a value of $n$ , let $n$ be any integer. Then

n^2-n=n(n-1) \qquad \text{factorise}

The factors are consecutive integers, so one is even. Their product is therefore even. This proves the result for every integer, including negative integers and zero: the argument never depended on a particular value.

Mathematical proof

A mathematical proof proceeds from stated assumptions through a logically connected sequence of valid steps to a conclusion. Each step follows from a definition, an accepted result or an earlier step.

For example, the consecutive-factor argument proves that $n^2-n$ is even for all integers $n$ . Checking three values is evidence for that statement, not a proof of it.

A universal statement claims that something holds for every member of its stated domain. An existence statement claims that at least one member works. One valid example can establish existence; one failed example can disprove a universal claim. Neither establishes a universal claim about an infinite domain.

Make the three jobs of a proof visible:

Job	In the consecutive-factor proof
State the assumption	Let $n\in\mathbb Z$ .
Give the logical chain	Factorise, then use the parity of consecutive integers.
State the conclusion	Therefore $n^2-n$ is even for every integer $n$ .

Symbols carry logical meaning

Writing $=$ between two lines claims equal values. Writing $\equiv$ says an identity holds throughout its domain, for example $(x+1)^2\equiv x^2+2x+1$ . An approximation uses $\approx$ , as in $\sqrt2\approx1.414$ ; an approximation cannot establish an exact equality.

An implication goes one way: $x=2\Rightarrow x^2=4$ . Its reverse fails because $x=-2$ also has square $4$ . Use $\Leftrightarrow$ only when both directions hold: $x^2=4\Leftrightarrow x=2\text{ or }x=-2$ , for real $x$ . Likewise, $x^2\ge0$ includes equality at $x=0$ , whereas $x^2>0$ excludes it. Those small differences can decide whether a proof is valid.

Key idea

A proof explains why the conclusion must follow for the whole stated domain; a collection of successful trials does not fill that logical gap.

The proof methods in this lesson are not supplied in the formula booklet. Learn their logic, then use the following check to distinguish a calculation from a conclusion.

Proof by deduction

Deduction starts from what you know and takes justified steps towards what you need to prove.

For instance, consecutive integers $n$ and $n+1$ have squares whose difference is

\begin{aligned} (n+1)^2-n^2 &= n^2+2n+1-n^2 && \text{expand} \\ &=2n+1 && \text{collect terms} \end{aligned}

Since $n$ is an integer, $2n+1$ is odd. The algebra gives the form; the final sentence explains why that form proves the claim.

Proof by deduction

Proof by deduction derives the required conclusion directly from the assumptions, definitions and known results. For example, writing a difference as $2n+1$ , with integer $n$ , proves it is odd.

For positivity, a different known result is useful: a real square cannot be negative. Completing the square makes that fact visible.

You already know

Expanding gives $(n-a)^2=n^2-2an+a^2$ . To complete a square, halve the coefficient of $n$ , put that number inside the bracket, then adjust the constant so the expression keeps its value.

The adjustment matters: $(n-3)^2$ already contains a constant term of $9$ , so an expression with constant term $10$ needs one more. Once the square is exposed, use its sign.

A real square is non-negative

For every real number $u$ ,

u^2\ge0

Equality holds exactly when $u=0$ . Thus $u^2+c>0$ for every real $u$ if $c>0$ .

Not in the formula booklet: learn it.

Look for a square plus a constant before trying individual values. That gives a bound for the entire real domain in one line.

Worked example 1: proving strict positivity

Question. Prove that $n^2-6n+10$ is positive for every real value of $n$ .

Plan. Complete the square, then use its smallest possible value.

Answer. For any real $n$ ,

\begin{aligned} n^2-6n+10 &= (n-3)^2+1 && \text{complete the square} \\ &\ge 0+1 && \text{a real square is non-negative} \\ &=1>0 && \text{the lower bound is positive} \end{aligned}

Therefore $n^2-6n+10>0$ for every real $n$ .

Why complete the square? It separates the variable part, which has a known lower bound, from the constant that decides strict positivity.

Check. At $n=3$ , the square vanishes and the expression equals $9-18+10=1$ . This attains the bound and confirms its value; the inequality above, rather than this check, proves the claim.

Worked example 2 changes only the constant term, from $10$ to $9$ . That one change makes equality possible, so the conclusion must change too.

Worked example 2: allowing equality

Question. Show that $n^2-6n+9\ge0$ for every real $n$ , and state when equality holds.

Plan. Use the same completed square and identify when it is zero.

Answer. For every real $n$ ,

\begin{aligned} n^2-6n+9 &= (n-3)^2 && \text{complete the square} \\ &\ge0 && \text{a real square is non-negative} \end{aligned}

Also,

(n-3)^2=0\Leftrightarrow n-3=0\Leftrightarrow n=3

Therefore the expression is non-negative for all real $n$ , with equality exactly at $n=3$ .

Why keep $\ge$ rather than $>$ ? The square can be zero, and there is no longer a positive constant added to it.

Check. At $n=3$ , $9-18+9=0$ ; at $n=2$ , $4-12+9=1$ . Both agree with the claimed bound and equality case.

Completing the square, parity and factorisation are all deduction tools. Later, deductions will also establish derivatives from first principles and formulas for arithmetic and geometric sums; the habit remains to justify each link.

Watch out

Wrong: “ $(n-3)^2>0$ for every real $n$ .” At $n=3$ , it equals zero. Right: write $(n-3)^2\ge0$ , then examine any added constant before deciding whether the final result is strictly positive.

Pearson's positivity proofs reward the algebra and its implication. Writing only the completed square leaves the crucial sign argument unstated. Now change the constant once more.

Proof by exhaustion

Exhaustion works when you can identify a complete finite set of cases and establish the claim in every one.

If $n$ is an integer with $1\le n\le4$ , the values of $n^2+n$ are $2, 6, 12, 20$ . Each is even, and there are no other permitted values of $n$ . Here checking four values really does prove the claim. Remove the bounded domain, and those four calculations are no longer enough.

Proof by exhaustion

Proof by exhaustion establishes a statement by checking every case in a complete finite set of cases. For example, a list of the allowed integers in a bounded interval can be exhaustive; an arbitrary selection of integers is not.

Begin by explaining why your list is complete. Otherwise, even a table of correct arithmetic might leave an unexamined case.

Worked example 3: every permitted prime

Question. Given that $p$ is prime and $3<p<25$ , prove by exhaustion that $(p-1)(p+1)$ is a multiple of $12$ .

Plan. List every prime in the interval and express each result as an integer multiple of $12$ .

Answer. The primes strictly between $3$ and $25$ are exactly $5, 7, 11, 13, 17, 19, 23$ . For these cases,

$p$	$(p-1)(p+1)$	Integer multiple
$5$	$4\times6=24$	$12\times2$
$7$	$6\times8=48$	$12\times4$
$11$	$10\times12=120$	$12\times10$
$13$	$12\times14=168$	$12\times14$
$17$	$16\times18=288$	$12\times24$
$19$	$18\times20=360$	$12\times30$
$23$	$22\times24=528$	$12\times44$

Each permitted prime gives a multiple of $12$ . Since the list covers every possible $p$ in the given interval, the result is proved by exhaustion.

Why list primes first? The domain contains primes, not every integer in the interval; the list identifies exactly the cases that the proof must cover.

Check. There are no omitted primes: $9, 15, 21$ are divisible by $3$ ; the remaining unlisted integers in the interval are even. The endpoint $3$ is excluded by the strict inequality.

The next example changes how the cases are listed: instead of individual numbers, use remainder classes. Infinitely many integers can fall into a finite number of classes. Every integer is $4k+r$ , with integer $k$ and exactly one of $r=0, 1, 2, 3$ , because division by $4$ leaves one of those remainders. This includes negative integers: $-1=4(-1)+3$ .

[DIAGRAM: asset_name: Square numbers split into groups of four; asset_slug: 9ma0-proof-square-remainders; caption: An even square splits into four equal squares; an odd square splits into four equal rectangles and one extra unit; description: A six by six unit square is split into four three by three squares, showing 36 equals four times 9. Beside it, a five by five unit square is split into four two by three rectangles around one central unit, showing 25 equals four times 6 plus 1. General labels give (2k) squared equals 4k squared and (2k plus 1) squared equals 4k(k plus 1) plus 1. The picture explains why a square leaves remainder zero or one on division by four]
An even square splits into four equal squares

The picture shows why remainders $0$ and $1$ are plausible. The algebra now checks a complete set of classes, so the proof is not restricted to the two pictured squares.

Worked example 4: every possible remainder

Question. Prove by exhaustion that the square of any integer leaves remainder $0$ or $1$ when divided by $4$ .

Plan. Write an arbitrary integer as $4k+r$ , then examine all four possible remainders $r$ .

Answer. Let $n=4k+r$ , where $k\in\mathbb Z$ and $r\in\{0, 1, 2, 3\}$ . Then

\begin{aligned} n^2&=(4k+r)^2 && \text{substitute the complete case form} \\ &=16k^2+8kr+r^2 && \text{expand} \\ &=4(4k^2+2kr)+r^2 && \text{separate a multiple of }4 \end{aligned}

The bracket is an integer, so only $r^2$ affects the remainder:

$r$	$r^2$	Remainder on division by $4$
$0$	$0=4\times0$	$0$
$1$	$1=4\times0+1$	$1$
$2$	$4=4\times1$	$0$
$3$	$9=4\times2+1$	$1$

All four possible classes have been checked. Therefore every integer square leaves remainder $0$ or $1$ on division by $4$ , as required.

Why use $4k+r$ rather than just $r$ ? It represents every integer in each class. Checking only the integers $0, 1, 2, 3$ would not prove the universal statement.

Check. For $n=-3$ , the square is $9=4\times2+1$ . For $n=6$ , it is $36=4\times9$ . Both are among the proved possibilities.

These divisibility and remainder results are not in the formula booklet: derive them from the cases. When completing a supplied proof, identify the cases still missing rather than repeating the ones already shown.

Watch out

Wrong: “Checking $n=0, 1, 2, 3$ proves the claim for all integers.” Right: check $n=4k, 4k+1, 4k+2, 4k+3$ , with $k\in\mathbb Z$ . Those forms cover the entire domain, not just four numbers.

The following question changes only the divisor, from $4$ to $3$ . Rebuild the complete list of remainders for that divisor.

Disproof by counterexample

One failure is enough to defeat an “always” claim, provided the failed case obeys the claim's assumptions.

The claim “every prime is odd” fails at $2$ : it is prime and even. The number $4$ would not be a counterexample, because it is not prime. Your example must enter through the assumptions before it can challenge the conclusion.

Counterexample

A counterexample is a case satisfying all the assumptions of a universal statement but making its conclusion false. It disproves the statement. For example, $2$ disproves “every prime is odd”; $4$ does not.

For a claim that an expression is prime, show a non-trivial factorisation of a value greater than $1$ , or show that the value is at most $1$ . An unexplained assertion that a number is “not prime” is less convincing than its factors.

Worked example 5: a prime-producing claim fails

Question. Disprove the statement: “ $n^2-n+1$ is prime for every positive integer $n$ .”

Plan. Find one permitted integer that makes the expression composite.

Answer. Take $n=5$ , which is a positive integer. Then

\begin{aligned} n^2-n+1&=5^2-5+1 && \text{substitute a permitted value} \\ &=21 && \text{evaluate} \\ &=3\times7 && \text{exhibit non-trivial factors} \end{aligned}

Thus the expression is not prime for $n=5$ , so the statement is false.

Why show factors? They establish exactly why the conclusion fails; choosing a permitted value alone does not disprove anything.

Check. Both $3$ and $7$ lie strictly between $1$ and $21$ , so this is a genuine factorisation proving compositeness. There is an even quicker counterexample: at $n=1$ , the value is $1$ , which is not prime.

Worked example 6 changes only the constant term, from $1$ to $2$ . The old boundary counterexample no longer works, so find a new failure.

Worked example 6: changing the constant

Question. Disprove the statement: “ $n^2-n+2$ is prime for every positive integer $n$ .”

Plan. Test a small positive integer and factorise the resulting value.

Answer. Take $n=2$ , a positive integer. Then

\begin{aligned} n^2-n+2&=2^2-2+2 && \text{substitute} \\ &=4 && \text{evaluate} \\ &=2\times2 && \text{a non-trivial factorisation} \end{aligned}

The value $4$ is composite, so $n=2$ is a counterexample and the statement is false.

Why not use $n=1$ ? Its value is now $2$ , which is prime. A successful example cannot disprove a universal statement.

Check. The input $n=2$ satisfies the positive-integer assumption. The input being prime is irrelevant: the claim concerns the output $n^2-n+2$ .

Sometimes the input must itself be prime. For “if $p$ is prime, then $2p+1$ is prime”, choose $p=7$ : it is prime, but $2p+1=15=3\times5$ . Both the input condition and the failed output matter. These polynomial claims and the counterexample method are not supplied as formula-booklet results.

Watch out

Wrong: “Take $p=9$ to disprove a claim about prime inputs.” That input is outside the domain. Right: select a prime input, such as $p=7$ above, and then show that the claimed output property fails.

The next claim changes the constant once more. You need only one valid counterexample, not a catalogue of failures.

Proof by contradiction

Contradiction proves a statement by following its opposite until that assumption forces an impossibility.

For a claim that a number is irrational, the opposite is that it is rational. A rational number can be written as $a/b$ , with integers $a$ and $b\ne0$ ; an irrational number cannot. For example, $3/5$ is rational. An endless decimal is not automatically irrational: $1/3=0.333\ldots$ is rational.

Proof by contradiction

In proof by contradiction, assume the negation of the statement to be proved, derive a conflict with a known fact or an assumption, then reject that negation and conclude the original statement.

For example, assuming a fraction is in lowest terms and then proving both numerator and denominator are even gives a precise contradiction.

Be exact about the negation. The opposite of “there is no solution” is “there is at least one solution”, not “every number is a solution”. The opposite of “ $x>0$ ” is “ $x\le0$ ”, which includes zero.

Before the irrationality proof, establish its parity step. If $a=2k+1$ is odd, then

\begin{aligned} a^2&=(2k+1)^2 && \text{substitute the odd form} \\ &=4k^2+4k+1 && \text{expand} \\ &=2(2k^2+2k)+1 && \text{an odd integer} \end{aligned}

An odd integer cannot have an even square. An even integer $a=2k$ has square $a^2=4k^2=2(2k^2)$ , which is even. Together these prove both directions of the following result.

Parity of integer squares

For any integer $a$ ,

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

An odd integer has an odd square. These claims concern integers; they do not classify arbitrary real numbers as even or odd.

Not in the formula booklet: learn it.

Now choose a lowest-terms fraction. Every rational number has one: cancel common factors until none remain. That choice is what makes “both even” impossible at the end.

Worked example 7: the irrationality of root two

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

Plan. Assume a lowest-terms fraction exists and show that its numerator and denominator must both be even.

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

\begin{aligned} a^2&=2b^2 && \text{square and multiply by }b^2 \\ a&=2k\quad(k\in\mathbb Z) && a^2\text{ even implies }a\text{ even} \\ 4k^2&=2b^2 && \text{substitute }a=2k \\ b^2&=2k^2 && \text{divide by }2 \end{aligned}

Thus $b^2$ is even, so $b$ is even. Both $a$ and $b$ have a factor of $2$ , contradicting the choice of a lowest-terms fraction. Therefore $\sqrt2$ is irrational.

Why require lowest terms? Without that condition, two even integers could represent an ordinary rational number: $2/4=1/2$ is no contradiction.

Check. The contradiction is “no common factor greater than $1$ ” versus “a common factor of $2$ ”. It does not depend on the decimal approximation $\sqrt2\approx1.414$ , which cannot establish irrationality.

Worked example 8 changes only the number under the root, from $2$ to $6$ . The first parity step survives, but the second needs an extra reason.

Worked example 8: adapting the contradiction

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

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

Answer. Suppose $\sqrt6=a/b$ , with positive integers $a, b$ having no common factor greater than $1$ . Then

\begin{aligned} a^2&=6b^2 && \text{square and clear the denominator} \\ a&=2k\quad(k\in\mathbb Z) && a^2\text{ is even} \\ 4k^2&=6b^2 && \text{substitute }a=2k \\ 2k^2&=3b^2 && \text{divide by }2 \end{aligned}

The left side is even, so $3b^2$ is even. If $b$ were odd, $b^2$ would be odd and $3b^2$ would be odd. Hence $b$ is even. Both $a$ and $b$ are therefore even, contradicting their having no common factor greater than $1$ . Thus $\sqrt6$ is irrational.

Why mention that $3$ is odd? From an even product, you may conclude that the other factor is even only when the known factor is odd. “ $2b^2$ is even” alone would say nothing about $b$ .

Check. The odd-square expansion above proves the parity claim used for $b$ . Every division was by a non-zero constant, and the argument ended in the same explicit lowest-terms contradiction.

Neither irrationality result is supplied in the formula booklet: reconstruct the proof rather than quoting a decimal display. This is also how you adapt contradiction to an unfamiliar statement: identify the exact assumption that your final line must break.

Watch out

Wrong: “Both $a$ and $b$ are even, so a contradiction.” That is incomplete if you never required lowest terms. Right: state that $a/b$ is in lowest terms at the start, then name the common factor that contradicts that condition.

The next question changes the radicand from $6$ to $10$ . The odd factor in the denominator argument changes with it.

Infinitely many primes

To prove that the primes never run out, assume a finite list contains them all and construct a number that the list cannot account for.

Return to the opening idea. The product of listed primes is divisible by every prime on the list; adding $1$ leaves remainder $1$ on division by each of them. That small change defeats all the listed divisors at once.

You already know

Every integer greater than $1$ has a prime divisor. If it is prime, it divides itself. If it is composite, choose its smallest divisor greater than $1$ ; that divisor must be prime, since a proper factor of it would be an even smaller divisor.

This fact is the safety net in the proof. The new number does not have to be prime; it only has to have a prime divisor missing from the list.

Worked example 9: defeating a specified list

Question. A claim says that $2, 3, 5, 7$ are all the primes. Use a contradiction to disprove it.

Plan. Multiply the alleged complete list and add $1$ , then consider a prime divisor of the new number.

Answer. Suppose the list is complete. Form

\begin{aligned} P&=2\times3\times5\times7=210 && \text{a multiple of each listed prime} \\ N&=P+1=211 && \text{add }1 \end{aligned}

For each listed prime $p$ , the integer $P$ is divisible by $p$ , so $N=P+1$ leaves remainder $1$ . Thus none of $2, 3, 5, 7$ divides $N$ . But $N>1$ , so it has a prime divisor. That divisor is absent from the list, contradicting completeness. Hence the list cannot contain all primes.

Why use a prime divisor instead of asserting that $211$ is prime? The divisor argument works immediately and will still work when the constructed number is composite.

Check. Explicitly, $211=2(105)+1=3(70)+1=5(42)+1=7(30)+1$ . Every listed divisor leaves remainder $1$ , as claimed.

Worked example 10 changes the list from four specified primes to an arbitrary finite list. The same construction will now rule out every possible finishing point.

Worked example 10: no finite list can be complete

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

Plan. Assume a complete finite list, multiply its entries and add $1$ , then force a prime divisor outside the list.

Answer. Suppose there are finitely many primes, listed as $p_1, p_2,\ldots, p_k$ . Set

\begin{aligned} P&=p_1p_2\cdots p_k && \text{multiply the alleged complete list} \\ N&=P+1 && \text{construct an integer greater than }1 \end{aligned}

For any listed prime $p_i$ ,

N=p_i\left(\frac{P}{p_i}\right)+1

Here $P/p_i$ is an integer because $p_i$ is a factor of $P$ . Therefore $N$ leaves remainder $1$ when divided by $p_i$ , so no listed prime divides $N$ . Since $N>1$ , it has a prime divisor $q$ . This $q$ is not on the list, contradicting the assumption that all primes were listed. Therefore there are infinitely many primes.

Why add $1$ ? Every listed prime divides $P$ . If one also divided $P+1$ , it would divide their difference $1$ , which a prime cannot do.

Check. With the finite list $2, 3, 5$ , the construction gives $31$ , agreeing with the opening calculation. More importantly, the symbolic argument above works for any finite list, so it proves infinity rather than just finding one more example.

Here is a useful surprise: multiplying consecutive primes and adding $1$ does not always give a prime. For the first six primes,

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

Both prime factors are new, so the proof succeeds anyway. This is why the distinction between “a new prime” and “a number with a new prime factor” matters. The infinity result and this construction are not supplied in the formula booklet.

Watch out

Wrong: “ $P+1$ is prime because none of the listed primes divides it.” A different prime might divide it, as $59$ divides $30031$ . Right: $P+1>1$ has a prime divisor, and that divisor cannot be in the supposed complete list.

You can now choose a method with a reason: use deduction for a general chain, exhaustion for complete cases, a counterexample for one failure, and contradiction when the negation gives you something useful to work with. They can also work together in one argument. The final question varies the construction by squaring the product before adding $1$ .

Quick Recap

State the assumptions, justify the chain of reasoning, and finish with the requested conclusion for the stated domain.
Deduction uses general facts; exhaustion checks a complete finite set of cases, which may be remainder classes.
A counterexample must satisfy the assumptions and break the conclusion. One valid failure defeats a universal statement.
Contradiction assumes the exact negation and derives an explicit impossibility; lowest terms makes the irrationality argument work.
A product of listed primes plus $1$ has a prime divisor outside the list, whether or not the constructed number is prime.

You can never finish the opening list: any proposed finite list leads to a missing prime divisor, so there are infinitely many primes.

Last Accessed

Pure Mathematics (Papers 1 and 2)

Statistics (Paper 3, Section A)

Mechanics (Paper 3, Section B)

Pure 1.1 - Structure of mathematical proof

What a proof must do

Symbols carry logical meaning

Proof by deduction

Proof by exhaustion

Disproof by counterexample

Proof by contradiction

Infinitely many primes

Quick Recap

Learn faster with Nova