¿Tiene soluciones $x^2+x+1 \equiv 0 \pmod {997}$? ¿Por qué sí o por qué no?

Question

Tengo dificultades para resolver este problema en mi libro de texto.

¿Tiene soluciones $x^2+x+1 \equiv 0\pmod{997}$? ¿Por qué o por qué no?

Supongo que el primer paso sería $$ \begin{array}{l} (2x+1)^2 \equiv (-3)\pmod{997} \\ y^2 \equiv -3\pmod{997} \end{array} $$ ¿Eso significa que no hay solución?

Answer 1

De aquí, usando $\displaystyle\left(\frac{ab}p\right)=\left(\frac ap\right)\left(\frac bp\right)$

$$\left(\frac{-3}p\right)=\left(\frac{-1}p\right)\left(\frac 3p\right)$$

Como $\displaystyle997\equiv1\pmod4,\left(\frac{-1}p\right)=1$ (Ver $-1$ es un residuo cuadrático módulo $p$ si y solo si $p\equiv 1\pmod{4}$)

Ahora usa Teorema de Reciprocidad Cuadrática, $$\left(\frac 3{997}\right)\left(\frac{997}3\right)=1$$

Como $997\equiv1\pmod3,$ $$\left(\frac{997}3\right)=\left(\frac13\right)$$

Ahora $\displaystyle\left(\frac1p\right)=(1)^{\dfrac{p-1}2}=1$ para todo primo impar $p

Answer 2

Pista $\,\ 997\, =\, 5^2\! + 3(18)^2\,\Rightarrow\, -3 \equiv (5/18)^2\pmod{997}.\ $ O, utilizar reciprocity cuadrática.

Answer 3

De acuerdo, vamos a probar algunas operaciones aritméticas burdas de fuerza bruta. Estamos viendo $$ x^2 + x + 1 \pmod{997}. $$ Las ecuaciones cuadráticas se resuelven completando el cuadrado, y eso significa tomar la mitad del coeficiente del término de primer grado y elevarlo al cuadrado, y sumarlo. El coeficiente del término de primer grado es $1$, entonces ¿cuál es la mitad de $1$ en $\bmod997$? Como $2\times499\equiv1$, la mitad de $1$ es $499$. El cuadrado de eso es $499^2\equiv748\pmod{997}$. Entonces tenemos $$ (x^2 + x + 748) +(1-748) \equiv (x + 499)^2 + 250 \equiv 0. $$ $$ (x+499)^2 \equiv-250\equiv747 $$ Ahora la pregunta es si $747$ tiene una raíz cuadrada. Cálculos numéricos burdos a través de computadora me dicen que $194^2\equiv747$, entonces por supuesto $(-194)^2\equiv747$, y $-194\equiv803$. Entonces $x+449 \equiv\pm 194$, lo que significa que $x+449\equiv(194\text{ o }803)$.

Has escrito $(2x+1)\equiv-3$. Como $388^2\equiv-3$, eso significaría que hay una solución.

Moral de la historia: La parte "difícil" es encontrar raíces cuadradas. Eso se puede hacer por fuerza bruta, pero sería deseable tener una manera inteligente de hacerlo. La naturaleza de la manera "inteligente" de hacerlo ha sido abordada en respuestas publicadas por otros. La mitad de los números en $\{1,\ldots,996\}$ tienen raíces cuadradas módulo $997$ y la otra mitad no.