Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

5 Answers 5

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|improve this answer

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.

share|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|improve this answer
1  
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

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|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|improve this answer

Your Answer

 
discard

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.