HSC Study

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?

Select one answer

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?

Select one answer

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?

Select one answer

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?

Select one answer

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?

Select one answer

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?

Select one answer

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.