<s>[INST] How many solutions does $x^2 \equiv {-1} \pmod {365}$ have? 
How many solutions does $x^2 \equiv {-1} \pmod {365}$ have?

My thought:
$365 = 5 \times 73$ where $5$ and $73$ are prime numbers. 
So we can obtain $x^2 \equiv {-1} \pmod 5$ and $x^2 \equiv {-1} \pmod {73}$.
For $x^2 \equiv {-1} \pmod 5$, 
we checked $5 \equiv 1 \pmod 4$, therefore it is solvable. 
Using the Euler criterion, $(-1)^{\frac{5-1}{2}} \equiv 1 \pmod 5$. 
Thus it has two solutions.
For $x^2 \equiv {-1} \pmod {73}$, 
we checked $73 \equiv 1 \pmod 4$, therefore it is solvable. 
Using the Euler criterion, $(-1)^{\frac{73-1}{2}} \equiv 1 \pmod{73}$. 
Thus it has two solutions.
So, there are four solutions in total.
 [/INST] Because $5$ and $73$ are relatively prime, we have $x^2\equiv -1\pmod{5\cdot 73}$ if and only if $x^2\equiv -1\pmod{5}$ and $x^2\equiv -1\pmod{73}$. 
Because $5$ is a prime of the form $4k+1$, the congruence $x^2\equiv -1 \pmod{5}$ has a solution, and hence two solutions. The same applies to $x^2\equiv -1\pmod{73}$.
Suppose that $(a,b)$ is an ordered  pair such that $a^2\equiv -1\pmod{5}$ and $b^2\equiv -1\pmod{73}$. By the Chinese Remainder Theorem, there is a unique $c$ (modulo $5\cdot 73$) such that $c\equiv a\pmod{5}$ and $c\equiv b\pmod{73}$.
Then $c^2\equiv -1\pmod{5\cdot 73}$, so $c$ is a solution of $x^2\equiv -1\pmod{365}$.  Conversely, any solution $x$ of $x^2\equiv -1\pmod{365}$ gives rise to such an ordered pair. 
There are $4$ such ordered pairs, and hence $4$ solutions of the congruence modulo $365$.
Remark: The four solutions come in two $\pm$ pairs, so the task of finding them is only half as unpleasant as it looks. Actually, with the Chinese Remainder Theorem, once you have found $A$ and $B$ such that $73A\equiv 1 \pmod{5}$ and $5B\equiv 1\pmod{73}$, all four solutions can be written down mechanically. We do need to know that $\pm 2$ are the solutions of $x^2\equiv -1\pmod{5}$ and $\pm 27$ are the solutions of $x^2\equiv -1\pmod{73}$.   
The idea generalizes: there are $8$ solutions modulo $5^3\cdot 73\cdot 97^2$. 
</s>