Question

Let n be a positive odd integer. Prove that n4 ≡ 1 (mod 16). You may use any of the mod rules provided in class (In addition, if you end up getting an expression of the form a (3a+1) somewhere in your work where a is an integer, separately end up proving that this expression is always even and use that result to complete your proof).

Answer 1

If $n$ is odd, then we can write $n=2m+1$ for some $m\in Bbb Z$.

Expanding gives

$n^4=(2m+1)^4=16m^4+32m^3+24m^2+8m+1$

This reduces to

$n^4\equiv8m^2+8m+1\pmod{16}$

Notice that $8m^2+8m=8m(m+1)$ is 8 times the product of two consecutive integers, one even and the other odd. This product is even and thus divisible by 2, so that $8m^2+8m=16\ell$ where $\ell\in\Bbb Z$, and the equivalence further reduces to

$n^4\equiv16\ell+1\equiv1\pmod{16}$

as required.