Finding quadratic residues without Legendre symbols

Question

I ran into two very similar problems concerning quadratic residues, and I'm having a bit of trouble working through them. These problems are supposed to rely exclusively on the theory of cyclic groups, without use of Legendre symbols. I'm posting both in one question since I roughly managed to solve the first one and it's meant to show my thought process towards solving the second.

Let $p$ be a prime congruent to $1$ modulo $3$. Show that there exists an $a \in \mathbb{Z}$ such that $a^2 + a + 1 \equiv 0 \textrm{ mod } p$ and conclude that $-3$ is a square modulo $p$.

To solve this one, I let $p = 3k + 1$, and take $g \in (\mathbb{Z}_p, \times)$ to be a generator from which follows that $g^{3k} - 1 = (g^k - 1)(g^{2k} + g^k + 1) \equiv 0 \textrm{ mod } p$. Since $g$ is a generator, $g^k \ne 1$. To conclude $-3$ is a square, I (somewhat randomly) noticed that

\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*}

I was wondering, is there any significance to the element $g^k - g^{-k}$ as a root for $-3$? Is there any way to intuitively know immediately that's the square you're looking for? I remember seeing similarly defined elements before, and I pretty much just plugged it in hoping for the best, without really knowing what I was doing. The next problem has me completely stumped.

Let $p$ be a prime congruent to $1$ modulo $5$. Show that there exists an $a \in \mathbb{Z}$ such that $(a + a⁴)² + (a + a⁴) - 1 \equiv 0 \textrm{ mod } p$ and conclude that $5$ is a square modulo $p$.

I sort of have this sense that I'm gonna need an element of order $10$, i.e. $g^{\frac{5k}{2}}$ where $g$ is yet again a generator, however I can't seem to get anywhere with this. If I let $x = a + a^4$, then I can tell I'm basically looking for an element $x$ which has the next element $x + 1$ as its inverse, but that doesn't really help me forward.

Answer 1

Hint: If $a^5 = 1$ then $a^4 = a^{-1}$ and $(a+a^4)^2 + (a+a^4) - 1 = a^{-2}(a^4 + a^3 + a^2 + a + 1)$.

Also if $x^2 + x - 1 = 0$ in $\mathbb Z_p$, then $4(x^2 + x - 1) = (2x+1)^2 - 5 = 0$.

Answer 2

A substantial part of your question seems to be “how do I intuitively arrive at an expression which yields the desired square root?”. I want to address this first.

In both cases the question is structured as “show there exists a solution to this quadratic, hence $d$ is a square modulo $p$”. In the first question the quadratic is $x^2+x+1$, and in the second question it’s $x^2+x-1$. Notice that in each case the desired square root is exactly the discriminant $b^2 - 4ac$ from the quadratic formula.

Intuitively, the idea is that if a ring contains solutions to the quadratic then the square root in the quadratic formula “should” work in that ring. (This isn’t universally true: when a cubic polynomial has all real roots, the cubic formula still involves taking square roots of negative numbers.). The way to expose this explicitly is just to complete the square:

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

As for how to guess at the element which makes it work, in both cases we know that $\mathbb Z_p$ contains a primitive $r$th root of unity for $r=3$ and $r=5$ respectively. In some sense that’s about all the specialized knowledge we possess. I think the author is hoping/expecting the reader to first try plugging in that root of unity into $a$, since there’s no simpler value to choose from, and the questions are designed to make this work on that first try.

For the second question it may have resulted in a rather intimidating-looking expression hiding inside the quadratic, but presumably the intent was for the first question to go very smoothly, giving the reader the hope that the exact same strategy will work for the second.