Mini-Lesson

Proof

2 missions. Guess, learn, then check. Your place is saved.

Mission 1 $n^{2} + n + 41$ n²+n+41 is prime for $n = 0$ n=0 to $39$ 39. Is it always prime?
Mission 2How can you prove there are infinitely many primes without a list?

The specification points and sources are listed under the lesson: see Sources.

Mission 1

$n^{2} + n + 41$ n²+n+41 is prime for $n = 0$ n=0 to $39$ 39. Is it always prime?

Make a guess: $n^{2} + n + 41$ n²+n+41 is prime for $n = 0$ n=0 to $39$ 39. Is it always prime?

Proof · deduction, exhaustion, counterexample

What a proof is

A proof uses logical steps from assumptions to a conclusion, valid in every case.
Examples are not a proof: a statement can hold thousands of times and still fail.
$P \Rightarrow Q$ P ⇒ Q: " $P$ P implies $Q$ Q" (if $P$ P then $Q$ Q). $P \Leftarrow Q$ P Leftarrow Q: " $P$ P is implied by $Q$ Q". $P \Leftrightarrow Q$ P Leftrightarrow Q: each implies the other ("if and only if").
If $P \Rightarrow Q$ P ⇒ Q, then $P$ P is sufficient for $Q$ Q and $Q$ Q is necessary for $P$ P.
$\equiv$ ≡: identically equal (true for all values). $∴$ ∴: therefore.
End with a concluding statement.

Quick check

?Which symbol goes in the gap to make a true statement?

x^{2} = 9__x = - 3

Proof · deduction, exhaustion, counterexample

Proof by deduction

Deduction: start from a general case and use algebra so the argument covers every case at once.
Write integers in general form: any integer $n$ n; consecutive integers $n$ n, $n + 1$ n+1, $n + 2$ n+2; even $2 a$ 2a; odd $2 a + 1$ 2a + 1 (with $a$ a an integer).
To show "is a multiple of 3", reach $3 \times (an integer)$ 3 × (an integer): $n + (n + 1) + (n + 2) = 3 (n + 1)$ n + (n+1) + (n+2) = 3(n+1).
Two odd numbers: $(2 a + 1) + (2 b + 1) = 2 (a + b + 1)$ (2a+1) + (2b+1) = 2(a+b+1), which is even. Use different letters $a$ a, $b$ b, or you have only proved it for equal numbers.

Worked example Proof · deduction, exhaustion, counterexample

Showing $n^{3} - n$ n³ − n is a multiple of 6

Question

Prove that

n^{3} - n

is a multiple of 6 for every integer

n

.

1
Factorise: $n^{3} - n = n (n^{2} - 1) = (n - 1) n (n + 1)$ n³ − n = n(n² − 1) = (n−1)n(n+1)
2
Interpret: this is the product of three consecutive integers.
3
Among any two consecutive integers one is even, so 2 is a factor.
4
Among any three consecutive integers one is a multiple of 3, so 3 is a factor.
5
Conclude: 2 and 3 are both factors and share no common factor, so $n^{3} - n$ n³ − n is a multiple of 6 for every integer $n$ n.

Answer

n^{3} - n = (n - 1) n (n + 1)

is divisible by both 2 and 3, so it is a multiple of 6.

⚠️ Watch out

testing

n = 2, 3, 4

and getting 6, 24, 60 is not a proof. The factorised form covers every

n

.

Calculate

?Let

n

be an integer. Write the sum of the five consecutive integers

n, n + 1, n + 2, n + 3, n + 4

in factorised form. What is the greatest whole number that always divides this sum?

Proof · deduction, exhaustion, counterexample

Exhaustion and counterexample

Proof by exhaustion: split all possibilities into a finite set of cases and prove each one, e.g. $n$ n even or odd, or $n = 3 m$ n = 3m, $3 m + 1$ 3m+1, $3 m + 2$ 3m+2.
Every case must be covered: miss one and the proof fails.
Disproof by counterexample: to show "if $P$ P then $Q$ Q" is false, find one value where $P$ P is true and $Q$ Q is false.
One counterexample is enough. No number of examples proves a "for all" statement.

Worked example Proof · deduction, exhaustion, counterexample

Squares and multiples of 3

Question

Prove by exhaustion that the square of any integer is either a multiple of 3 or one more than a multiple of 3.

1
Every integer is $3 m$ 3m, $3 m + 1$ 3m + 1 or $3 m + 2$ 3m + 2 for some integer $m$ m, so check these three cases.
2
Case 1: $(3 m)^{2} = 9 m^{2} = 3 (3 m^{2})$ (3m)² = 9m² = 3(3m²), a multiple of 3.
3
Case 2: $(3 m + 1)^{2} = 9 m^{2} + 6 m + 1 = 3 (3 m^{2} + 2 m) + 1$ (3m+1)² = 9m² + 6m + 1 = 3(3m² + 2m) + 1
4
Case 3: $(3 m + 2)^{2} = 9 m^{2} + 12 m + 4 = 3 (3 m^{2} + 4 m + 1) + 1$ (3m+2)² = 9m² + 12m + 4 = 3(3m² + 4m + 1) + 1
5
Conclude: all integers are covered, so $n^{2}$ n² is always $3 k$ 3k or $3 k + 1$ 3k + 1.

Answer

In every case

n^{2} = 3 k

or

n^{2} = 3 k + 1

for an integer

k

, so the statement is true.

⚠️ Watch out

Case 3 gives

+ 4

at first. Write

4 = 3 + 1

and move the 3 into the bracket to see the form

3 k + 1

.

Calculate

?A student claims: "If

p

is a prime number, then

2^{p} - 1

is prime." Find the smallest value of

p

that is a counterexample to this claim.

Sort it

?Which method is the natural one for each task?

Tap a statement, then tap the group it belongs in. Then press Check.

Mission check

?

n^{2} + n + 41

is prime for

n = 0

to

39

. Is it always prime?

Mission 2

How can you prove there are infinitely many primes without a list?

Make a guess: How can you prove there are infinitely many primes without a list?

Proof · contradiction (A-level only)

How proof by contradiction works (A2 only)

To prove a statement, assume it is false (assume its negation).
Reason correctly from that assumption until you reach something impossible: a contradiction.
The assumption must have been false, so the original statement is true.
Write the negation carefully. "There is no greatest even number" becomes "there is a greatest even number, $N$ N".
Finish with "This is a contradiction, so …" and restate the result.

Quick check

?You want to prove by contradiction that "there are infinitely many primes". What do you assume at the start?

Worked example Proof · contradiction (A-level only)

There is no greatest even number

Question

Prove by contradiction that there is no greatest even number.

1
Assume the opposite: there is a greatest even number, $N$ N.
2
$N$ N is even, so $N = 2 k$ N = 2k for some integer $k$ k.
3
Then $N + 2 = 2 k + 2 = 2 (k + 1)$ N + 2 = 2k + 2 = 2(k+1), which is even.
4
But $N + 2 > N$ N + 2 > N, so $N$ N is not the greatest even number: a contradiction.

Answer

The assumption is false, so there is no greatest even number.

⚠️ Watch out

showing that 1,000,000 is beaten by 1,000,002 is an example, not a proof. The argument must work for any

N

.

Proof · contradiction (A-level only)

Tools for the $2$ √2 proof (A2 only)

A rational number can be written as $\frac{a}{b}$ a/b with integers $a$ a, $b$ b ( $b \neq = 0$ b ≠ 0) and no common factor (lowest terms). An irrational number cannot.
Key fact: if $a^{2}$ a² is even, then $a$ a is even.
Why: if $a$ a were odd, $a = 2 k + 1$ a = 2k + 1, then $a^{2} = 4 k^{2} + 4 k + 1 = 2 (2 k^{2} + 2 k) + 1$ a² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd.
In the $2$ √2 proof, the contradiction is that $a$ a and $b$ b turn out to share a factor of 2.

Worked example Proof · contradiction (A-level only)

$2$ √2 is irrational

Question

Prove by contradiction that

2

is irrational.

1
Assume $2$ √2 is rational: $2 = \frac{a}{b}$ √2 = a/b, with $a$ a, $b$ b integers with no common factor.
2
Square and rearrange: $a^{2} = 2 b^{2}$ a² = 2b², so $a^{2}$ a² is even, so $a$ a is even. Write $a = 2 c$ a = 2c.
3
Substitute: $4 c^{2} = 2 b^{2}$ 4c² = 2b², so $b^{2} = 2 c^{2}$ b² = 2c². Then $b^{2}$ b² is even, so $b$ b is even.
4
Both $a$ a and $b$ b are even, so they share the factor 2: this contradicts "no common factor".

Answer

The assumption is false, so

2

is irrational.

⚠️ Watch out

the proof needs "no common factor" in step 1. Without it there is nothing to contradict.

Quick check

?To prove

3

is irrational, you assume

3 = \frac{a}{b}

, where

a

and

b

are integers with no common factor. Which equation follows directly?

Proof · contradiction (A-level only)

Infinitely many primes (A2 only)

Assume there are only finitely many primes: $p_{1}, p_{2}, \dots, p_{n}$ p₁, p₂, …, pₙ.
Let $N = p_{1} p_{2} \dots p_{n} + 1$ N = p₁ p₂ ⋯ pₙ + 1.
Dividing $N$ N by any $p_{i}$ pᵢ leaves remainder 1, so no prime on the list divides $N$ N.
But $N > 1$ N > 1, so $N$ N has at least one prime factor (possibly $N$ N itself). That prime is not on the list: a contradiction.
So there are infinitely many primes. $N$ N itself need not be prime.

Calculate

?In the proof, suppose the list of primes were 2, 3, 5, 7, 11. Then

N = 2 \times 3 \times 5 \times 7 \times 11 + 1

. What is the remainder when

N

is divided by 7?

Calculate

?A student says: "In this proof,

N

is always a new prime." Test it:

N = 2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031

. Find the smallest prime factor of 30031.

Mission check

?How can you prove there are infinitely many primes without a list?

Recap

Big ideas

A proof covers every case through logical steps; examples alone never prove a "for all" statement.
Deduction uses general algebra ( $n$ n, $2 a + 1$ 2a+1, $3 m + 2$ 3m+2); exhaustion splits into a finite set of cases and checks each.
One counterexample, where the "if" part holds and the conclusion fails, disproves a statement.
Proof by contradiction: assume the negation, reason correctly to something impossible, conclude the original statement is true.
$2$ √2: assume $\frac{a}{b}$ a/b in lowest terms, show $a$ a and $b$ b are both even.
Primes: assume a finite list, consider their product plus 1; it has a prime factor not on the list.

🏆

Mini-lesson complete!

⭐⭐⭐

You've worked through Proof for CCEA GCE Mathematics (2210). 🎉

Mission 1 $n^{2} + n + 41$ n²+n+41 is prime for $n = 0$ n=0 to $39$ 39. Is it always prime?
Mission 2How can you prove there are infinitely many primes without a list?

Your stars: 0 / 0

Next: test yourself in the Verify stage.

📣 Smashed it? Share your score

Challenge a mate to beat your stars, or show a parent how you got on.

→ Back to A-Level Mathematics · CCEA

Specification points and sources for this lesson are listed at the bottom of the page.

Proof

n2+n+41n²+n+41 is prime for n=0n=0 to 3939. Is it always prime?

What a proof is

Proof by deduction

Showing n3−nn³ − n is a multiple of 6

Exhaustion and counterexample

Squares and multiples of 3

How can you prove there are infinitely many primes without a list?

How proof by contradiction works (A2 only)

There is no greatest even number

Tools for the 2​√2 proof (A2 only)

2​√2 is irrational

Infinitely many primes (A2 only)

Big ideas

Mini-lesson complete!

📣 Smashed it? Share your score

$n^{2} + n + 41$ n²+n+41 is prime for $n = 0$ n=0 to $39$ 39. Is it always prime?

Showing $n^{3} - n$ n³ − n is a multiple of 6

Tools for the $2$ √2 proof (A2 only)

$2$ √2 is irrational