use mathematical induction to prove 7^n - 3^n is divisible by 4.
It is true for n = 1 since 71 - 31 = 4 which is divisible by 4.
We also need to show that it is true for n = 2 (which makes this proof a little different from most induction proofs as we will see.)
It is true for n = 2 since 72 - 32 = 49 - 9 = 40 which is divisible by 4.
Assume for some k ≧ 2 , that both 7k - 3k and 7k-1 - 3k-1 are divisible by 4. Therefore there exist integers p,q such that
(A) 7k - 3k = 4p and
(B) 7k-1 - 3k-1 = 4q
Multiply the left side of (A) by (7 + 3) and the right side by 10
(7 + 3)(7k - 3k) = 40p
FOIL the left side
7k+1 - 7·3k + 3·7k - 3k+1 = 40p
Factor 7·3 out of the two middle terms on the left:
7k+1 + 7·3(-3k-1 + 7k-1) - 3k+1 = 40p
Reverse the terms inside the parentheses:
7k+1 + 7·3(7k-1 - 3k-1) - 3k+1 = 40p
By (B) above we can replace the parentheses by 4q
7k+1 + 7·3(4q) - 3k+1 = 40p 7k+1 + 84q - 3k+1 = 40p
Rearrange the equation:
7k+1 - 3k+1 = 40p - 84q 7k+1 - 3k+1 = 4(10p - 21)q
The right side is divisible by 4, and therefore so is the left side.