Problem: Let $\gcd(y,400) = 1$, and consider the congruence equation $x^2 \equiv y \pmod{400}$. Assuming the congruence equation is soluble, how many solutions are there? I believe I am nearly finished with this problem in the "Attempt" section below, but there is one small problem in the end of my solution that I am encountering.
Attempt: Since the equation is assumed soluble, there exists $x_0$ such that $x_0^2 \equiv y \pmod{400}$. Now let $x'$ be such that $x'^2 \equiv 1 \pmod{400}$. Then we have $(x_0 x')^2 \equiv y \mod{400}$. The equation $x'^2 \equiv 1 \pmod{400}$ has 8 solutions (simple application of Chinese remainder theorem), so I have generated a set of 8 solutions to the original equation. However, I am having trouble proving that the set of solutions to the original equation is completely described by $\{ x_0 x' \mid x'^2 \equiv 1 \pmod{400} \}$. In other words, how do I show that for any $z$ satisfying the original equation, it must be true that $z \equiv x_o x' \pmod{400}$ for some $x'$ described above? Or are there more than eight solutions to the original equation?
Here enters the condition $\gcd(y,400)=1$ in the picture. Since ${x_0}^2\equiv y$, neither $x_0$ can have common divisor with $400$, implying $\gcd(x_0,400)=1$. So, by Bezout's identity, it will have a multiplicative inverse $\pmod{400}$.
Thus, if $z^2\equiv y$, then $({x_0}^{-1}z)^2\equiv 1 \pmod{400}$.