Proof by Exhaustion (Case by Case)
# Proof by Exhaustion (Case by Case)

Sometimes the most straight forward, if not the most elegant, way to construct a proof is by checking
cases.
## Example: Divisibility

**Theorem.** If n is a positive integer then n^{7} - n is divisible by 7.

**Proof.** First we factor n^{7} - n = n(n^{6} - 1) = n(n^{3} -
1)(n^{3} + 1) = n(n-1)(n^{2} + n + 1)(n+1)(n^{2} - n + 1). Now there are 7
cases to consider, depending on n = 7 q + r where r = 0, 1, 2, 3, 4, 5, 6, 7.

Case 1: n = 7q. Then n^{7} - n has the factor n, which is divisible by 7.

Case 2: n = 7q + 1. Then n^{7} - n has the factor n-1 = 7q.

Case 3: n = 7q + 2. Then the factor n^{2} + n + 1 = (7q + 2)^{2} + (7q+2) + 1 = 49
q^{2} + 35 q + 7 is clearly divisible by 7.

Case 4: n = 7q + 3. Then the factor n^{2} - n + 1 = (7q + 3)^{2} - (7q+3) + 1 = 49 q^{2} + 35 q + 7 is clearly divisible by 7.

Case 5: n = 7q + 4. Then the factor n^{2} + n + 1 = (7q + 4)^{2} + (7q+4) + 1 = 49 q^{2} + 63 q + 21 is clearly divisible by 7.

Case 6: n = 7q + 5. Then the factor n^{2} - n + 1 = (7q + 5)^{2} - (7q+5) + 1 = 49 q^{2} + 63 q + 21 is clearly divisible by 7.

Case 7: n = 7q + 6. Then the factor n + 1 = 7q +7 is clearly divisible by 7.

q

## Exercises

Prove each of the following using a case by case analysis.

- The "Triangle Inequality" for real numbers, |a + b| is less than or equal to |a| + |b|. (The cases coorespond to the signs (plus or minus) of a and b.)

** Next==>**What does Well Defined Mean?

**<==Back To
** Counter Examples

Back to Proofs