Encontrar residuos cuadráticos sin símbolos de Legendre

Question

Me he encontrado con dos problemas muy parecidos relacionados con los residuos cuadráticos, y estoy teniendo un poco de problemas para resolverlos. Se supone que estos problemas se basan exclusivamente en la teoría de grupos cíclicos, sin utilizar los símbolos de Legendre. Estoy publicando los dos en una sola pregunta, ya que más o menos logré resolver el primero y es para mostrar mi proceso de pensamiento hacia la resolución del segundo.

Dejemos que $p$ sea un primo congruente con $1$ modulo $3$ . Demuestre que existe un $a \in \mathbb{Z}$ tal que $a^2 + a + 1 \equiv 0 \textrm{ mod } p$ y concluir que $-3$ es un cuadrado módulo $p$ .

Para resolverlo, he dejado que $p = 3k + 1$ y tomar $g \in (\mathbb{Z}_p, \times)$ para ser un generador del que se deduce que $g^{3k} - 1 = (g^k - 1)(g^{2k} + g^k + 1) \equiv 0 \textrm{ mod } p$ . Desde $g$ es un generador, $g^k \ne 1$ . Para concluir $-3$ es un cuadrado, me he dado cuenta (un poco al azar) de que

\begin{align*} (g^k - g^{-k})^2 &= g^{2k} - 2 + g^{-2k} \\ &= g^{2k} + g^k + 1 - 3 \\ &\equiv -3 \textrm{ mod } p \end{align*}

Me preguntaba si el elemento $g^k - g^{-k}$ como raíz para $-3$ ? ¿Hay alguna forma de saber intuitivamente y de inmediato que ese es el cuadrado que se busca? Recuerdo haber visto antes elementos definidos de forma similar, y me limité a introducirlos esperando lo mejor, sin saber realmente lo que estaba haciendo. El siguiente problema me tiene completamente perplejo.

Dejemos que $p$ sea un primo congruente con $1$ modulo $5$ . Demuestre que existe un $a \in \mathbb{Z}$ tal que $(a + a)² + (a + a) - 1 \equiv 0 \textrm{ mod } p$ y concluir que $5$ es un cuadrado módulo $p$ .

Tengo la sensación de que voy a necesitar un elemento de orden $10$ es decir $g^{\frac{5k}{2}}$ donde $g$ es de nuevo un generador, sin embargo parece que no puedo llegar a ninguna parte con esto. Si dejo que $x = a + a^4$ Entonces puedo decir que básicamente estoy buscando un elemento $x$ que tiene el siguiente elemento $x + 1$ como su inversa, pero eso no me ayuda a avanzar.

Answer 1

Sugerencia: Si $a^5 = 1$ entonces $a^4 = a^{-1}$ y $(a+a^4)^2 + (a+a^4) - 1 = a^{-2}(a^4 + a^3 + a^2 + a + 1)$ .

También si $x^2 + x - 1 = 0$ en $\mathbb Z_p$ entonces $4(x^2 + x - 1) = (2x+1)^2 - 5 = 0$ .

Answer 2

Una parte sustancial de tu pregunta parece ser "¿cómo puedo llegar intuitivamente a una expresión que dé la raíz cuadrada deseada?". Quiero abordar esto primero.

En ambos casos la pregunta está estructurada como "demuestre que existe una solución para esta cuadrática, por lo tanto $d$ es un cuadrado módulo $p$ ". En la primera pregunta la cuadrática es $x^2+x+1$ y en la segunda pregunta es $x^2+x-1$ . Observe que en cada caso la raíz cuadrada deseada es exactamente el discriminante $b^2 - 4ac$ de la fórmula cuadrática.

Intuitivamente, la idea es que si un anillo contiene soluciones a la cuadrática entonces la raíz cuadrada en la fórmula cuadrática "debería" funcionar en ese anillo. (Esto no es universalmente cierto: cuando un polinomio cúbico tiene todas las raíces reales, la fórmula cúbica todavía implica tomar raíces cuadradas de números negativos). La forma de exponer esto explícitamente es simplemente completar el cuadrado:

$$x^2 + x + 1 = 0, \\ 4x^2 + 4x + 4 = 0, \\ 4x^2 + 4x + 1 = -3, \\ (2x+1)^2 = -3.$$

En cuanto a cómo adivinar el elemento que lo hace funcionar, en ambos casos sabemos que $\mathbb Z_p$ contiene una primitiva $r$ raíz de la unidad para $r=3$ y $r=5$ respectivamente. En cierto sentido, eso es todo el conocimiento especializado que poseemos. Creo que el autor espera que el lector intente primero introducir esa raíz de unidad en $a$ , ya que no hay un valor más simple para elegir, y las preguntas están diseñadas para que esto funcione en el primer intento.

Para la segunda pregunta puede haber resultado una expresión de aspecto bastante intimidatorio escondida dentro de la cuadrática, pero presumiblemente la intención era que la primera pregunta se desarrollara sin problemas, dando al lector la esperanza de que la misma estrategia funcionara para la segunda.