¿Modo eficiente de encontrar cuadrados mod una potencia prima?

Question

Supongamos que se nos plantea el problema de, por ejemplo, encontrar todos los cuadrados módulo $3^4$ . ¿Hay alguna forma eficiente de calcular esto sin tener que comprobar una tonelada de casos? Para sólo un primo podemos usar la reciprocidad cuadrática, pero eso no sirve aquí.

Un problema como este fue preguntado en un examen oral en mi programa (el número era $4000$ (por lo que había que aplicar primero el teorema del resto chino y luego resolver dos preguntas como esta), así que supongo que el profesor pensó que esto es algo que uno debería ser capaz de resolver en la pizarra con bastante rapidez.

La única aproximación que conozco es encontrar primero todos los cuadrados modulo digamos $9$ , lo que daría $0,1,4,7$ y luego mira los números:

$0,0+9,0+18,1,1+9,1+18,4,4+9,4+18,...$

y averiguar cuáles de estos levantamientos son cuadrados mod $27$ . Esto se vuelve rápidamente muy molesto. Especialmente cuando hay que levantar estos cuadros para $3^4$ .

Answer 1

Esta solución depende de la estructura del grupo $U_{p^\ell}$ de unidades en el anillo $\mathbf{Z}_{p^\ell}$ . Si no ha cubierto eso, entonces la pregunta fue un poco mezquina IMHO.

Si $p>2$ es un primo, entonces se puede aplicar el siguiente procedimiento para encontrar todos los cuadrados mod $p^\ell$ . Primero encontremos los cuadrados que son coprimos a $p$ . El grupo $U_{p^\ell}$ es cíclico de orden $\phi(p^\ell)=(p-1)p^{\ell-1}$ . En un grupo cíclico de orden par, exactamente la mitad de los elementos son cuadrados. Pero para un número entero $m$ para ser un residuo cuadrático módulo $p^\ell$ es necesario que $m$ para ser un residuo cuadrático módulo $p$ . Esto ya impide que la mitad de los elementos de $U_{p^\ell}$ de ser cuadrados. Por lo tanto, por la observación anterior, este criterio necesario es también suficiente: $m$ es un cuadrado módulo $p^\ell$ si y sólo si $m$ es un cuadrado módulo $p$ .

Si $p\mid m$ entonces $m\equiv a^2\pmod{p^\ell}$ implica que $p\mid a$ . Escribamos $a=a'p$ . Entonces $m\equiv a'^2p^2\pmod{p^\ell}$ y vemos que debemos tener $p^2\mid m$ . Por lo tanto, $m=p^2m'$ y $m'\equiv a'^2\pmod {p^{\ell-2}}$ . Esto significa que encontrar cuadrados divisibles por $p$ en el ring $\mathbf{Z}_{p^\ell}$ equivale a encontrar todo las casillas en $\mathbf{Z}_{p^{\ell-2}}$ . Aclarar. Repetir.

Cuando $p=2$ un enfoque general similar funciona. Esta vez $U_{2^\ell}$ es un producto directo de dos grupos cíclicos. Uno de orden $2$ y la otra de orden $2^{\ell-2}$ . Por lo tanto, exactamente una cuarta parte de los elementos de $U_{2^\ell}$ son cuadrados, y están formados por los números $m\equiv 1\pmod 8$ porque lo vemos por un cálculo directo en el caso $\ell=3$ y para $\ell >3$ se puede repetir el argumento anterior. Encontrar los cuadrados pares se hace de la misma manera que en el caso $p>2$ .

Answer 2

La forma más sencilla de enumerar las casillas mod. $3^4 = 81$ es esto:

$\pmatrix{0 & 0 + 1 = 1 & 1 + 3 = 4 & 4 + 5 = 9 & 9 + 7 = 16 & 16 + 9 = 25 & 25 + 11 = 36 & 36 + 13 = 49 & 49 + 15 = 64 \cr 64 + 17 = 0 & 0 + 19 = 19 & 19 + 21 = 40 & 40 + 23 = 63 & 63 + 25 = 7 & 7 + 27 = 34 & 34 + 29 = 63 & 63 + 31 = 13 & 13 + 33 = 46 \cr 46 + 35 = 0 & 0 + 37 = 37 & 37 + 39 = 76 & 76 + 41 = 36 & 36 + 43 = 79 & 79 + 45 = 43 & 43 + 47 = 9 & 9 + 49 = 58 & 58 + 51 = 28 \cr 28 + 53 = 0 & 0 + 55 = 55 & 55 + 57 = 31 & 31 + 59 = 9 & 9 + 61 = 70 & 70 + 63 = 52 & 52 + 65 = 36 & 36 + 67 = 22 & 22 + 69 = 10\cr 10 + 71 = 0 & 0 + 73 = 73 & 73 + 75 = 67 & 67 + 77 = 63 & 63 + 79 = 61\cr}$

... y podemos parar ahí, porque $(81-x)^2 \equiv x^2 \mod 81$ .