Cuántos cuadrados hay modulo $2^n$?
Si hemos de tratar con $p^n$, donde p impar primo, entonces podríamos usar Hensel del Lexema, que claramente no funciona con $2^n$.
Respuestas
¿Demasiados anuncios?
Tas
Puntos
11
A partir de las 8, el extraño residuos están dadas por $(-1)^k3^m$, por lo que claramente, las plazas son exactamente de la forma $3^{2m}$ que es una cuarta parte de ellos. Incluso los residuos son cuadrados si son divisibles por 4 y el cociente es un cuadrado modulo $2^{n-2}$.
Así, consigue $squares(2^n)=2^{n-3} + squares(2^{n-2})$ que se resuelve fácilmente.
Holden Lee
Puntos
368
Tenemos $(\mathbb Z/2^n\mathbb Z)^{\times}\cong C_2\times C_{2^{n-2}}$ donde $C_m$ denota el grupo cíclico de orden $m$, donde un isomorfismo es dado por $(-1)^a3^b\leftarrow (a,b)$. (Prueba: ver Thm. 6.1, p. 25 aquí: http://web.mit.edu/~holden1/www/matemáticas/número-teoría.pdf. Básicamente, demostrar por inducción que $3^{2^k}=2^{k+2}j+1$ donde $j$ es impar.)
Los elementos en $C_2\times C_{2^{n-2}}$ que son divisibles por 2 son exactamente $0\times 2C_{2^{n-2}}$ que tiene cardinalidad $2^{n-3}$. Tenemos la recurrencia $\#\text{squares}(2^n)=2^{n−3}+\#\text{squares}(2^{n−2})$ como en Phira la respuesta.
