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.
Best Answer
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.