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?
Why is $x^2 \pmod{16}$ always $0, \ 1,\ 4,\ 9$?
5 Answers
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}$.
$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\}.$
-
1You can say: $x = 8k \pm n$ where $n \in \{0,1,2,3,4\}$, so $x^2 = 64k^2 \pm 16kn + n^2 \equiv n^2$ where $n^2 \in \{0,1,4,9,16\}$. – 2012-11-05
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.
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.$
$(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}$