Prove by using the Division Algorithm that the fourth power of any integer is of the form $8k$ or $8k + 1$.
We'll use the Division Algorithm which guarantees that given integers $a$ and (divisor) $b \geq 1$, there exists unique integers quotient $q$ and remainder $r$ such that $a$ can be written as
$$a = qb + r \quad \text{where} \quad 0 \le r < b$$
If we choose $b=8$, then $0 \le r < 8$, and we have
$$\begin{align} a^4 &= 4096 q^4 + 2048 q^3 r + 384 q^2 r^2 + 32 q r^3 + r^4 \\ \\ &= 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3) + r^4 \end{align}$$
The integer $r$ can only be $0, 1, 2, 3, 4, 5, 6, 7$. Let's consider each case:
- $r=0$ means $a^4 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3)$, of the form $8k$.
- $r=1$ means $a^4 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3) + 1$, of the form $8k + 1$.
- $r=2$ means $a^4 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3) + 16 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3 + 2) $, of the form $8k$.
- $r=3$ means $a^4 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3) + 81 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3 + 10) + 1$, of the form $8k + 1$.
- $r=4$ means $a^4 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3) + 256 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3 + 32)$, of the form $8k$.
- $r=5$ means $a^4 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3) + 625 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3 + 78) +1 $, of the form $8k+1$.
- $r=6$ means $a^4 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3) + 1296 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3 + 162)$, of the form $8k$.
- $r=7$ means $a^4 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3) + 2401 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3 + 300) + 1$, of the form $8k+1$.
So the fourth power of any integer is of the form $8k$ or $4k+1$ for some integer $k$.