The short answer#
A proof by cases splits the objects you're reasoning about into a finite list of situations, proves the claim in each situation, and concludes it holds always. It is valid only if the list is exhaustive — every object falls into at least one case.
For the integers, the division algorithm hands you an exhaustive split for free. For any fixed m ≥ 1, every integer n can be written
so every integer lies in exactly one of the m classes r = 0, 1, 2, …, m − 1.
That is the engine. Pick m, get m cases, check them all. The number of cases is m — not 2, not "a few", not "however many I thought of".
Even and odd is just m = 2#
Splitting into even and odd feels like the default because it usually is the first split anyone learns. But it is only the m = 2 case, and parity carries no information about anything except divisibility by 2.
If a claim is about divisibility by 3, splitting into even and odd tells you nothing at all — 3 and 4 are on opposite sides of that split and neither fact is relevant. Match the modulus to the claim.
| The claim is about… | Split modulo | Cases |
|---|---|---|
| parity, or 2 | something | 2 | 2 |
| 3 | something | 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 integer n, 3 divides n³ − n.
Factor first: n³ − n = (n − 1)n(n + 1). Now split by n mod 3, which gives exactly three cases.
- n ≡ 0 (mod 3). Then 3 | n, so 3 divides the product.
- n ≡ 1 (mod 3). Then n − 1 ≡ 0, so 3 | (n − 1) and 3 divides the product.
- n ≡ 2 (mod 3). Then n + 1 ≡ 3 ≡ 0, so 3 | (n + 1) and 3 divides the product.
The three cases cover every integer, so the claim holds for all n. ∎
Notice what made it short: factoring before splitting. Three consecutive integers must contain a multiple of 3, and the case split is just that observation written out rigorously.
The squares tables worth memorizing#
Squares are wildly restricted modulo small numbers, and that restriction is what powers most impossibility proofs. Compute these once and keep them.
| n mod 4 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| n² mod 4 | 0 | 1 | 0 | 1 |
Modulo 8 the picture is finer and separates odd from even squares 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 is the one that does real work. Write n = 2m + 1. Then
n² = 4m² + 4m + 1 = 4m(m + 1) + 1.
Among any two consecutive integers m and m + 1 one is even, so m(m + 1) is even and 4m(m + 1) is a multiple of 8. Therefore every odd square is ≡ 1 (mod 8).
Killing an equation with a modulus#
To show an equation has no integer solutions, find a modulus where the two sides can never match. This is proof by cases wearing its most useful hat.
Claim. No integers x, y satisfy x² + y² = 4k + 3.
Proof. Work modulo 4. By the table above, each of x² and y² is ≡ 0 or 1. So the possible values of x² + y² modulo 4 are
0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 2.
A sum of two squares is therefore ≡ 0, 1, or 2 (mod 4) — never 3. But 4k + 3 ≡ 3 (mod 4). The two sides can never be congruent, so no solution exists. ∎
How to pick the modulus. Look at the coefficients and exponents. Squares want 4 or 8. A term like 2y² pushes you to 8, because you need to know 2y² modulo 8 and that depends on the parity of y. Cubes want 9. Fifth powers want 5 or 11. If a modulus gives you every residue on both sides, it is the wrong modulus — try the next one up in the same family.
When the claim is true for some classes and false for others#
A modulus does not only prove impossibility. It also tells you exactly which cases survive, and that is often the real answer.
Take odd numbers of the form x² + 2y². Since the total is odd, x must be odd, so x² ≡ 1 (mod 8). For the other term: if y is even then 2y² ≡ 0 (mod 8), and if y is odd then y² ≡ 1 (mod 8) so 2y² ≡ 2. Adding,
x² + 2y² ≡ 1 + 0 = 1 or 1 + 2 = 3 (mod 8).
So an odd number of this form is always ≡ 1 or 3 (mod 8) — which means no odd number ≡ 5 or 7 (mod 8) can be written as x² + 2y². Two of the four odd classes are excluded and two are not.
Be careful about the direction of that arrow. It says representable ⟹ residue 1 or 3. It does not say every number with residue 1 or 3 is representable: 35 ≡ 3 (mod 8) and is not of this form. A residue argument can rule cases out; it can rarely rule them in.
Where these go wrong#
- A non-exhaustive split. The cases must cover everything. "Positive, negative" forgets zero. "n ≡ 1 or 2 (mod 3)" forgets n ≡ 0. If the list has a hole, the proof proves nothing.
- Too few cases. Splitting mod 2 when the claim needs mod 4 produces cases you cannot finish. If a case won't close, suspect the modulus before you suspect the claim.
- Overlapping is fine; missing is fatal. Cases may overlap without harming the proof — you just do redundant work. Only gaps break it.
- Reading the implication backwards. "Representable ⟹ residue in this set" does not give "residue in this set ⟹ representable." That converse needs its own argument and is usually false.
- Checking examples instead of classes. Verifying a claim for n = 1 through 20 is not a proof by cases. A case is an infinite class defined by a residue, not a number.
- Forgetting that the modulus fixes the count. Working modulo m means m cases. Not "the ones that seem interesting".
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#
How many cases does a proof modulo m need?
Exactly m. The division algorithm says every integer n can be written as n = qm + r with 0 ≤ r < m, so the possible remainders are 0, 1, …, m − 1 and there are m of them. Every integer lands in exactly one class, which is what makes the split exhaustive.
Why is splitting into even and odd sometimes not enough?
Because parity is only the m = 2 case, and it carries information about divisibility by 2 and nothing else. A claim about divisibility by 3, or about which residues a square can occupy, is invisible to a parity split. Match the modulus to what the claim is actually about.
What are the possible values of a perfect square modulo 4 and modulo 8?
Modulo 4 a square is always 0 or 1, never 2 or 3. Modulo 8 an odd square is always 1, and an even square is 0 or 4. The odd case follows from writing n = 2m + 1, giving n² = 4m(m + 1) + 1, where m(m + 1) is even so 4m(m + 1) is a multiple of 8.
How do you prove an equation has no integer solutions?
Pick a modulus, compute every residue each side can take, and show the two sets are disjoint. For example x² + y² = 4k + 3 has no solutions because squares are 0 or 1 mod 4, so a sum of two squares is 0, 1, or 2 mod 4 and can never be 3. Choosing the modulus is the only creative step.