Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 7 down vote accepted

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}$.

share|cite|improve this answer

$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\}.$

share|cite|improve this answer
You 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\}$. – ShreevatsaR Nov 5 '12 at 4:38

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

share|cite|improve this answer

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.$

share|cite|improve this answer

$(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}$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.