Check every box#
You have to check that every sock in a drawer is clean, and there are far too many to go through one at a time. But you know every sock in there is black, white or grey. Nothing else.
Then you only need three checks. Every black sock is clean, every white sock is clean, every grey sock is clean — and you are done, because there is nothing left over.
That is a proof by cases. Split what you are talking about into a finite list of situations, prove the claim in each one, and conclude it always holds.
The list of boxes must be exhaustive — every single object has to land in at least one of them. Miss a color of sock and the proof says nothing about it. That is the only way a proof by cases fails, and it fails silently.
Where the boxes come from#
For whole numbers you never have to invent the boxes. Division hands them to you.
Pick any number m. Divide any whole number n by m and you get a remainder, and that remainder is always one of 0, 1, 2, …, m − 1. Divide by 3 and the remainder is 0, 1 or 2 — never anything else. So every whole number lands in exactly one of m boxes.
Written formally: n = qm + r with 0 ≤ r < m. That is the division algorithm, and it is the engine of this whole topic.
The shorthand n ≡ r (mod m) is read “n leaves remainder r when divided by m”. Pick m, get m boxes, check them all. The number of cases is m — not two, not “a few”, not however many occurred to you.
Even and odd is just two boxes#
Splitting into even and odd feels like the default because it is the first split anyone learns. But it is only the m = 2 case, and it tells you about nothing except divisibility by 2.
If a claim is about dividing by 3, even-and-odd is useless: 3 and 4 sit on opposite sides of that split and neither fact is relevant. Match the split to the claim.
| The claim is about… | Split by | How many boxes |
|---|---|---|
| even/odd, or dividing by 2 | 2 | 2 |
| dividing by 3 | 3 | 3 |
| squares, sums of two squares | 4 | 4 |
| odd squares, forms like x² + 2y² | 8 | 8 |
| fifth powers | 5 | 5 |
Worked example — 3 divides n³ − n#
Claim. For every whole number n, 3 divides n³ − n.
Factor first: n³ − n = (n − 1) · n · (n + 1). Now split by the remainder when n is divided by 3, which gives exactly three boxes.
- Remainder 0. Then 3 divides n, so it divides the product.
- Remainder 1. Then n − 1 has remainder 0, so 3 divides n − 1, so it divides the product.
- Remainder 2. Then n + 1 has remainder 0, so 3 divides n + 1, so it divides the product.
Three boxes, every whole number in one of them, claim true in each. So it holds for all n. ∎
Notice what made that short: factoring before splitting. Three numbers in a row must contain a multiple of 3, and the case split is just that observation written out carefully.
The squares tables worth memorizing#
Squares are wildly restricted by remainders, and that restriction powers most “this is impossible” proofs. Work these out once and keep them.
Divided by 4:
| n leaves remainder | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| n² leaves remainder | 0 | 1 | 0 | 1 |
A perfect square always leaves remainder 0 or 1 when divided by 4. Never 2, never 3.
Divided by 8 the picture is finer, and separates odd squares from even ones completely:
| n | odd | even, n/2 odd | even, n/2 even |
|---|---|---|---|
| n² mod 8 | 1 | 4 | 0 |
The odd case is worth seeing derived, because it does real work. Write n = 2m + 1. Then n² = 4m² + 4m + 1 = 4m(m + 1) + 1. Of any two numbers in a row, one is even, so m(m + 1) is even and 4m(m + 1) is a multiple of 8. So every odd square leaves remainder 1 when divided by 8.
Killing an equation with a remainder#
To show an equation has no whole-number solutions, find a remainder that the two sides can never share.
Take x² + y² = 3z² with x, y, z not all zero. Look at everything divided by 4. Each square is 0 or 1, so the left side is 0, 1 or 2 — never 3. Work through what the right side can be, and the two sides cannot match. No solutions exist, and you never had to search for any.
An equation says two things are equal. Equal numbers leave equal remainders. So find one m where the two sides can never leave the same remainder, and the equation has no solutions at all. One well-chosen m settles infinitely many cases at once.
When some boxes work and others do not#
Sometimes the claim is true in some boxes and false in others. That is not a failed proof — it is a sharper result, and you should state it that way.
“n² + 1 is divisible by 5” is false for most n, but working through the five boxes shows it holds exactly when n leaves remainder 2 or 3. The case split turned a vague claim into a precise one. Report which boxes work instead of calling the whole claim false.
Where these go wrong#
- Boxes that do not cover everything. The only real way this method fails. Say out loud why every object lands somewhere.
- Reaching for even/odd out of habit. It only ever tells you about dividing by 2. Match the split to the claim.
- Too many boxes. Splitting by 6 when 3 would do doubles your work and your chance of a slip.
- Not factoring first. The n³ − n proof is three lines after factoring and a mess before it.
- Proving one case and waving at the rest. “Similarly” is only acceptable when the cases really are symmetric, and you should say why.
- Concluding “false” when you mean “sometimes”. If some boxes work, say which.
- Forgetting that remainders are never negative. Dividing by 3, the boxes are 0, 1, 2 — not −1, 0, 1.
Test yourself in the free Kestrel Exams app
Discrete Math practice is free and works offline — topic-selectable drills on divisibility, parity, residues, and proof methods.
Drill divisibility and parity →Frequently asked questions#
What makes a proof by cases valid?
The cases must be exhaustive — every object you are talking about has to fall into at least one of them. Cases may overlap without harm, but a gap breaks the proof, and it breaks it silently.
Which modulus should I split by?
Match it to the claim. Divisibility by 3 means split by 3. Anything about squares usually wants 4, and odd squares want 8. Even-and-odd is only the split by 2, and it tells you nothing about divisibility by anything else.
Why is every square 0 or 1 when divided by 4?
Because a number is either even or odd. An even number 2m squares to 4m², which leaves 0. An odd number 2m+1 squares to 4m² + 4m + 1, which leaves 1. There is no third possibility, so no square ever leaves 2 or 3.
How do remainders prove an equation has no solutions?
Equal numbers must leave equal remainders. So if you can find one modulus where the two sides can never leave the same remainder, no solution can exist — and one well-chosen modulus settles infinitely many cases at once.
Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written — several of these exist because somebody asked.