Theorem. If n is a positive integer then n7 - n is divisible by 7.
Proof. First we factor n7 - n = n(n6 - 1) = n(n3 - 1)(n3 + 1) = n(n-1)(n2 + n + 1)(n+1)(n2 - 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 n7 - n has the factor n, which is divisible by 7.
Case 2: n = 7q + 1. Then n7 - n has the factor n-1 = 7q.
Case 3: n = 7q + 2. Then the factor n2 + n + 1 = (7q + 2)2 + (7q+2) + 1 = 49 q2 + 35 q + 7 is clearly divisible by 7.
Case 4: n = 7q + 3. Then the factor n2 - n + 1 = (7q + 3)2 - (7q+3) + 1 = 49 q2 + 35 q + 7 is clearly divisible by 7.
Case 5: n = 7q + 4. Then the factor n2 + n + 1 = (7q + 4)2 + (7q+4) + 1 = 49 q2 + 63 q + 21 is clearly divisible by 7.
Case 6: n = 7q + 5. Then the factor n2 - n + 1 = (7q + 5)2 - (7q+5) + 1 = 49 q2 + 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.
Prove each of the following using a case by case analysis.
Next==>What does Well Defined Mean?
<==Back To Counter Examples