Número de soluciones de una ecuación de congruencia

Question

Problema: Sea $\gcd(y,400) = 1$ y consideremos la ecuación de congruencia $x^2 \equiv y \pmod{400}$ . Suponiendo que la ecuación de congruencia es soluble, ¿cuántas soluciones hay? Creo que estoy casi terminado con este problema en la sección "Intento" a continuación, pero hay un pequeño problema en el final de mi solución que me estoy encontrando.

Intento: Como la ecuación se supone soluble, existe $x_0$ tal que $x_0^2 \equiv y \pmod{400}$ . Ahora dejemos que $x'$ sea tal que $x'^2 \equiv 1 \pmod{400}$ . Entonces tenemos $(x_0 x')^2 \equiv y \mod{400}$ . La ecuación $x'^2 \equiv 1 \pmod{400}$ tiene 8 soluciones (simple aplicación del teorema chino del resto), así que he generado un conjunto de 8 soluciones a la ecuación original. Sin embargo, tengo problemas para demostrar que el conjunto de soluciones de la ecuación original está completamente descrito por $\{ x_0 x' \mid x'^2 \equiv 1 \pmod{400} \}$ . En otras palabras, ¿cómo demuestro que para cualquier $z$ que satisface la ecuación original, debe ser cierto que $z \equiv x_o x' \pmod{400}$ para algunos $x'$ descrito anteriormente? ¿O hay más de ocho soluciones a la ecuación original?

Answer 1

Aquí entra la condición $\gcd(y,400)=1$ en la foto. Desde ${x_0}^2\equiv y$ ni $x_0$ puede tener divisor común con $400$ lo que implica $\gcd(x_0,400)=1$ . Por lo tanto, por la identidad de Bezout, tendrá un inverso multiplicativo $\pmod{400}$ .
Así, si $z^2\equiv y$ entonces $({x_0}^{-1}z)^2\equiv 1 \pmod{400}$ .