Solution

Show that if $a$ and $b$ are both odd, then 8 divides $a^2-b^2$.


If $a$ and $b$ are both odd, than we can find integers $k_1$ and $k_2$, such that $a = 2k_1 + 1$ and $b = 2k_2 + 1$. As such,

$$\begin{array}{rcl} a^2 - b^2 &=& (a+b)(a-b)\\\\ &=& ((2k_1 + 1) + (2k_2 + 1))((2k_1 + 1) - (2k_2 + 1))\\\\ &=& (2k_1 + 2k_2 + 2)(2k_1 - 2k_2)\\\\ &=& 4(k_1 + k_2 + 1)(k_1 - k_2) \end{array}$$

We have established that $4 \mid a^2 - b^2$. We need to find one more factor of $2$ -- that is to say, it remains to show $2 \mid (k_1 + k_2 + 1)(k_1 - k_2)$.

We argue by cases: If $k_1$ and $k_2$ are both even or both odd, then $(k_1 - k_2)$ will be even. Alternatively, if one is even and the other odd, then $(k_1 + k_2 + 1)$ will be even. In either case, the product $(k_1 + k_2 + 1)(k_1 - k_2)$ must then be even and equal to some $2k_3$ for some integer $k_3$.

Thus, $a^2 - b^2 = 8k_3$ for some integer $k_3$ -- and consequently, $8 \mid a^2 - b^2$.

QED.