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?

 A: 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$.
A: 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$.
A: 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".
