# Elementary, direct proof of when $5$ is a quadratic residue mod $p$

$\newcommand{\kron}[2]{\left( \frac{#1}{#2} \right)}$ It's easy to use Quadratic Reciprocity to show that $\kron{5}{p} = \kron{p}{5} = 1$ when $p \equiv \pm 1 \pmod 5$, and is $-1$ when $p \equiv \pm 2 \pmod 5$.

I'm interested in an elementary, direct proof of when this happens without appealing to either quadratic reciprocity directly or to things like Gauss's lemma (which is sort of like quadratic reciprocity in disguise). For example, this answer gives a direct proof of $\kron 2p$.

For $p \pmod 5$, this is not so bad. For instance, if $p \equiv 1 \pmod 5$, then one can use that $\left( \mathbb{Z}/p\mathbb{Z} \right)^\times$ is cyclic of order divisible by $5$ to get an element of order $5$, and then proceed as in this question.

But what about when $p \not \equiv 1 \pmod 5$? In particular, how might we handle when $p \equiv -1 \pmod 5$?

• Have you checked Gauss's writings? It would seem quite likely that if there was a direct elementary proof, then Gauss would have found it on the way to proving the general quadratic reciprocity law. Jul 7, 2014 at 22:33
• I've looked at some of his writings, but I admit that I have neither seen all of them nor understood everything I read. Most presentations of Gauss's material rely on either Gauss's Lemma or Gauss sums - both of which I know, but want to avoid for now. Jul 7, 2014 at 22:49
• Well, for example, in Disquistiones, Gauss proves that if $p \equiv 1$ (mod $3$), then $x^{2}+x+1 = 0$ has a root in ${\rm GF}(3)$ (and conversely), so that $(2x+1)^{2} = -3$ has a root in the field and $-3$ is a quadratic residue, etc. . Jul 7, 2014 at 22:55
• @Geoff: I see this coming from the group of units for $\mathbb{Z}/p\mathbb{Z}$ being cyclic of order $3k$, so that there is an element of order $3$. Then this element satisfies $x^2 + x + 1 \equiv 0 \pmod{p-1}$, and so on. Do you happen to know if Gauss's ideas extend to $p \not \equiv 1 \pmod p$? Jul 7, 2014 at 23:04
• Jul 7, 2014 at 23:08

Here's a start: If $p \equiv 1$ (mod $5$), then $F = \mathbb{Z}/p\mathbb{Z}$ contains an element of multiplicative order $5$, so $x^{5}-1 = (x-1)(x^{4}+x^{3}+x^{2}+x+1)$ splits into linear factors in $F[x].$ If $\omega \neq 1$ is one of its roots, then $(\omega+\omega^{-1})^{2} = 1- \omega - \omega^{-1}$ so that $x^{2} +x-1$ has a root in $F.$ Then $F$ contains $\sqrt{5}$ by solving the quadratic.

Continuation: Suppose now that $p \equiv -1$ (mod $5$). Then ${\rm GF}(p^{2})$ contains an element $\omega$ of multiplicative order $5$. Note however that $\omega +\omega^{p} \in {\rm GF}(p).$ Also, as $p \equiv -1$ (mod $5$), we have $\omega^{p} = \omega^{-1}.$ Hence $x^{2}+x-1$ has a root in ${\rm GF}(p),$ so that we still have $\sqrt{5} \in {\rm GF}(p).$

I think the other direction follows ( at least for odd $p$) by mimicking the proof of the constructibility of the regular pentagon but working over ${\rm GF}(p).$ More precisely, if ${\rm GF}(p)$ contains $\sqrt{5}$ we can show that a primitive $5$-th root of unity $\omega$ satisfies a quadratic equation over ${\rm GF}(p).$ Hence ${\rm GF}(p^{2})$ contains an element of multiplicative order $5$, so that $5$ divides $p^{2}-1$ and $p \equiv \pm 1$ (mod $5$).

More detail: We know that $\alpha = \omega +\omega^{-1}$ is a root of $x^{2}+x-1$ as above, and lies in ${\rm GF}(p).$ Now $(\omega - \omega^{-1})^{2} = -2 - (1 + \omega + \omega^{-1}) = -3 - \alpha.$ Hence $\omega - \omega^{-1}$ lies in a quadratic extension (at most) of ${\rm GF}(p).$ Since $\omega+ \omega^{-1} \in {\rm GF}(p),$ we see that $\omega$ itself lies in a (at most) quadratic extension on ${\rm GF}(p).$

To treat the case $p = 2,$ note that $2$ is not a quadratic residue (mod $5$) by inspection.

Later note in response to question of PI: I think this approach may generalize, but it seems to stray into the realm of Gauss sums, and I have not worked through all the details: let $p,q$ be odd primes, and let $\omega$ be a primitive $q$-th root of unity in $\overline{{\rm GF}(p)}.$ Consider $\sigma = \sum_{i=0}^{\frac{q-3}{2}} \omega^{p^{i}}.$ Suppose that $p$ is a quadratic residue (mod $q$). Then $p^{\frac{q-1}{2}} \equiv 1$ (mod $q$). Hence $\sigma^{p} = \sigma$ and $\sigma \in {\rm GF}(p).$ Conversely, if $p$ is not a quadratic residue (mod $p$), then $\sigma^{p} \neq \sigma$ as $p^{\frac{q-1}{2}} \not \equiv 1$ (mod $q$).

• Silly question from me: why does $\text{GF}(p^2)$ have an element of order $5$? The order of the group of units of $\text{GF}(p^2)$ is $p^2 - 1 = (p+1)(p-1)$... aha. To be honest, I was thinking it was $\varphi(p^2)$ until just now. I'm going to leave this comment here as a note to myself. Next question: $\omega + \omega^p$ is in $F_p$. One way to see this is that it's fixed under Frobenius. Is there a non-Galois theoretic way of seeing it too (that's likely far simpler, but I don't deal very much with these so much anymore)? Jul 8, 2014 at 0:04
• By the way, I like this proof very much. +1 and (very likely) an accept later. This makes me wonder about something else: now the fact that we can get $-1 \pmod 5$ seems special to the size of the group of units of $F_{p^2}$. Do you see a way to extend this to handle something like... $p \equiv 2 \pmod 7$ (and $\equiv 1 \pmod 4$) leading to $7$ being a quadratic residue mod $p$? Or have we reached the end of how far we can push? Jul 8, 2014 at 0:14
• Well, you can check without Galois theory that $(\omega + \omega^{p})^{p} = \omega^{p} + \omega^{p^{2}} = \omega^{p}+ \omega,$ since we know $\omega \in {\rm GF}(p^{2}).$ Hence $\omega + \omega^{p} \in {\rm GF}(p)$ as it is a root of $x^{p}-x.$ Jul 8, 2014 at 0:14
• As to your most recent question, i suppose the question is how far you can push things by ad hoc methods before you reach the point where you re dealing with Gauss sums. My honest answer at the moment to that is "I don't know". Jul 8, 2014 at 0:19

One direction; if $(5|p) = 1,$ then $(20|p) =1.$ So, there is a solution to $$20 \equiv b^2 \pmod {4p},$$ where if we first found $b$ odd we switch to $p-b$ for it to become even. or $$20 = b^2 - 4 p t.$$ So, we have the indefinite binary quadratic form $$\langle p,b,t \rangle.$$

More on its way...

Alright, discriminant 20 has class number one, any such form is $SL_2 \mathbb Z$ equivalent to $x^2 - 5 y^2.$ What this means is that there is an integer expression $$x^2 - 5 y^2 = p.$$

Now, we find $$x^2 \equiv p \pmod 5.$$ Which says that $(p|5)=1.$

EXTRA: i think this works; if $(q|5)=1,$ some form in the principal genus, the same as $u^2 - q v^2,$ represents $5.$ The form is rationally equivalent, without essential denominator (Siegel's phrase), to $u^2 - q v^2,$ so we have rational $r^2 - q s^2 = 5,$ clear denominators to get integer $x^2 - q y^2 = 5 z^2.$ But then $x^2 -5 z^2 = q y^2$ and $x^2 \equiv 5 y^2 \pmod q,$ so $(5|q)=1.$

Alright, needs to be checked for hidden reciprocity, I suppose. Kap used to say that the totality of the theory of binary forms was equivalent to quadratic reciprocity. May be something to that.

There may be some separation needed depending on $q \pmod 4.$ Short theorem in Mordell's book that $x^2 - q y^2$ and $-x^2 + q y^2$ are equivalent when $q \equiv 1 \pmod 4,$ but they are distinct otherwise, and that may matter... When $q \equiv 1 \pmod 4,$ we can descend to discriminant $q$ with principal form $x^2 + x y - \frac{p-1}{4}y^2$ and guarantee a single genus, although not always a single class.

Not an answer, but might be useful. In section 6.2 of:

Ireland and Rosen: A Classical Introduction to Modern Number Theory

they use some basic algebra and a primitive eighth root of unity to derive the quadratic character of 2, and then in exercise 8 at the end of the chapter, they ask the reader to do something similar to derive the quadratic character of -3 (I did the exercise some years ago, but no longer have my notes). I suspect something similar could be done with 5.

• Hi, John. half of this is pretty straightforward. The other direction may need a different trick. Jul 7, 2014 at 23:06
• I am sure you are right, Will - I have unfortunately forgotten most of the little that I used to know on this topic, unfortunately :( Jul 7, 2014 at 23:10
• That is unfortunate unfortunate, unfortunately Jul 7, 2014 at 23:11