Why is $x^2 \pmod{16}$ always $0, \ 1,\ 4,\ 9$? With a simple piece of code I could deduce that for any non-negative integer $x$ the value of $x^2 \pmod{16}$ is always a number from the set $\{0, 1, 4, 9\}$. However, the math behind it evades me. Can anyone explain the reason behind this?
 A: Note that the square of an odd number is always $\equiv 1\pmod 8$ because $(2k+1)^2=4k^2+4k+1=4k(k+1)+1$ and one of $k, k+1$ is even.
Thus the square of an odd number is always $\equiv 1$ or $\equiv 9 \pmod  {16}$.
If a number is the double of an odd number, therefore its suqre is $\equiv 4\cdot 1$ or $\equiv 4\cdot 9\pmod  {16}$, but both mean $\equiv 4\pmod  {16}$.
Finally, if a number is divisible by $4$, its square is divisible by $16$, hence $\equiv 0\pmod {16}$.
A: $x=8k+n$ where $n\in\{0,1,2,3,4,5,6,7\}$, so $x^2=64k^2+16kn+n^2$ where $n^2\in\{0,1,4,9,16,25=16+9,36=2\times 16+4,49=3\times 16+1\}.$
A: You can just check the possible values for $x=0,1,\dots,15$. If you have $x=a+16k$ for some $a$ in $\{0,1,\dots,15\}$, you have $x^2=(a+16k)^2=a^2+16(\dots)=a^2$.
It is true in general that if you have some function $f(n)$ composed of addition and multiplication that $f(n)=f(n+ka)$ if you calculate mod $a$, see http://en.wikipedia.org/wiki/Modular_arithmetic.
A: Hint $\rm\ mod\ 16\!:\ (2^n (2k\!+\!1))^2\! = 4^{n+1} k(k\!+\!1) + 4^n\! \equiv 4^n$ if $\rm\,n\ge 1,\,$ else $\rm\equiv 8\,j + 1\:$ if $\rm\,n=0.$ 
A: $(4k)^2\equiv 0\pmod{16}$
$(4k+2)^2=16k^2+16k+4\equiv 4\pmod{16}$
$(4k\pm1)^2=16k^2\pm 8k+1\equiv 8k+1\pmod{16}\equiv1 \pmod{16}$ if $k$ is even.
If $k$ is odd $=2c+1, (4k\pm1)^2\equiv 8k+1\pmod{16}\equiv(2c+1)8+1\equiv9\pmod{16}$
