A particular case of the quadratic reciprocity law

To motivate my question, recall the following well-known fact: Suppose that $p\equiv 1\pmod 4$ is a prime number. Then the equation $x^2\equiv -1\pmod p$ has a solution.

One can show this as follows: Consider the following polynomial in ${\mathbb Z}_p[x]$: $x^{4k}-1$, where $p=4k+1$. The roots of this polynomial are precisely the elements of ${\mathbb Z}_p^*$, each one with multiplicity 1. The polynomial factors as $(x^{2k}-1)((x^k)^2+1)$, and it follows that if $a$ is any element of ${\mathbb Z}_p^*$ with $a^{2k}\ne 1$ (and there are precisely $(p-1)/2$ possible such $a$), then $b=a^k$ satisfies $b^2\equiv -1\pmod p$.

Of course, there are other arguments, but I am interested in pursuing this line of reasoning. My question is the following:

From the quadratic reciprocity law, we have that $x^2\equiv -2\pmod p$ has a solution iff $p\equiv 1$ or $3\pmod 8$. Is there a proof of the right-to-left implication using some polynomial and appropriate counting of roots, as in the case shown above?

-
It seems to me that your example works because the polynomial factors over Z, and then you can deduce facts about p as corollaries. On the other hand, $x^2+2$ doesn't factor over Z, so I sort of doubt the same method will work. On the other hand, I know next to nothing about number theory -- I'd love to be proven wrong... –  Aaron Mazel-Gee Nov 10 '10 at 7:25
Is this argument taken from the book of Weil? –  awllower Feb 26 '11 at 8:30
@awllower: Sorry for not replying sooner; didn't have the chance to check back for a while. I found the argument on my own, and then reading Cox's book mentioned in a comment below I saw the general context of it. I have now seen it in Weil's book as well; I am studying this book, very beautiful. –  Bruce George Apr 17 '11 at 16:16

If $p=8k+1$ then consider $a$ with $a^{4k}\equiv-1$ (mod $p$). Let $b=a^k-a^{7k}$. Then $$b^2=a^{2k}-2a^{8k}+a^{14k}\equiv a^{2k}(1+a^{4k})-2 \equiv-2\pmod{p}.$$ For $p\equiv3$ (mod $8$) this argument will also work but you need to use the Galois field $GF(p^2)$ rather than the integers modulo $p$.

-
Many thanks! This answer and the one by David indicate that there is much more here than I first thought. I'll go read a little about it. –  Bruce George Nov 10 '10 at 16:21

Similar arguments work for other cases as well. For example, if $p = 1 \mod 3k$, find $a$ such that $a^{3k}=1$ and $a^k \neq 1$. Set $z=a^k$, then $z^2+z+1=0$ and we deduce that $(z - z^2)^2 = -3$.

For a larger example, if $p=5k+1$, then there is an $a$ in $\mathbb{F}_p$ with $a^{5k}=1$ and $a^k \neq 1$. Let $z=a^k$, so $z^4+z^3+z^2+z+1=0$.

Let $b = z - z^2 - z^3 + z^4$. Then $$b^2 = z^8 - 2 z^7 - z^6 + 4 z^5 - z^4 - 2 z^3 + z^2=$$ $$-z^4 - z^3 - z^2 - z + 4 = 5.$$

So $p \equiv 1 \mod 5$ implies that $\left( \frac{5}{p} \right)=1$. Just as in Robin's answer, you can also prove that $p \equiv 4 \mod 5$ implies $\left( \frac{5}{p} \right)=1$ in this manner, but it is more difficult: the element $z$ will live in $\mathbb{F}_{p^2}$, and you will need to check that $b$ lives in $\mathbb{F}_{p}$.

In fact, for every squarefree $M$, let $\Delta$ be $|M|$ if $M \equiv 1 \mod 4$ and $\Delta=4 |M|$ otherwise. Then you can prove in this manner the statement "if $p = 1 + \Delta k$ then $\left( \frac{\Delta}{p} \right) = 1$." The first steps are the same in each case: find $a$ in $\mathbb{F}_p$ such that $a^{\Delta k}=1$ but $a^{d k} \neq 1$ for any proper divisor $d$ of $\Delta$. Let $z=a^k$, so $z$ is a primitive $\Delta$ root of unity in $\mathbb{F}_p$. At this point, some magic polynomial $g_M$ is introduced, such that $g_M(z)^2 = M$. If you want to prove the full quadratic reciprocity law, you can do so using this approach as well, but you will need to work in finite fields of non-prime order.

I often thought it would be fun to assign a class the job of finding the magic polynomials $g_M$, for various values of $M$, and see if they could guess the general pattern. Hint: $g$ stands for "Gauss sum".

-
David, many thanks for your answer. Just in case, do you know of a reference where to learn about these ideas? –  Bruce George Nov 10 '10 at 16:22
I learned this from Chapter 1 of Serre's Course in Arithmetic. Like all of Serre's writing, it is very clear and very concise. If anyone knows a more beginner friendly exposition, similar to the one I started here, I'd be curious to know a reference. –  David Speyer Nov 10 '10 at 16:53
Thank you. Do you know "Primes of the form $x^2 + ny^2$"? –  Bruce George Nov 10 '10 at 21:49
Yes, I do. If you can follow Cox's book, you will have no trouble with Serre. –  David Speyer Nov 11 '10 at 0:29
@David: Many thanks for the tip. I've been reading (and enjoying) Serre's book. –  Bruce George Dec 18 '10 at 3:15

If I remember correctly, this approach with a Gauss sum (associated to an 8th root of 1 in a finite field) is used in the first page or two of Serre's Cours d'Arithmetique to determine the "supplementary law" for $\left( \frac{2}{p} \right)$. The magical algebraic identity in this case is that if $a^4 = -1$, then $(a \pm 1/a)^2 = \pm 2$.

-
It's actually $a^2$ in the numerator (you have $0 = a^4 + 1 = (a^2 +1)^2 - 2a^2$ and similarly for the other sign). –  Geoff Robinson Aug 7 '11 at 9:10