¿Por qué es $x^2 \pmod{16}$ siempre $0, \ 1,\ 4,\ 9$?

Question

Con un simple trozo de código podría deducir que para cualquier entero no negativo, $x$ $x^2 \pmod{16}$ es siempre un número del conjunto $\{0, 1, 4, 9\}$. Sin embargo, las matemáticas detrás de ella se evade de mí. ¿Alguien puede explicar la razón detrás de esto?

Answer 1

Tenga en cuenta que el cuadrado de un número impar es siempre $\equiv 1\pmod 8$ porque $(2k+1)^2=4k^2+4k+1=4k(k+1)+1$ y uno de $k, k+1$ es incluso. Por lo tanto el cuadrado de un número impar es siempre $\equiv 1$ o $\equiv 9 \pmod {16}$. Si un número es el doble de un número impar, por lo tanto su suqre es $\equiv 4\cdot 1$ o $\equiv 4\cdot 9\pmod {16}$, pero ambos significan $\equiv 4\pmod {16}$. Por último, si un número es divisible por $4$, su plaza es divisible por $16$, por lo tanto $\equiv 0\pmod {16}$.

Answer 2

Usted sólo puede comprobar los posibles valores de $x=0,1,\dots,15$. Si usted tiene $x=a+16k$ algunos $a$$\{0,1,\dots,15\}$, usted tiene $x^2=(a+16k)^2=a^2+16(\dots)=a^2$.

Es cierto en general que si usted tiene alguna función $f(n)$ compuesta de la suma y la multiplicación que $f(n)=f(n+ka)$ si se calcula mod $a$, ver http://en.wikipedia.org/wiki/Modular_arithmetic.

Answer 3

Sugerencia $\rm\ mod\ 16\!:\ (2^n (2k\!+\!1))^2\! = 4^{n+1} k(k\!+\!1) + 4^n\! \equiv 4^n$ si $\rm\,n\ge 1,\,$ else $\rm\equiv 8\,j + 1\:$ si $\rm\,n=0.$

Answer 4

$(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}$ si $k$ es incluso.

Si $k$ es extraño $=2c+1, (4k\pm1)^2\equiv 8k+1\pmod{16}\equiv(2c+1)8+1\equiv9\pmod{16}$