Is $x^2 \equiv -1 \pmod{365}$ solvable? 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.
 A: We have $365 = 5 \times 73$.  The congruence becomes $x^2 = -1 \mod 5$  and $x^2 = -1 \mod 73$. 
We have if $p = 1 \mod 4 \implies x^2 = -1 \mod p$ has exactly $2$ solutions.
Thus $x^2 = -1 \mod 5$ has solutions $x_0,x_1$ and $x^2 = -1 \mod 73$ has solutions $y_0,y_1$. 
The original solutions satisfies either:
$x = x_0 \mod 5, x = y_0 \mod 73$; $x = x_0 \mod 5, x = y_1 \mod 73$; $x = x_1 \mod 5, x = y_0 \mod 73$ ; $x = x_1 \mod 5, x = y_1 \mod 73$.
For each pair of congruence , $x$ is uniquely determined $\mod 365$ by the Chinese remainder theorem.  Hence the original congruence has $4$ solutions.
A: If $\,m,n\,$ are coprime then, by CRT, solving an integer coefficient  polynomial $\,f(x)\equiv 0\pmod{\!mn}\,$ is equivalent to solving $\,f(x)\equiv 0\,$ mod $\,m\,$ and mod $\,n.\,$ By CRT, each combination of a root $\,r_i\bmod m\,$ and a root $\,s_j\bmod n\,$ corresponds to a unique root $\,t_{ij}\bmod mn,\,$ i.e.
$$\begin{eqnarray} f(x)\equiv 0\!\!\!\pmod{mn}&\overset{\rm CRT}\iff& \begin{array}{}f(x)\equiv 0\pmod m\\f(x)\equiv 0\pmod n\end{array} \\ 
&\iff&  \begin{array}{}x\equiv r_1,\ldots,r_k\pmod m\phantom{I^{I^{I^I}}}\\x\equiv s_1,\ldots,s_\ell\pmod n\end{array}\\ 
&\iff& \left\{ \begin{array}{}x\equiv r_i\pmod m\\x\equiv s_j\pmod n\end{array} \right\}_{\begin{array}{}1\le i\le k\\ 1\le j\le\ell\end{array}}^{\phantom{I^{I^{I^I}}}}\\
&\overset{\rm CRT}\iff& \left\{ x\equiv t_{i j}\!\!\pmod{mn} \right\}_{\begin{array}{}1\le i\le k\\ 1\le j\le\ell\end{array}}\\
\end{eqnarray}\qquad\qquad$$
A: Yes. Let a solution to $x^2+1 \equiv 0 \pmod {5}$ be $r_{1}$, and let a solution  to $x^2+1 \equiv 0 \pmod {73}$ be $r_{2}$
Then note that by CRT, we have that there exists such $x$ that $$x \equiv r_{1} \pmod {5}$$ $$x \equiv r_{2} \pmod {73}$$
Exists. Then note that for such $x$, $$x^2+1 \equiv 0 \pmod {5}$$ $$x^2+1 \equiv 0 \pmod {73}$$
Which gives $$x^2+1 \equiv 0 \pmod {365}$$
A: We show the following result:

Let $n,m$ be coprime integers. Let $a \in \Bbb Z$. Then $a$ is a square modulo $nm$ iff $a$ is square mod $n$ and $a$ is square mod $m$.

Assume that there are integers $x_i$ such that $x_1^2 \equiv a \pmod m$ and $x_2^2 \equiv a \pmod n$ where $m,n$ are coprime.
We show that $y^2 \equiv a \pmod {nm}$ has a solution (the converse is obvious).
We know that there is an integer $y$ such that  $y \equiv x_1 \pmod m$ and $y \equiv x_2 \pmod n$, by the Chinese remainder theorem.
Then $y^2-a$ is a multiple of $m$ and $n$, so it is a multiple of $nm$ since $(n,m)=1$. Therefore $y^2 \equiv a \pmod {nm}$.

More generally, we have the following theorem (see Ireland Rosen, p. 50)

Let $a,n \in \Bbb N$ be coprime integers. Write $n=2^e p_1^{e_1} \cdots p_k^{e_k}$ as product of distinct prime powers.
  Then $a$ is a square modulo $n$ if and only if
  
  
*
  
*$a$ is a square modulo $p_i$ (for $1 \leq i \leq k$) ; this is equivalent to $a^{\dfrac{p_i-1}{2}} \equiv 1 \pmod{p_i}$
  
*$e>1 \implies a \equiv 1 \pmod{2^{2+r}}$ where $r = 1$ if $e \geq 3$ and $r=0$ if $e=2$.

A: It is true because of the Chinese remainder theorem, which asserts the map
\begin{align}
\mathbf Z/n\mathbf Z&\longrightarrow \mathbf Z/p_1^{n_1}\mathbf Z\times\dotsm\times\mathbf Z/p_k^{n_k}\mathbf Z\\
x\bmod n&\longmapsto(x\bmod p_1^{n_1},\dots,x\bmod p_k^{n_k})
\end{align}
is a ring isomorphism.
