Es $x^2 \equiv -1 \pmod{365}$ ¿se puede resolver?

Question

Sé que ya existe una pregunta similar, pero tengo una pregunta diferente que hacer.

Queremos examinar si $x^2 \equiv -1 \pmod{365}$ tiene una solución.

Mi pensamiento es: $365=5\cdot 73$ . Entonces, la congruencia $x^2 \equiv -1 \pmod{365}$ tiene solución, si y sólo si, las congruencias $x^2 \equiv -1 \pmod 5$ y $x^2 \equiv -1 \pmod{73}$ tiene soluciones. Entonces, si usamos el Símbolo de Legendre tenemos

• $x^2 \equiv -1 \pmod 5$ tiene solución $\iff (-1/5)=1 $ (y con cálculos sencillos, de hecho)
• $x^2 \equiv -1 \pmod{71}$ tiene solución $\iff (-1/73)=1 $

Ahora, ¿podemos concluir que la congruencia $x^2 \equiv -1 \pmod{365}$ ¿tiene solución?

Y más en general: Si tenemos la congruencia $x^2 \equiv a \pmod n$ con $n=p_1^{n_1}\cdots p_n^{n_k},\ \gcd(a,n)=1$ que es equivalente al sistema $x^2 \equiv a {\pmod p_1^{n_1}},\ldots,x^2 \equiv a \pmod{p_k^{n_k}}$ podemos concluir que la primera tiene solución si y sólo si cada una de $x^2\equiv a\pmod{p_i^{n_i}},\ \forall i=1,\ldots,k$ ¿tiene solución?

Gracias.

Answer 1

Tenemos $365 = 5 \times 73$ . La congruencia se convierte en $x^2 = -1 \mod 5$ y $x^2 = -1 \mod 73$ .

Tenemos si $p = 1 \mod 4 \implies x^2 = -1 \mod p$ tiene exactamente $2$ soluciones.

Así, $x^2 = -1 \mod 5$ tiene soluciones $x_0,x_1$ y $x^2 = -1 \mod 73$ tiene soluciones $y_0,y_1$ .

Las soluciones originales satisfacen cualquiera de las dos cosas: $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$ .

Para cada par de congruencias , $x$ se determina de forma única $\mod 365$ por el teorema chino del resto. Por lo tanto, la congruencia original tiene $4$ soluciones.

Answer 2

Si $\,m,n\,$ son coprimos entonces, por CRT, resolver un polinomio de coeficiente entero $\,f(x)\equiv 0\pmod{\!mn}\,$ equivale a resolver $\,f(x)\equiv 0\,$ mod $\,m\,$ y mod $\,n.\,$ Por CRT, cada combinación de una raíz $\,r_i\bmod m\,$ y una raíz $\,s_j\bmod n\,$ corresponde a una única raíz $\,t_{ij}\bmod mn,\,$ es decir

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

Answer 3

Demostramos el siguiente resultado:

Dejemos que $n,m$ sean enteros coprimos. Sea $a \in \Bbb Z$ . Entonces $a$ es un cuadrado módulo $nm$ si $a$ es mod cuadrado $n$ y $a$ es mod cuadrado $m$ .

Supongamos que hay números enteros $x_i$ tal que $x_1^2 \equiv a \pmod m$ y $x_2^2 \equiv a \pmod n$ donde $m,n$ son coprimos. Demostramos que $y^2 \equiv a \pmod {nm}$ tiene una solución (la inversa es obvia).

Sabemos que hay un número entero $y$ tal que $y \equiv x_1 \pmod m$ y $y \equiv x_2 \pmod n$ por el teorema chino del resto.

Entonces $y^2-a$ es un múltiplo de $m$ y $n$ por lo que es un múltiplo de $nm$ desde $(n,m)=1$ . Por lo tanto, $y^2 \equiv a \pmod {nm}$ .

---

De forma más general, tenemos el siguiente teorema (véase Ireland Rosen, p. 50)

Dejemos que $a,n \in \Bbb N$ sean enteros coprimos. Escribe $n=2^e p_1^{e_1} \cdots p_k^{e_k}$ como producto de potencias primarias distintas. Entonces $a$ es un cuadrado módulo $n$ si y sólo si

• $a$ es un cuadrado módulo $p_i$ (para $1 \leq i \leq k$ ) ; esto equivale a $a^{\dfrac{p_i-1}{2}} \equiv 1 \pmod{p_i}$

• $e>1 \implies a \equiv 1 \pmod{2^{2+r}}$ donde $r = 1$ si $e \geq 3$ y $r=0$ si $e=2$ .

Answer 4

Sí. Que una solución a $x^2+1 \equiv 0 \pmod {5}$ sea $r_{1}$ y que una solución a $x^2+1 \equiv 0 \pmod {73}$ sea $r_{2}$

Entonces, observe que por CRT tenemos que existe tal $x$ que $$x \equiv r_{1} \pmod {5}$$ $$x \equiv r_{2} \pmod {73}$$ Existe. A continuación, observe que para tal $x$ , $$x^2+1 \equiv 0 \pmod {5}$$ $$x^2+1 \equiv 0 \pmod {73}$$ Lo que da $$x^2+1 \equiv 0 \pmod {365}$$

Answer 5

Es cierto que debido a la Teorema del resto chino que afirma el mapa \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 {alinear} es un isomorfismo de anillo.