Proofs About Numbers and Proof by Contradiction
Direct proofs about integers using general forms such as 2k + 1 and 10a + b, proof by cases, and proof by contradiction, including the irrationality of √2 and log₂5 and the infinitude of primes.
50 min · Proof
Assumes you have read The Language of Proof.
The full teaching. Start here.
The short version
- General forms:
- even is , odd is ;
- a multiple of is , and every integer is , or ;
- a two-digit number with digits is .
- Use different letters for independent numbers.
- Direct proof: start from what you know and reach the claim. Never start from the claim itself.
- Cases: split into cases that cover every possibility, and prove each.
- Contradiction: assume the statement is false, and deduce something impossible.
- Irrationality:
- : assume in lowest terms and show both and are even.
- : assume , which gives (even equals odd).
Direct proofs with integers
A proof about "all integers" or "all odd numbers" must work for every one of them. So you represent a general member with a letter:
- even: ; odd: (with );
- divisible by : ;
- consecutive integers: , , (or , , for symmetry);
- a number with digits : .
Then use algebra to reach the required form.
Worked example5 marks
Direct proofs about integers
(a) Prove that the sum of two odd integers is even. (b) Prove that the square of any odd integer is one more than a multiple of .
(a) Represent generally
Two independent odd numbers need two letters.
Let the numbers be and with .
(a) Add
Reach the form 2(integer).
, and is an integer, so the sum is even.
(b) Expand
Look for a factor of 8.
.
(b) Find the extra factor 2
Consecutive integers.
One of and is even, so for an integer . Hence .
Answer
(a) The sum is , which is even. (b) .
Is that answer sensible?
(b) , , . These examples agree with the proof but do not replace it.
CheckpointAnswer before reading on.
Which is the standard way to write a general odd integer in a proof?
Hint 1Odd means one more than an even number.
Hint 2Use an integer parameter.
Hint 3.
CheckpointAnswer before reading on.
A student proves "the sum of two even numbers is even" by writing the numbers as 2k and 2k. What is wrong?
Hint 1Are the two numbers the same?
Hint 2Generality.
Hint 3Use 2a and 2b.
CheckpointAnswer before reading on.
Prove that the sum of any three consecutive integers is divisible by 3.
Hint 1Let the integers be .
Hint 2Add them.
Hint 3.
CheckpointAnswer before reading on.
Prove that the product of two odd integers is odd.
Hint 1 and .
Hint 2Use different letters.
Hint 3.
CheckpointAnswer before reading on.
Prove that the difference between a two-digit number and the number formed by reversing its digits is divisible by 9.
Hint 1.
Hint 2Reverse: .
Hint 3.
Exam question
Standard · about 4 min
3 marks
Prove that the square of any odd integer is one more than a multiple of 8.
Hint 1.
Hint 2 is even.
Hint 3.
Where students lose marks on this one
Stopping at 4k(k + 1) + 1.
Why it happens: Not justifying the extra factor of 2.
Explain why k(k + 1) is even.
Written for this site.
Exam question
Standard · about 4 min
3 marks
Prove that is divisible by for every integer .
Hint 1Factorise.
Hint 2.
Hint 3Consecutive integers contain a multiple of 2 and of 3.
Where students lose marks on this one
Checking n = 1, 2, 3 only.
Why it happens: Using examples as proof.
Give a general argument.
Written for this site.
Exam question
Standard · about 4 min
3 marks
Prove that a three-digit number is divisible by 9 if and only if the sum of its digits is divisible by 9.
Hint 1.
Hint 2.
Hint 3Both directions.
Where students lose marks on this one
Only proving one direction.
Why it happens: Ignoring iff.
iff needs both directions.
Written for this site.
Proof by cases
When a single form will not do, split into cases that together cover everything. For remainders on division by , every integer is , or . For parity, every integer is even or odd.
CheckpointAnswer before reading on.
Prove that for every integer , leaves remainder or when divided by .
Hint 1Proof by cases.
Hint 2, or .
Hint 3Square each.
Exam question
Standard · about 3 min
2 marks
Prove that if is odd for integers and , then exactly one of and is odd.
Hint 1Cases.
Hint 2Both even or both odd gives an even sum.
Hint 3Contrapositive.
Where students lose marks on this one
Only checking both even.
Why it happens: Missing a case.
Both odd also gives even.
Written for this site.
Common mistake
To prove x² + 1 ≥ 2x: x² + 1 ≥ 2x ⇒ (x − 1)² ≥ 0, which is true, so done.
Why it happens: Starting from the result and reaching something true proves nothing.
False statements can also lead to true ones (). Start from a known fact and work forward: . Or write at every step and make sure each step really is reversible.
CheckpointAnswer before reading on.
To prove , a student writes: ", which is true." What is the flaw?
Hint 1What did they start from?
Hint 2Direction of the arrows.
Hint 3Reverse the chain.
Proof by contradiction
To prove : assume , reason correctly, and reach something impossible, such as being even, or a fraction in lowest terms having a common factor. Since correct reasoning from gives nonsense, is false and is true.
Contradiction is the natural tool for "there is no …" and "… is irrational" statements. Showing something does not exist is hard directly, but assuming it does gives you something to work with.
Worked example6 marks
Two irrationality proofs
Prove that (a) is irrational; (b) is irrational.
(a) Assume the opposite, in lowest terms
This is what will be contradicted.
Suppose with integers , , and no common factor.
(a) p is even
Square and rearrange.
, so is even. If were odd, would be odd, so is even: .
(a) q is even: contradiction
Substitute back.
, so is even too. Then is a common factor of and , contradicting lowest terms.
(b) Assume rational
log₂5 > 0, so p, q > 0.
Suppose with positive integers . Then , so .
(b) Parity
Even cannot equal odd.
is even because , and is odd. Contradiction.
Answer
Both assumptions lead to contradictions, so and are irrational.
Is that answer sensible?
In (b), the same argument fails for , as it should: has solutions (, ), since both sides are even.
CheckpointAnswer before reading on.
To prove " is irrational" by contradiction, what do you assume?
Hint 1Assume the negation.
Hint 2Rational means p/q.
Hint 3Lowest terms.
CheckpointAnswer before reading on.
Why does deriving a contradiction prove the original statement?
Hint 1What assumption produced it?
Hint 2A statement or its negation is true.
Hint 3The negation is impossible.
CheckpointAnswer before reading on.
Which statement is false?
Hint 1Look for a cancelling example.
Hint 2.
Hint 3Counter-example.
Exam question
Standard · about 5 min
3 marks
Prove that is irrational.
Hint 1Assume in lowest terms.
Hint 2, so is even.
Hint 3Then q is even too.
Where students lose marks on this one
Not stating "lowest terms".
Why it happens: Having nothing to contradict.
The contradiction is with the common-factor assumption.
Written for this site.
Exam question
Harder · about 6 min
4 marks
(a) Prove that if is divisible by , then is divisible by . (b) Hence prove that is irrational.
Hint 1(a) Contrapositive with cases 3k + 1, 3k + 2.
Hint 2(b) .
Hint 3Both divisible by 3.
Where students lose marks on this one
Using "p² divisible by 3 ⇒ p divisible by 3" without proof.
Why it happens: Assuming the lemma.
Part (a) is exactly that lemma.
Written for this site.
Exam question
Standard · about 5 min
3 marks
Prove that is irrational.
Hint 1Assume , .
Hint 2.
Hint 3Even = odd.
Where students lose marks on this one
Allowing p = 0.
Why it happens: Not justifying why 2^p is even.
log₂5 > 0 gives p ≥ 1.
Written for this site.
Exam question
Harder · about 5 min
3 marks
Prove that is irrational.
Hint 1.
Hint 2.
Hint 3Odd = even.
Where students lose marks on this one
Writing 2^p = 3^q.
Why it happens: Mixing up base and argument.
log_b a = p/q ⇔ b^(p/q) = a.
Written for this site.
Exam question
Standard · about 4 min
3 marks
Prove that the sum of a rational number and an irrational number is irrational.
Hint 1Let rational, irrational.
Hint 2Suppose rational.
Hint 3.
Where students lose marks on this one
Claiming the sum of two irrationals is irrational too.
Why it happens: Overgeneralising.
√2 + (−√2) = 0.
Written for this site.
Exam question
Standard · about 3 min
2 marks
Prove that there are no integers with .
Hint 1Factor the left side.
Hint 2.
Hint 3Even = odd.
Where students lose marks on this one
Trying values of a and b.
Why it happens: Searching instead of proving.
No finite search proves non-existence.
Written for this site.
Exam question
Harder · about 4 min
3 marks
Prove by contradiction that there are no positive integers with .
Hint 1.
Hint 2Both factors positive integers.
Hint 3Both equal , so .
Where students lose marks on this one
Allowing x − y = −1.
Why it happens: Ignoring sign.
x + y > 0 forces x − y > 0.
Written for this site.
Exam question
Harder · about 5 min
3 marks
Prove that there are infinitely many primes.
Hint 1Suppose finitely many: p₁, …, pₖ.
Hint 2.
Hint 3Remainder 1 on division by each.
Where students lose marks on this one
Claiming N itself must be prime.
Why it happens: Overstating.
2·3·5·7·11·13 + 1 = 30031 = 59 × 509.
Written for this site.
What lifts this to a Band 6
Write the structure of a contradiction proof explicitly: "Suppose, for contradiction, that …", then the working, then "This contradicts …, so the assumption is false and …". In irrationality proofs, markers look specifically for "in lowest terms" (or "") in the assumption, because without it there is nothing to contradict.
Irrational sums of surds
Is irrational? Suppose it equals a rational . Squaring gives , so would be rational. But is irrational: if in lowest terms, then is even, so . Then , so . The left side is even, so is even, which forces to be even (an odd makes odd). Both and are even, contradicting lowest terms. Chaining contradictions like this, where one irrationality result is used to prove another, is a common pattern in harder questions.