I know that a similar question already exists, but I have a different question to ask.
We want to examine if $x^2 \equiv -1 \pmod{365}$ has a solution.
My thought is: $365=5\cdot 73$. So,The congruence $x^2 \equiv -1 \pmod{365}$ has solution, if and only if, the congrueces $x^2 \equiv -1 \pmod 5$ and $x^2 \equiv -1 \pmod{73}$ has solutions. So, if we use Legendre's Symbol we have
- $x^2 \equiv -1 \pmod 5$ has solution $\iff (-1/5)=1 $ (and with simple calculations, indeed)
- $x^2 \equiv -1 \pmod{71}$ has solution $\iff (-1/73)=1 $
Now, can we conclude that the congruence $x^2 \equiv -1 \pmod{365}$ has solution?
And more general: If we have the congruence $x^2 \equiv a \pmod n$ with $n=p_1^{n_1}\cdots p_k^{n_k},\ \gcd(a,n)=1$, which is equivalent with the system $x^2 \equiv a {\pmod p_1^{n_1}},\ldots,x^2 \equiv a \pmod{p_k^{n_k}}$, can we conclude that the first has solution if and only if each one of $x^2\equiv a\pmod{p_i^{n_i}},\ \forall i=1,\ldots,k$ has solution?
Thank you.