Parity and remainders
Odd and even (parity) is the simplest invariant, and remainders on division by small numbers are the next simplest. A sum of two numbers is even when they are both odd or both even; a square leaves remainder 0 or 1 on division by 3 or 4; the units digit of a power repeats in a short cycle.
Working with remainders rules out whole families of answers at once and makes huge numbers small.
When to try it
- Huge numbers or powers appear (units digits, last two digits, remainders).
- You suspect something is impossible: try remainders mod 2, 3, 4, 5, 8 or 9.
- The problem involves alternating colours, turns or sides.
Watch out: A remainder test can rule things out, but passing it proves nothing: a number with the right remainder still need not be a square.
Worked example
Two opposite corner squares are cut from an 8 by 8 chessboard. Can the 62 squares left be covered by 31 dominoes, each covering two squares next to each other?
Show the solution
- Colour the board as a chessboard. Every domino covers one black and one white square.
- Opposite corners are the same colour, so the board left has 30 squares of one colour and 32 of the other.
- 31 dominoes would cover 31 of each colour, so it cannot be done.
Answer: No
Practise: 45 problems that use parity and remainders
Other strategies
Organised cases · Count the opposite · Working backwards · Invariants · Extremal principle · Pigeonhole principle · Symmetry · Spot the pattern and generalise · Proof techniques