Is $x^2 \equiv -1 \pmod{365}$ solvable?

Question

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.

Answer 1

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$.

Answer 2

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}$$

Answer 3

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.

Answer 4

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.

Answer 5

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$$