CBSE Math Revision Start revising
Problem-solving strategy

Proof techniques

A proof is an argument that leaves no case unchecked. The main tools are: direct proof (chain facts together), contradiction (assume the opposite and reach something impossible), the contrapositive (prove ‘not B implies not A’ instead of ‘A implies B’), induction (prove it for 1, then show each case gives the next) and construction (show something exists by building it).

Competition answers are often a number, but the reason the number is right is a proof: a bound plus an example, or a full list of cases.

When to try it

  • The question says ‘prove’, ‘show that’, ‘find all’ or ‘for every’.
  • You have found an answer and need to be sure there are no others.
  • A statement is claimed for every whole number n.

Watch out: Checking examples is not a proof, and neither is an argument that only works for the cases you happened to try.

Two worked examples

Try each one first. The hints and the full solution are underneath.

Problem J44

Junior · Number theoryShort answer

What is the smallest whole number that has exactly 5 factors (including 1 and itself)?

Hint

Most numbers have an even number of factors, because factors come in pairs. When does a number have an odd number?

Second hint

Factors pair up as d and n/d, except when d = n/d. So the number is a perfect square. Check the squares in order.

Full worked solution

Answer: 16

  1. Factors come in pairs d and n/d. The count is odd only when one factor is paired with itself, i.e. n is a perfect square.
  2. Check squares: 4 has 3 factors (1, 2, 4); 9 has 3; 16 has 1, 2, 4, 8, 16: five factors.
  3. So the smallest is 16.
  4. In general a number with exactly 5 factors is p4 for a prime p (since 5 is prime, the formula (a + 1)(b + 1)… = 5 forces one prime to the 4th power); the smallest is 24.

Why this works: Pairing each factor with its partner explains why non-squares have an even number of factors, and narrows the search to squares.

Where it leads: A number with exactly 3 factors is the square of a prime. Which numbers have exactly 4 factors? (p3 or pq.)

Strategy: Proof techniques, Extremal principle

Problem I41

Intermediate · Number theoryShort answer

How many whole numbers from 1 to 100 have exactly 3 positive factors?

Hint

Factors pair up as d and n/d. When can there be an odd number of them?

Second hint

Only perfect squares have an odd number of factors. Which squares have exactly 3?

Full worked solution

Answer: 4

  1. Factors pair up as d and n/d, so a number has an odd number of factors only if it is a perfect square.
  2. If n = m2 has exactly 3 factors they are 1, m and m2, so m has no factors other than 1 and itself: m is prime.
  3. Squares of primes up to 100: 4, 9, 25, 49.
  4. So 4 numbers.

Why this works: Pairing factors explains odd counts, and then the factor list 1, m, m2 forces m to be prime.

Where it leads: The number of factors of paqb… is (a + 1)(b + 1)…; exactly 3 factors needs (a + 1)(b + 1)… = 3, i.e. p2.

Strategy: Proof techniques, Spot the pattern and generalise

Practise: 55 problems that use proof techniques

Other strategies

Organised cases · Count the opposite · Working backwards · Invariants · Extremal principle · Pigeonhole principle · Parity and remainders · Symmetry · Spot the pattern and generalise

All strategy guides · Extension & competition maths