Número de soluciones a la congruencia $x^2\equiv 121\pmod {1800}$

Question

Estoy tratando de encontrar el número de soluciones a esta congruencia: $$x^2\equiv 121\pmod {1800}$$

Pensé en escribirlo como un sistema de congruencias. Como $1800=3^2 \cdot 5^2 \cdot 2^3$ obtenemos:

$x^2\equiv 121\pmod {5^2} \;,\; x^2\equiv 121\pmod {3^2} \;,\; x^2\equiv 121\pmod {2^3}$

$\Downarrow$

$ x^2\equiv 21\pmod {5^2} \;,\; x^2\equiv 4\pmod {3^2} \;,\; x^2\equiv 1\pmod {2^3} $

Ahora estoy bastante atascado con la forma de resolver cada una de las congruencias cuadráticas anteriores, ¿hay alguna forma rápida de hacerlo?

Gracias

Answer 1

Una pista:

Necesitamos $\left(\dfrac x{11}\right)^2\equiv1\pmod{3^2,5^2,2^3}$

Ahora podemos demostrar $y^2\equiv1\pmod{p^n}$ tiene exactamente dos soluciones para el primo $p\ge3$ y enteros $n\ge1$

Por último, podemos aplicar Teorema chino del resto para encontrar el número de soluciones in-congruentes para ser $$4\cdot2^2$$

Ver también : Número de soluciones de $x^2=1$ en $\mathbb{Z}/n\mathbb{Z}$

Answer 2

No, no hay una forma rápida. Para resolver $x^2\equiv a \pmod{p^n}$ primero resolvemos $x^2\equiv a \pmod{p}$ y luego utilizar el Lemma de Hensel para "levantar" la solución a $\pmod{p^2}$ y luego $\pmod{p^3}$ etc. A veces las soluciones se levantan de forma única, a veces no.

En el caso de su problema, hay dos soluciones modulares $5$ que se elevan unívocamente a dos soluciones módulo $25$ . Lo mismo ocurre con el módulo $9$ . Hay una solución modulo $2.$ Se eleva a dos soluciones módulo $4.$ Cada una de ellas, a su vez, da lugar a dos soluciones módulo $8$ para un total de 4 soluciones modulo $8.$

Así que al final, hay $2\times 2\times 4 = 16$ soluciones modulo $1800.$