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.
$\endgroup$ 42 Answers
$\begingroup$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$.
$\endgroup$ $\begingroup$Working modulo $\,73\,$ :
$$2^6=-9\implies 2^{12}=(-9)^2=8=2^3\implies 2^9=1$$
$$3^4=8=2^3\implies3^{12}=(2^3)^3=2^9=1$$
$$5^6=3\implies 5^{36}=3^6=8\cdot3^2=72=-1$$
Thus, we've found a primitive root modulo $\,73\,$ (namely $\,5\,$), and from here we get two solutions to $\,x^2=-1\pmod{73}\,$ : $\;\;5^{18}=(5^6)^3=3^3=27\;,\;-27=46\;$ , and the two solutions to $\,x^2=-1\pmod 5 \;$ are $\,\;2,3\;$
So we have the solutions modulo $\,365\,$ : $\;173\;,\;-173=192\;,\;338\ldots$ and I think that's all, folks: four different solutions: $\;27,\; 46,\; 173,\; 339\pmod{365}$
$\endgroup$ 1
