2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.